Similar documents
1

, = = 7 6 = 42, =

x, y x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 xy (x y) (x + y) xy (x y) (x y) ( x 2 + xy + y 2) = 15 (x y)

ad bc A A A = ad bc ( d ) b c a n A n A n A A det A A ( ) a b A = c d det A = ad bc σ {,,,, n} {,,, } {,,, } {,,, } ( ) σ = σ() = σ() = n sign σ sign(

all.dvi

NOTE P, A,. A P ( A, P ),,.,. P A. (set) (set), (). (element), (element).,.,. ( A, B, X, Y, P ), { } (),..3 (union) A, B,A B, A B (union),. A B = {x x


‚åŁÎ“·„´Šš‡ðŠp‡¢‡½‹âfi`fiI…A…‰…S…−…Y…•‡ÌMarkovŸA“½fiI›ð’Í

untitled

( a 3 = 3 = 3 a a > 0(a a a a < 0(a a a

koji07-01.dvi

x () g(x) = f(t) dt f(x), F (x) 3x () g(x) g (x) f(x), F (x) (3) h(x) = x 3x tf(t) dt.9 = {(x, y) ; x, y, x + y } f(x, y) = xy( x y). h (x) f(x), F (x

2012 A, N, Z, Q, R, C

all.dvi


F = 0 F α, β F = t 2 + at + b (t α)(t β) = t 2 (α + β)t + αβ G : α + β = a, αβ = b F = 0 F (t) = 0 t α, β G t F = 0 α, β G. α β a b α β α β a b (α β)

9. 05 L x P(x) P(0) P(x) u(x) u(x) (0 < = x < = L) P(x) E(x) A(x) P(L) f ( d EA du ) = 0 (9.) dx dx u(0) = 0 (9.2) E(L)A(L) du (L) = f (9.3) dx (9.) P

ii

II A A441 : October 02, 2014 Version : Kawahira, Tomoki TA (Kondo, Hirotaka )

I II III IV V

newmain.dvi

Microsoft PowerPoint - 3.ppt [互換モード]

I II III 28 29

生活設計レジメ

44 4 I (1) ( ) (10 15 ) ( 17 ) ( 3 1 ) (2)


koji07-02.dvi

IMO 1 n, 21n n (x + 2x 1) + (x 2x 1) = A, x, (a) A = 2, (b) A = 1, (c) A = 2?, 3 a, b, c cos x a cos 2 x + b cos x + c = 0 cos 2x a

行列代数2010A

０４年度LS民法Ⅰ教材改訂版.PDF

オートマトン 形式言語及び演習 4. 正規言語の性質 酒井正彦 正規言語の性質 反復補題正規言語が満たす性質 ある与えられた言語が正規言語でないことを証明するために その言語が正規言語であると


.5 z = a + b + c n.6 = a sin t y = b cos t dy d a e e b e + e c e e e + e 3 s36 3 a + y = a, b > b 3 s363.7 y = + 3 y = + 3 s364.8 cos a 3 s365.9 y =,

SO(2)

50 2 I SI MKSA r q r q F F = 1 qq 4πε 0 r r 2 r r r r (2.2 ε 0 = 1 c 2 µ 0 c = m/s q 2.1 r q' F r = 0 µ 0 = 4π 10 7 N/A 2 k = 1/(4πε 0 qq

1 0/1, a/b/c/ {0, 1} S = {s 1, s 2,..., s q } S x = X 1 X 2 X 3 X n S (n = 1, 2, 3,...) n n s i P (X n = s i ) X m (m < n) P (X n = s i X n 1 = s j )

PSCHG000.PS

(1) (2) (1) (2) 2 3 {a n } a 2 + a 4 + a a n S n S n = n = S n

ii 3.,. 4. F. (), ,,. 8.,. 1. (75%) (25%) =7 20, =7 21 (. ). 1.,, (). 3.,. 1. ().,.,.,.,.,. () (12 )., (), 0. 2., 1., 0,.


linearal1.dvi

入試の軌跡

2005

meiji_resume_1.PDF


T T T T A 0 1 A 1 A P (A 1 ) = C 1 6 C 8C 3 = 15 8, P (A ) = C 6 C 1 8C 3 = 3 8 T 5 B P (A 1 B) = =

x V x x V x, x V x = x + = x +(x+x )=(x +x)+x = +x = x x = x x = x =x =(+)x =x +x = x +x x = x ( )x = x =x =(+( ))x =x +( )x = x +( )x ( )x = x x x R

untitled

6kg 1.1m 1.m.1m.1 l λ ϵ λ l + λ l l l dl dl + dλ ϵ dλ dl dl + dλ dl dl 3 1. JIS 1 6kg 1% 66kg 1 13 σ a1 σ m σ a1 σ m σ m σ a1 f f σ a1 σ a1 σ m f 4

r 1 m A r/m i) t ii) m i) t B(t; m) ( B(t; m) = A 1 + r ) mt m ii) B(t; m) ( B(t; m) = A 1 + r ) mt m { ( = A 1 + r ) m } rt r m n = m r m n B

A 2 3. m S m = {x R m+1 x = 1} U + k = {x S m x k > 0}, U k = {x S m x k < 0}, ϕ ± k (x) = (x 0,..., ˆx k,... x m ) 1. {(U ± k, ϕ± k ) 0 k m} S m 1.2.

( ) ( ) lex LL(1) LL(1)

(1.2) T D = 0 T = D = 30 kn 1.2 (1.4) 2F W = 0 F = W/2 = 300 kn/2 = 150 kn 1.3 (1.9) R = W 1 + W 2 = = 1100 N. (1.9) W 2 b W 1 a = 0

zz + 3i(z z) + 5 = 0 + i z + i = z 2i z z z y zz + 3i (z z) + 5 = 0 (z 3i) (z + 3i) = 9 5 = 4 z 3i = 2 (3i) zz i (z z) + 1 = a 2 {

17 ( :52) α ω 53 (2015 ) 2 α ω 55 (2017 ) 2 1) ) ) 2 2 4) (α β) A ) 6) A (5) 1)

微分積分 サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行時のものです.

x = a 1 f (a r, a + r) f(a) r a f f(a) 2 2. (a, b) 2 f (a, b) r f(a, b) r (a, b) f f(a, b)

1 8, : 8.1 1, 2 z = ax + by + c ax by + z c = a b +1 x y z c = 0, (0, 0, c), n = ( a, b, 1). f = n i=1 a ii x 2 i + i<j 2a ij x i x j = ( x, A x), f =

n (1.6) i j=1 1 n a ij x j = b i (1.7) (1.7) (1.4) (1.5) (1.4) (1.7) u, v, w ε x, ε y, ε x, γ yz, γ zx, γ xy (1.8) ε x = u x ε y = v y ε z = w z γ yz

2 7 V 7 {fx fx 3 } 8 P 3 {fx fx 3 } 9 V 9 {fx fx f x 2fx } V {fx fx f x 2fx + } V {{a n } {a n } a n+2 a n+ + a n n } 2 V 2 {{a n } {a n } a n+2 a n+

II (1) log(1 + r/100) n = log 2 n log(1 + r/100) = log 2 n = log 2 log(1 + r/100) (2) y = f(x) = log(1 + x) x = 0 1 f (x) = 1/(1 + x) f (0) = 1

I

,2,4


応力とひずみ.ppt

熊本県数学問題正解

( )/2 hara/lectures/lectures-j.html 2, {H} {T } S = {H, T } {(H, H), (H, T )} {(H, T ), (T, T )} {(H, H), (T, T )} {1

?

1 Abstract 2 3 n a ax 2 + bx + c = 0 (a 0) (1) ( x + b ) 2 = b2 4ac 2a 4a 2 D = b 2 4ac > 0 (1) 2 D = 0 D < 0 x + b 2a = ± b2 4ac 2a b ± b 2

³ÎΨÏÀ

1990 IMO 1990/1/15 1:00-4:00 1 N N N 1, N 1 N 2, N 2 N 3 N 3 2 x x + 52 = 3 x x , A, B, C 3,, A B, C 2,,,, 7, A, B, C

II Time-stamp: <05/09/30 17:14:06 waki> ii

i


Wide Scanner TWAIN Source ユーザーズガイド

( 23 )

経済分析 第82号

4.6: 3 sin 5 sin θ θ t θ 2t θ 4t : sin ωt ω sin θ θ ωt sin ωt 1 ω ω [rad/sec] 1 [sec] ω[rad] [rad/sec] 5.3 ω [rad/sec] 5.7: 2t 4t sin 2t sin 4t

A(6, 13) B(1, 1) 65 y C 2 A(2, 1) B( 3, 2) C 66 x + 2y 1 = 0 2 A(1, 1) B(3, 0) P 67 3 A(3, 3) B(1, 2) C(4, 0) (1) ABC G (2) 3 A B C P 6

The Physics of Atmospheres CAPTER :

δ ij δ ij ˆx ˆx ŷ ŷ ẑ ẑ 0, ˆx ŷ ŷ ˆx ẑ, ŷ ẑ ẑ ŷ ẑ, ẑ ˆx ˆx ẑ ŷ, a b a x ˆx + a y ŷ + a z ẑ b x ˆx + b

1/1 lim f(x, y) (x,y) (a,b) ( ) ( ) lim limf(x, y) lim lim f(x, y) x a y b y b x a ( ) ( ) xy x lim lim lim lim x y x y x + y y x x + y x x lim x x 1

(Basics of Proability Theory). (Probability Spacees ad Radom Variables,, (Ω, F, P ),, X,. (Ω, F, P ) (probability space) Ω ( ω Ω ) F ( 2 Ω ) Ω σ (σ-fi

直交座標系の回転

2 1 κ c(t) = (x(t), y(t)) ( ) det(c (t), c x (t)) = det (t) x (t) y (t) y = x (t)y (t) x (t)y (t), (t) c (t) = (x (t)) 2 + (y (t)) 2. c (t) =

68 A mm 1/10 A. (a) (b) A.: (a) A.3 A.4 1 1

第１部　一般的コメント


A A = a 41 a 42 a 43 a 44 A (7) 1 (3) A = M 12 = = a 41 (8) a 41 a 43 a 44 (3) n n A, B a i AB = A B ii aa

9 1. (Ti:Al 2 O 3 ) (DCM) (Cr:Al 2 O 3 ) (Cr:BeAl 2 O 4 ) Ĥ0 ψ n (r) ω n Schrödinger Ĥ 0 ψ n (r) = ω n ψ n (r), (1) ω i ψ (r, t) = [Ĥ0 + Ĥint (

1 filename=mathformula tex 1 ax 2 + bx + c = 0, x = b ± b 2 4ac, (1.1) 2a x 1 + x 2 = b a, x 1x 2 = c a, (1.2) ax 2 + 2b x + c = 0, x = b ± b 2


5 n P j j (P i,, P k, j 1) 1 n n ) φ(n) = n (1 1Pj [ ] φ φ P j j P j j = = = = = n = φ(p j j ) (P j j P j 1 j ) P j j ( 1 1 P j ) P j j ) (1 1Pj (1 1P


福岡大学人文論叢47-3

73

B ver B

K E N Z OU

第１章　国民年金における無年金

情報数理学

Transcription:

オートマトンと言語理論 テキスト 成蹊大学理工学部情報科学科 山本真基

ii

iii 1 1 1.1.................................. 1 1.2................................ 5 1.3............................. 5 2 7 2.1.................................. 7 3 15 3.1 DFA..................... 15 3.2 NFA.................... 19 3.3 ϵ- ϵ-nfa.................. 24 3.4............................ 26 3.5................................. 31 4 35 4.1................................ 35 4.2................................... 41 4.3............................ 42 5 45 5.1................... 45 5.2.......................... 50 5.3............................... 51 70

iv

1 1 1.1 1.1 Σ Σ Σ x Σ x x x ϵ Σ Σ = 1.1. a, b, c,..., z, A, B, C,..., Z 1.1 ( ). 1. Σ = {0, 1} 2. Σ = {0, 1, 2,..., 9, a,b,c,...,z,a,b,c,...,z, #, $, %} 3. Σ = {0, 1, (, )} 1.2 ( ). Σ = {0, 1, (, )} Σ

2 1 1. 0101001 2. (101)(((0 3. ((000)(111))(010)(101) 00#11 Σ # Σ 1.1. Σ = {a,b,c} Σ 1.1. Σ p p Σ 1.3. 1.1 #include<iostream> using namespace std; int main() { int a=1; cout << a << endl; } 1.1: Σ #include<iostream> using namespace std; int main() { int a=1; cout << a << endl; } 1.2: Σ Σ 1.2 Σ Σ Σ

1.1 3 L L L L 1.4 ( ). Σ = {a,b,c} L Σ L = {a, ab, abc, ababa, abbcca}. L = 5 1.5 ( ). Σ = {0, 1} L Σ L = {x : n N[x n ]}. L 1.6 ( ). Σ L Σ L = {p : p }. L 1.2. Σ Σ Σ 1.3 Σ k x 1, x 2,..., x k Σ x 1 x 2 x k x 1 = x 2 = = x k = a Σ x 1 x 2 x k a k k = 0 a 0 ϵ 1.4 Σ Σ Σ Σ Σ Σ Σ def = {xy : x, y Σ}.

4 1 k N Σ k Σ 0 def = Σ Σ Σ }{{} def = {ϵ} k def = {x 1 x 2... x k : x 1, x 2,..., x k Σ} Σ Σ Σ def = k N {0} Σ k. 1.2. Σ x Σ x Σ L Σ L Σ 1.7. Σ = {0, 1} 1. Σ Σ = {00, 01, 10, 11} 2. Σ 3 = {000, 001, 010, 011, 100, 101, 110, 111} 1. Σ x =000 x Σ 3 Σ 2. Σ L = {000, 111} L Σ 3 Σ 1.1. Σ Σ = n Σ k = n k k = 0 Σ 0 = {ϵ} = 1 1.3. 1.4. Σ Σ Σ Σ Σ 1.5. 1. ϵ Σ

1.2 5 2. = {ϵ} 1.2 Σ = {0, 1, 2,..., 9,.} Σ L L def = {a Σ : a }. 1. 0 L 2. 012 L 3. 3.1415926 L 4..123 L 5. 1 L 6. 12345.000 L 7. 10/3 L L Σ = Σ \ {.}, Σ = Σ \ {0} {0} Σ Σ ({0} Σ Σ ) {.} Σ Σ 1.3 Σ = {0, 1, 2,..., 9,.} Σ L L def = {a Σ : a }. L

6 1 Σ 0 Σ. Σ Σ. Σ... Σ 1.3: L

7 2 2.1 2.1 Σ L Σ k x 1, x 2,..., x k L x 1 x 2 x k x 1 = x 2 = = x k = y L x 1 x 2 x k y k k = 0 y 0 ϵ 2.2 Σ L, L 1, L 2 Σ : L 1 L 2 def = {x : x L 1 x L 2 }, : L 1 L 2 def = {xy : x L 1 y L 2 }, : L def = {x 1 x 2... x k : k N {0} x 1, x 2,..., x k L}. 2.1 ( ). Σ = {0, 1, #} Σ L 1 = {0 n #1 n : n N {0}}, L 2 = {1 n #0 n : n N {0}}, L 1 L 2 = {0 n #1 n, 1 n #0 n : n N {0}}.

8 2 2.1. 1. L = L 2. ϵ L L {ϵ} L 2.2 ( ). Σ = {0, 1, #} Σ L 1 = {0, 1}, L 2 = {ϵ, #0, #1}, L 1 L 2 = {0, 1, 0#0, 0#1, 1#0, 1#1} L 2 L 1 = {0, 1, #00, #01, #10, #11} 2.2. 1. L {ϵ} = {ϵ} L = L 2. L = L = 2.3 ( ). Σ = {0, 1, #} L = {00#, 11#}, Σ L = {ϵ, 00#, 11#, 00#00#, 00#11#, 11#00#, 11#11#, 00#00#00#,... }. 2.3. Σ = {0, 1} L = {00, 11} L 000 L 010 101 111 2.1.,, L 1 L 2 L (L 1 L 2 ) (L ) (L 1 (L 2 L)) 2.3 Σ Σ L

2.1 9 1., {ϵ} 2. x Σ {x} 3. L, L 1, L 2 L 1 L 2, L 1 L 2, L Σ Σ,, 2.4 L REG 2.2. 2.4 ( ). Σ = {0, 1, #} 1. L = {0, 1} {0} {1} 2. L = {00, 11, 0#, 1#, 01#, 10#} {0} {0} {1} {1} {0} {#} {1} {#} {0} {1} {#} {1} {0} {#}. 3. L = {w Σ : w 1 } Σ {1} Σ. 2.1. Σ Σ L Σ Σ 2.4. 2.4 2 L 2.5 ( ). Σ = {0, 1}

10 2 {0} {1} {0} {w Σ : w } {0} {1} {0} {1} {0} {w Σ : w } Σ {010} Σ {w Σ : w 010 } Σ {010} {w Σ : w 010 } {0} Σ Σ {1} {w Σ : w 0 1 } 2.2. Σ = {0, 1} {0 n : n N} {1 n : n N} {0 i 1 j : i, j N} {0 n 1 n : n N}. {0 n : n N} {1 n : n N} {0 i 1 j : i, j N} 2.5. {0 n 1 n : n N} 3.7 2.6. Σ = {0, 1} 1. {0} Σ {0} {1} Σ {1}. 2. (Σ Σ). 3. {1} ({0} {1} {0} {1} ). 2.7. Σ = {0, 1} 1. {w Σ : w }. 2. {w Σ : w }. 3. {w Σ : w 0 }.

2.1 11 2.3. Σ = {0, 1} L = {w Σ : w 00 }. L {1} ({01} {1} ) {ϵ, 0} R R = L R L R L ( ) w R w L w 0 R {01} {1} {011 n : n N {0}} 2.8. A A = {011 n : n N {0}} w 0 y 1, y 2,..., y k A k N {0} w w = y 1 y 2... y k w = y 1 y 2... y k 0 2.9. w 00 A k k = 0 w = ϵ y 1 y 2... y k 1 y i A 00 y 1 y 2... y k 1 y k y i A w = y 1 y 2... y k 1 00 w ϵ 1 n N {0} y k = 011 n w = w y k 00 ( ) w L w R w 0 w y 1, y 2,..., y k k N {0} w = y 1 y 2... y k

12 2 2.10. w = 111011101010 i [k] i = 1 : y i {1} {01} {1} i [k] \ {1, k} : y i {01} {1} i = k : {01} {1} {ϵ, 0} 2.11. w = 111011101010 w = 010101110111 w R = {1} ({01} {1} ) {ϵ, 0} 2.12. Σ = {0, 1} L = {w Σ : w 000 } L Σ L Σ x Σ x L x L

2.1 13 1. Σ = {0, 1} a L = {w Σ : w 01 } b L = {w Σ : w 10 } c L = {w Σ : w 11 } d L = {w Σ : w 001 } e L = {w Σ : w 100 } 2. Σ = {0, 1} a L = {w Σ : w 0 1 } b L = {w Σ : w 00 11 } c L = {w Σ : w 000 111 } 3. Σ = {0, 1} a {ϵ, 1} {01} {ϵ, 0}. b {ϵ, 0} ({1} {1} {0}) {1}. c {ϵ, 0, 00} ({1} {1} {0, 00}) {1}.

15 3 3.1 DFA 3.1 DFA (Q, Σ, δ, q 0, F ) Q : Σ : δ : Q Σ Q q 0 : q 0 Q F : F Q Q, Σ, F 3.1 ( ). M 1 = (Q, Σ, δ, q 0, {q 1 }) Q = {q 0, q 1 }, Σ = {0, 1} δ : Q Σ Q 0 1 q 0 q 0 q 1 q 1 q 1 q 1 3.1.

16 3 0 0, 1 1 0 1 3.2 ( ). M 2 = (Q, Σ, δ, q 0, {q 2 }) Q = {q 0, q 1, q 2 }, Σ = {0, 1, a} δ : Q Σ Q 0 1 a q 0 q 0 q 0 q 1 q 1 q 1 q 1 q 2 q 2 q 2 q 2 q 2 0, 1 0, 1 0, 1, a a 0 1 a 2 3.2 M = (Q, Σ, δ, q 0, F ) w = w 1 w 2... w n Σ n w Σ n M w r 0, r 1,..., r n Q 1. r 0 = q 0 2. i [n][δ(r i 1, w i ) = r i ] 3. r n F M L(M) = {w Σ : M w } M L(M) L DFA L DFA = {L : DFA L }

3.1 DFA 17 3.3 ( ). 3.1 M 1 1, 01, 10, 11, 00100 L(M 1 ) 0, 00, 000, 00000 L(M 1 ) M 1 L 1 = L(M 1 ) L 1 = {w {0, 1} : w 1 }. 3.4 ( ). 3.2 M 2 aaa, 01a01a, a0a1a0a1a L(M 2 ) 0a1, 1a0, a01010 L(M 2 ) M 2 L 2 = L(M 2 ) L 2 = {w {0, 1, a} : w a }. 3.1. Σ = {0, 1} DFA 1. M = (Q, Σ, δ, q 0, {q 1 }). Q = {q 0, q 1, q 2 } δ : Q Σ Q 0 1 q 0 q 0 q 1 q 1 q 1 q 2 q 2 q 2 q 2 2. M = (Q, Σ, δ, q 0, {q 0 }). Q = {q 0, q 1 } δ : Q Σ Q 0 1 q 0 q 0 q 1 q 1 q 1 q 0 3. M = (Q, Σ, δ, q 0, {q 0 }). Q = {q 0, q 1, q 2 } δ : Q Σ Q 0 1 q 0 q 0 q 1 q 1 q 1 q 2 q 2 q 2 q 0

18 3 0 1 a 0 1 2 3 1, a 0, a 0, 1 0, 1, a 4 0, 1, a 3.5. Σ = {0, 1, a} L = {0, 01, 01a} M = (Q, Σ, δ, q 0, F ). Q = {q 0, q 1, q 2, q 3, q 4 }, Σ = {0, 1, a}, F = {q 1, q 2, q 3 } δ : Q Σ Q 0 1 a q 0 q 1 q 4 q 4 q 1 q 4 q 2 q 4 q 2 q 4 q 4 q 3 q 3 q 4 q 4 q 4 q 4 q 4 q 4 q 4 3.2. Σ = {0, 1} 1. L = {w Σ : w 010 }. 2. L = {w Σ : w 101 }. 3. L = {w Σ : w 010 }. 4. L = {w Σ : w 101 }. 5. L = {w Σ : w 1 0 }.

3.2 NFA 19 3.2 NFA 3.3 NFA (Q, Σ, δ, q 0, F ) Q : Σ : δ : Q Σ 2 Q q 0 : q 0 Q F : F Q Q, Σ, F 3.2. Q = {q 0, q 1, q 2 } 2 Q = {, {q 0 }, {q 1 }, {q 2 }, {q 0, q 1 }, {q 0, q 2 }, {q 1, q 2 }, {q 0, q 1, q 2 }} Q DFA 3.6 ( ). N = (Q, Σ, δ, q 0, {q 2 }) Q = {q 0, q 1, q 2 }, Σ = {0, 1} δ : Q Σ 2 Q 0 1 q 0 {q 0 } {q 0, q 1 } q 1 {q 2 } {q 2 } q 2 0, 1 1 0 1 0, 1 2

20 3 δ(q 2, 0), δ(q 2, 1) 3.3. 3.4 N = (Q, Σ, δ, q 0, F ) w = w 1 w 2... w n Σ n w Σ n N w r 0, r 1,..., r n Q 1. r 0 = q 0 2. i [n][r i δ(r i 1, w i )] 3. r n F N L(N) = {w Σ : N w } N L(N) L NFA L NFA = {L : NFA L } 3.3. 3.7 ( ). 3.6 N N L = L(N) 10, 11, 111, 00010 L(N) 0, 1, 00, 01, 101, 11101 L(N) L = {w Σ : w 1 }. 111 101 3.4. Σ = {0, 1} NFA 1. N = (Q, Σ, δ, q 0, {q 2 }) Q = {q 0, q 1, q 2 }, Σ = {0, 1} δ : Q Σ 2 Q

3.2 NFA 21 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 0 1 2 1 1 1 1 0 2 1 1 1 0 1 2 x 0 1 x (a) 111 (b) 101 3.1: 0 1 q 0 {q 1 } q 1 {q 1 } {q 1, q 2 } q 2 2. N = (Q, Σ, δ, q 0, {q 2 }) Q = {q 0, q 1, q 2 }, Σ = {0, 1} δ : Q Σ 2 Q 0 1 q 0 {q 1 } q 1 {q 1, q 2 } {q 1 } q 2 3.5. Σ = {0, 1} 1. L = {w Σ : w 010 }. 2. L = {w Σ : w 010 }.

22 3 3.6. 3.7 L DFA DFA DFA NFA 3.1. L NFA = L DFA 3.5 M = (Q, Σ, δ, q 0, F ) δ δ q Q s Σ δ (q, s) = { q s = ϵ δ(δ (q, t), c) s = tc (c Σ) N = (Q, Σ, δ, q 0, F ) δ δ q Q s Σ q s = ϵ δ (q, s) = δ(q, c) s = tc (c Σ) q δ (q,t) 3.8. 3.1 DFA M δ (q 0, 000) = q 0 δ (q 0, 010) = q 1 δ (q 1, 000) = q 1 3.9. 3.6 NFA N δ ({q 0 }, 010) = {q 0, q 2 } δ ({q 0, q 1 }, 010) = {q 0, q 2 } δ ({q 1, q 2 }, 010) =

3.2 NFA 23. L NFA L DFA L NFA L DFA L NFA L DFA 3.7. L NFA L DFA L NFA L DFA N = (Q, Σ, δ, q 0, F ) D = (Q D, Σ D, δ D, q D, F D ) N L(D) = L(N) N D Q D = 2 Q Σ D = Σ S Q D, a Σ δ D (S, a) = q S δ(q, a) q D = {q 0 } F D = {S Q D : S F } L(D) = L(N) x Σ δd (q D, x) = δ (q 0, x) 3.8. x x = 0 3.9. x Σ x 1 x = ya y Σ, a Σ δd(q D, x) = δd(q D, ya) = δ D (δd(q D, y), a) ( δd ) = δ D (δ (q 0, y), a) ( ) = δ(q, a) ( δ D ) q δ (q 0,y) = δ (q 0, ya) ( δ ) = δ (q 0, x).

24 3 3.10. 3.6 NFA N = (Q, Σ, δ, q 0, F ) DFA M = (Q D, Σ D, δ D, q D, F D ) Q D = {, {q 0 }, {q 1 }, {q 2 }, {q 0, q 1 }, {q 0, q 2 }, {q 1, q 2 }, {q 0, q 1, q 2 }} Σ D = Σ q D = {q 0 } F D = {{q 2 }, {q 0, q 2 }, {q 1, q 2 }, {q 0, q 1, q 2 }} δ D 0 1 {q 0 } {q 0 } {q 0, q 1 } {q 1 } {q 2 } {q 2 } {q 2 } {q 0, q 1 } {q 0, q 2 } {q 0, q 1, q 2 } {q 0, q 2 } {q 0 } {q 0, q 1 } {q 1, q 2 } {q 2 } {q 2 } {q 0, q 1, q 2 } {q 0, q 2 } {q 0, q 1, q 2 } 3.10. NFA DFA 1. L = {w00 : w {0, 1} } 2. L = {w11 : w {0, 1} } 3.3 ϵ- ϵ-nfa 3.6 Σ ϵ ϵ = 0 Σ ϵ = Σ {ϵ} 3.7 ϵ- ϵ-nfa

3.3 ϵ- ϵ-nfa 25 (Q, Σ, δ, q 0, F ) Q : Σ : δ : Q Σ ϵ 2 Q q 0 : q 0 Q F : F Q Q, Σ, F ϵ- L ϵ-nfa L ϵ-nfa = {L : NFA L } 3.11 (ϵ- ). ϵ- N = (Q, Σ, δ, q 0, {q 3, q 6 }) Q = {q 0, q 1, q 2, q 3, q 4, q 5, q 6 }, Σ = {0, 1} δ : Q Σ ϵ 2 Q ϵ 0 1 q 0 {q 1, q 4 } q 1 {q 1, q 2 } {q 1 } q 2 {q 3 } q 3 q 4 {q 4 } {q 4, q 5 } q 5 {q 6 } q 6 0, 1 ε 0 1 2 1 3 0 0, 1 ε 1 4 5 0 6

26 3 N L = L(N) L = {w Σ : w 01 10 } 3.4. δ(q 0, ϵ) = {q 1, q 4 } ϵ- ϵ- 3.11. L NFA NFA 3.12 (ϵ- ). Σ = {a, b, c} L = {a i b j c k Σ : i, j, k N {0}} L ϵ- N = (Q, Σ, δ, q 0, {q 0, q 1, q 2 }) Q = {q 0, q 1, q 2 } δ : Q Σ ϵ 2 Q a b c ε ε 0 1 2 3.12. L NFA NFA 3.2. L ϵ-nfa = L NFA 3.4 3.3. L REG = L DFA

3.4 27 L REG L DFA L REG L DFA 3.4 (L REG L DFA ). L Σ L. 3.1 3.2 L ϵ-nfa = L DFA L ϵ-nfa 2.3 ϵ-nfa 1. L = 2. L = {ϵ} 3. x Σ L = {x} 3.13. NFA DFA k N {0},, k L,, k + 1 1. L = L 1 L 2 L 1, L 2,, k L 1, L 2 NFA N 1, N 2 L NFA N N 1, N 2 3.2 2. L = L 1 L 2 L 1, L 2,, k L 1, L 2 NFA N 1, N 2 L NFA N N 1, N 2 3.3 3. L = L 0 L 0,, k L 0 NFA N 0 L NFA N N 0 3.4 3.14. NFA

28 3 N N 1 N 1 ε N 2 N 2 ε 3.2: L = L 1 L 2 N 1 N 2 N N ε 1 N 2 ε 3.3: L = L 1 L 2

3.4 29 N N 0 ε N 0 ε ε ε 3.4: L = L 0 L ϵ-nfa L DFA 3.5 (L REG L DFA ). M L M L. L 3.8 (Q, Σ, δ, q 0, F ) Q : Σ : δ : (Q \ {q accept }) (Q \ {q start }) R q start : q start Q q accept : q accept Q R Σ DFA M G 3.15. M G 3.1. G L

30 3. G L 3.5 GNFA G 1. G GNFA a q Q \ {q start, q accept } b G = (Q, Σ, δ, q start, q accept ) i. Q = Q \ {q} ii. q i Q \ {q, q accept }, q j Q \ {q, q start } δ (q i, q j ) def = R 1 R R 2 R 3. R = δ(q, q) R 1 = δ(q i, q) R 2 = δ(q, q j ) R 3 = δ(q i, q j ) 2. G q start q accept 3.5: 3.2. 3.5 1 GNFA G reg L(G) = L(G reg ). G k k = 2 k 1 GNFA k GNFA G 1 GNFA G 1-(a) q L(G) = L(G ) ( ) w L(G) w G q i1, q i2,..., q in G w q i1 = q start j [n 1] w j δ(q ij, q ij+1 ) w j Σ w G q {q i1, q i2,..., q in } G w

3.5 31 3.16. q {q i1, q i2,..., q in } q = q ij w j 1 δ(q ij 1, q ij ), w j δ(q ij, q ij+1 ) 1-(b)-(ii) δ w j 1 w j δ (q ij 1, q ij+1 ) w G ( ) w L(G ) w G q i1, q i2,..., q in G w q i1 = q start j [n 1] w j δ(q ij, q ij+1 ) w j Σ w G j [n 1] L(G) = L(G ) G k 1 L(G ) = L(G reg ) L(G) = L(G ) = L(G reg ) 3.5 3.6 ( ). L p p a L a a = xyz 1. i N {0}[xy i z L] 2. y > 0 3. xy p. L L M = (Q, Σ, δ, q 0, F ) p p = Q p a L *1 a = n p a L r 0, r 1,..., r n Q 1. r 0 = q 0 2. i [n][δ(r i 1, a i ) = r i ] 3. r n F 3.3. i, j [p] {0} i < j r i = r j *1

32 3. r 0, r 1,..., r p Q = p r i = r j i, j [p] i r i = r j j i < j a a = xyz x y z def = a 1 a i, def = a i+1 a j, def = a j+1 a p. i xy i z L z r n x a j +1 r j +1 a 1 a 2 a i -1 a i r 0 r 1 r r i-1 i a j a i +1 r i +1 r j -1 a i +2 a j -1 y r i+2 r j-2 r * 3.6: xy i z L 3.5. 3.13 ( ). L = {w {0, 1} : w } p p w L w w = xyz w = (01) p L w = xyz x = ϵ y = (01) 2 z = (01) p 2

3.5 33 w = 0 2p 1 2p L w = xyz x = ϵ y = 0 2 z = 0 2p 2 1 2p 3.7. L = {0 n 1 n : n N}. L p p w L w = 0 p 1 p w = xyz = 0 p 1 p xy p xy = 0 i, z = 0 j 1 p i + j = p y > 0 xyyz L L 3.17. xyyz L 3.18. 1. L = {ww : w {0, 1} } 2. L = {ww R : w {0, 1} } 3. L = {w {0, 1} : w = w R }

34 3 1. DFA NFA ϵ-nfa a L = {w {0, 1} : w 111 } b L = {w {0, 1} : w i=1 w i 2 0} c L = {w {0, 1, 2} : w i=1 w i 3 0} d {0} {0, 1} {1} e {0} {0, 1} {0, 1} {1} 2. a L = {0 i 1 j : i > j}. b L = {w {0, 1} : w 0 1 }. c L = {1 n2 : n N {0}}. 3. L 1, L 2, L a L 1 L 2 b L 1 L 2 c L

35 4 4.1 4.1 (V, Σ, R, S) V : Σ : R : S : S V V, Σ, R x V, y (V Σ) x y 4.1 ( ). G 1 = (V, Σ, R, S) V = {S} Σ = {0, 1} R S 0S1, S ϵ. 4.1. S 0S1 ϵ. 4.2 ( ). G 2 = (V, Σ, R, S) V =

36 4 {S, A, B} Σ = {0, 1} R S 0S1 0A 1B, A 0A ϵ, B 1B ϵ. 4.2 G = (V, Σ, R, S) u, v (V Σ) u v u G v G u v x, y, z (V Σ), A V 1. u = xay, 2. v = xzy, 3. (A z) R. w Σ w Σ G w u 0, u 1,..., u n (V Σ) S = u 0 u 1 u n 1 u n = w. S G w G S w 4.3 ( ). 4.1 G 1 S G1 0S1 0S1 G1 00S11 00S11 G1 000S111. 000111 S G1 000111 S 0S1 00S11 000S111 000111. 4.4 ( ). 4.2 G 2 00S11 G2 000S111 00S11 G2 000A11 00S11 G2 001B11. 00011 00011111 S G2 00011, S G2 00011111 00011 : S 0S1 00S11 000A11 00011 00011111 : S 0S1 00S11 000S111 0001B111 00011B111 00011111

4.1 37 4.1. 4.1 4.2 G 1, G 2 00111 000011 4.3 G = (V, Σ, R, S) G L(G) def = {w Σ : S w} G L(G) Σ L Σ G = (V, Σ, R, S) L = L(G) L L CFG 4.5 ( ). 4.1 G 1 L(G 1 ) = {0 n 1 n : n N {0}}. 4.6 ( ). 4.2 G 2 L(G 2 ) = {0 i 1 j : i, j N {0}, i j}. 4.1. L REG L CFG. L REG L CFG L REG L CFG 5.4 L DFA L PDA?? L(G 1 ) L(G 2 ) L REG L CFG 4.7 ( ). Σ = {0, 1} L = {w Σ : w 0 1 } G = (V, Σ, R, S) V = {S, A} R S 0A A1, A 0A 1A ϵ. 4.2. Σ = {0, 1} 1. L 1 = {w Σ : w 010 }

38 4 2. L 2 = {w Σ : w 010 } 3. L 3 = {w Σ : w 1 } 4.8 ( ). G = (V, Σ, R, S) V = {S} Σ = {(, ), } R S SS (S) G 4.3. G 1. (( ) ) 2. ( )(( )( )) 4.9 ( ). G = (V, Σ, R, < exp >) V = {< exp >, < term >, < fact >} Σ = {+,,, /, (, )} R R < exp > < term > + < exp > < term > < exp > < term >, < term > < fact > < term > < fact > / < term > < fact >, < fact > (< exp >) a. G a 1 (2 3) < exp > < term > < exp > < fact > < term > 1 < fact > 1 (< exp >) 1 (< term > < exp >) 1 (< fact > < term >) 1 (2 < fact >) 1 (2 3) (1 (2 3)) ( 1) 2 3/5 < exp > < term > < exp > < fact > < term > < fact > < term >

4.1 39 (< exp >) < fact > 2 < term > (1 (2 3)) (< exp >) 2 < fact > / < term > (1 (2 3)) (< term >) 2 3/ < fact > (1 (2 3)) (< fact >) 2 3/5 (1 (2 3)) ( 1) 2 3/5 4.4. 1. 1 2 3 2. (1 2) (2 3)/(3 1) 3. 1 + 1/(1 + 1/(1 + 1/2)) 4.5. Σ = {0, 1} G i = (V i, Σ, R i, S) 1. V 1 = {S, A}, R 1 = {S A1A, A A0 ϵ}. 2. V 2 = {S}, R 2 = {S 0S0 1S1 ϵ}. 3. V 3 = {S}, R 3 = {S 0S0 1S1 0 1 ϵ}. 4.2. Σ = {0, 1} {ww R : w {0, 1} }, {w Σ : w = w R } {ww : w {0, 1} }. {ww R : w {0, 1} }, {w Σ : w = w R } {ww : w {0, 1} } 5.8 4.6. Σ = {0, 1} 1. L 1 = {w Σ : w 1 }. 2. L 2 = {w Σ : w 00 }. 3. L 3 = {w Σ : w 1 }.

40 4 4. L 4 = {0 i 1 j : i > j}. 5. L 5 = {w {0, 1} : w 0 1 }. 4.3. Σ = {0, 1} L = Σ \ {0 n 1 n : n N {0}}. L G = (V, Σ, R, S) R L(G) = L S XA B A XXA ϵ X 1 0 B 0B1 Y Y 0Z0 1Z0 1Z1 Z 0Z 1Z ϵ ( ) w L(G) w L S XA w i N S XA XXXA X i A X i X w L S B w i N {0} S B 0B1 00B11 0 i B1 i 0 i Y 1 i 1. 0 i Y 1 i 0 i 0Z01 i 2. 0 i Y 1 i 0 i 1Z01 i 3. 0 i Y 1 i 0 i 1Z11 i Z w L

4.2 41 ( ) w L w L(G) w ( ) w S XA w w L w {0 n 1 n : n N {0}} w i N {0} x Σ 1. 0 i 0x01 i 2. 0 i 1x01 i 3. 0 i 1x11 i ( ) w S B 4.2 4.4 G = (V, Σ, R, S) T G 1. T 2. T 3. T S 4. T v v 1,..., v k v v A v 1,..., v k A 1,..., A k A A 1... A k 4.2. 4.5 G = (V, Σ, R, S) w (V Σ) T w 1. T G 2. T w 4.10. 4.9 a (a) 1 (2 3) (b) (1 (2 3)) ( 1) 2 3/5 (b) (a) (a)

42 4 exp term - exp exp fact term term - exp 1 fact fact * term term ( exp ) ( ) fact fact * term term - exp ( exp ) 2 fact / term fact term term 3 fact 2 fact (a) fact 5 3-1 (a) 1 (2 3) (b) (1 (2 3)) ( 1) 2 3/5 4.1: 4.7. 1. 1 2 3 2. (1 2) (2 3)/(3 1) 3. 1 + 1/(1 + 1/(1 + 1/2)) 4.3 4.6 G = (V, Σ, R, S) R G A BC A a A B, C a

4.3 43 4.4 ( ). L Σ L Σ x Σ x L x L

44 4 1. G = (V, Σ, R, S) V = {S, A, B}, Σ = {0, 1}, S AB BA A 0A0 0A1 1A0 1A1 0 B 0B0 0B1 1B0 1B1 1 2. a L 1 = {0 i 1 j : i > 2j}. b L 2 = {0 i 1 i 2 j : i, j N {0}}. c L 3 = {0 i 1 j 2 i : i, j N {0}}.

45 5 *1 5.1 5.1 PDA (Q, Σ ϵ, Γ ϵ, δ, q 0, F ) Q : Σ ϵ : Γ ϵ : δ : Q Σ ϵ Γ ϵ 2 Q Γ ϵ q 0 : q 0 Q F : F Q Q, Σ ϵ, Γ ϵ, F Γ ϵ $ PDA NFA *1 {ww R : w {0, 1} }

46 5 5.1 ( ). N 1 = (Q, Σ ϵ, Γ ϵ, δ, q 0, {q 0, q 3 }) Q = {q 0, q 1, q 2, q 3 }, Σ = {0, 1}, Γ = {0, $} δ : Q Σ ϵ Γ ϵ 2 Q Γ ϵ ϕ Σ ϵ 0 1 ϵ Γ ϵ 0 $ ϵ 0 $ ϵ 0 $ ϵ q 0 (q 1, $) q 1 (q 1, 0) (q 2, ϵ) q 2 (q 2, ϵ) (q 3, ϵ) q 3 ϕ 0, ε 0 1, 0 ε ε, ε $ 1, 0 ε ε, $ ε 0 1 2 3 5.1. δ δ(q i, y, a) = (q j, b) y Σ ϵ, a, b Γ ϵ y, a b 5.2 ( ). N 2 = (Q, Σ ϵ, Γ ϵ, δ, q 0, {q 3, q 4, q 5, q 6 }) Q = {q 0, q 1, q 2,..., q 6 }, Σ = {0, 1}, Γ = {0, $} δ : Q Σ ϵ Γ ϵ 2 Q Γ ϵ 5.2 N = (Q, Σ ϵ, Γ ϵ, δ, q 0, F ) w = w 1 w 2... w n Σ n w Σ n N w w = y 1 y m y i Σ ϵ r 0, r 1,..., r m Q s 0, s 1,..., s m Γ 1. r 0 = q 0, s 0 = ϵ, s 1 = $

5.1 47 0, ε 0 1, 0 ε ε, 0 ε 3 ε, ε $ 1, 0 ε 0 1 2 0, ε ε 1, ε ε 1, $ $ 4 5 6 1, $ $ 0, ε ε 1, ε ε 2. i [m], a, b Γ ϵ, t Γ 3. r m F 1. (r i, b) δ(r i 1, y i, a) 2. s i 1 = at 3. s i = bt N L(N) = {w Σ : N w } N L(N) L PDA L PDA = {L : PDA L }. 5.2. NFA 5.3. δ δ(q i, y, a) = (q j, b) y Σ ϵ, a, b Γ ϵ a b a pop b push *2 a = ϵ : b push b = ϵ : a pop 5.3 ( ). 5.1 N 1 ϵ, 01, 0011, 000111 L(N 1 ) 0, 1, 000, 111, 0101, 1001, 00111 L(N 1 ) *2 Γ ϵ

48 5 N 1 L 1 = L(N 1 ) L 1 = {0 n 1 n : n N {0}}. 5.4 ( ). 5.2 N 2 0, 1, 000, 111, 00011, 00111 L(N 2 ) ϵ, 01, 0011, 000111, 0101, 1001 L(N 2 ) N 2 L 2 = L(N 2 ) L 2 = {0 i 1 j : i, j N {0}, i j}. 5.1. L DFA L PDA.. L DFA L PDA DFA PDA DFA PDA L = {0 n 1 n : n N {0}} L L PDA 5.1, 5.3 L L DFA L L DFA L PDA 5.1. Σ = {0, 1} PDA 1. N 1 = (Q, Σ ϵ, Γ ϵ, δ, q 0, {q 0, q 3 }) Σ ϵ 0 1 ϵ Γ ϵ 0 1 $ ϵ 0 1 $ ϵ 0 1 $ ϵ q 0 (q 1, $) q 1 (q 1, 0) (q 1, 1) (q 2, ϵ) q 2 (q 2, ϵ) (q 2, ϵ) (q 3, ϵ) q 3 2. N 2 = (Q, Σ ϵ, Γ ϵ, δ, q 0, {q 0, q 3 }) Σ ϵ 0 1 Γ ϵ 0 1 $ ϵ 0 1 $ ϵ q 0 q 1 (q 1, 0), (q 2, ϵ) (q 1, 1), (q 2, ϵ) q 2 (q 2, ϵ) (q 2, ϵ) q 3

5.1 49 Σ ϵ ϵ Γ ϵ 0 1 $ ϵ q 0 (q 1, $) q 1 (q 2, ϵ) q 2 (q 3, ϵ) q 3 5.2. Σ = {0, 1} 1. L 1 = {w Σ : w 1 }. 2. L 2 = {w Σ : w 1 }. 3. L 3 = {0 i 1 j : i > j}. 4. L 4 = {0 i 1 j : i < j}. 5. L 5 = {w {0, 1} : w 0 1 }. 5.2. PDA δ : Q Σ ϵ Γ ϵ 2 Q Γ ϵ δ(q,, ϵ) = {(q, ) : q Q } δ(q,, a) = {(q, ϵ) : q Q } PDA 5.3. PDA δ : Q Σ ϵ Γ ϵ 2 Q Γ ϵ δ : Q Σ ϵ Γ ϵ 2 Q Γ ϵ PDA

50 5 5.2 5.4. L CFG = L PDA. L CFG L PDA L CFG L PDA 5.5 (L CFG L PDA ). L L. L G = (V, Σ, R, S) L = L(G) G P = (Q, Σ ϵ, Γ ϵ, δ, q 0, F ) Q = {q 0, q loop, q 1 }, Γ = V Σ, F = {q 1 } 5.3 δ : Q Σ ϵ Γ ϵ 2 Q Γ ϵ δ(q 0, ϵ, ϵ) = {(q loop, S)} A B A V Γ, B Γ ϵ δ(q loop, ϵ, A) = {(q loop, B)} a δ(q loop, a, a) = {(q loop, ϵ)} δ(q loop, ϵ, $) = {(q 1, ϵ)} 5.1. L = L(P ). L L(P ) L L(P ) PDA P P L 5.5. 4.1 CFG PDA P L = L(P ) = {0 n 1 n : n N {0}} ε, S 0S1 ε, S ε 0, 0 ε 1, 1 ε ε, ε S ε, $ ε 0 loop 1

5.3 51 5.3. 4.2 CFG PDA 5.6 (L CFG L PDA ). P = (Q, Σ ϵ, Γ ϵ, δ, q 0, F ) L P L. 5.2 P P F = 1 P G = (V, Σ, R, S) V = {A pq : p, q Q} {S} R S A q0 q accept x Γ (s, x) δ(p, a, ϵ) (t, ϵ) δ(q, b, x) p, q, s, t Q, a, b Σ A pq aa st b A pq A pr A rq A pp ϵ 5.2. L = L(G). L L(G) L L(G) G L 5.3 5.7 ( ). L p p w L w w = axyzb 1. i N {0}[ax i yz i b L] 2. xz > 0 3. xyz p

52 5. L G = (V, Σ, R, S) L = L(G) 4.4 G p = 2 V +1 p w L w T 5.3. T 5.4. 5.4. T V + 1 5.5. w T P P V + 2 5.5. A V P A. P V V + 1 A V P A P v V +1, v V,..., v 1, v 0 a, A V,..., A 1, A 0 v 0 A A i = A j = A i > j v i v j v i T T i v j T T j 5.6. T i V + 1 5.6. w = axyzb 1 v i v j v i y v i v j ayb ayb L v i v j

5.3 53 v i v j a x y z b 5.1: v i = v j y a b 5.2: v j xyz v j v i T i ax 2 yz 2 b ax 2 yz 2 b L ax i yz i b L 1 2 xz = 0 x = z = ϵ v i = v j v i v j xz > 0 3 5.6 T i V +1

54 5 v i v i a x v j z b x y z 5.3: xyz 2 V +1 = p 5.6 ( ). L = {ww R : w {0, 1} } 4.2 p p w L w w = axyzb w = 0 p 1 p 1 p 0 p L w = axyzb a = 0 p 1 p 2 x = 1 p 2 y = ϵ z = 1 p 2 b = 1 p 2 0 p 5.8. {ww : w Σ }. L p p w L w = 0 p 1 p 0 p 1 p w = axyzb = 0 p 1 p 0 p 1 p xyz p xyz

5.3 55 xyz = 0 i i p 1 i j p 0 i 1 j i + j p 1 i 0 j i + j p axxyzzb L L 5.7. axxyzzb L 5.8. L = {0 n 1 n 2 n : n N {0}}

56 5 1. a L = Σ \ {0 n 1 n : n N {0}} b 4.8 c 4.9 2. a L = {0 i 1 j 2 k : 0 i j k}. b L = {0 n2 : n N {0}}. 3. L 1, L 2, L a L 1 L 2 b L 1 L 2 c L

57 1. Σ abcabca abcdef 2. Σ Σ 3. Σ k Σ k n k 4. Σ Σ 1 ϵ Σ Σ ϵ Σ 5. a ϵ Σ 0 Σ b 0 = {ϵ}, k N[ k = ] 1. a b ϵ 2. a w L wϵ = ϵw = w b xy L x L y y 3. L = {ϵ, 00, 11, 0000, 0011, 1100, 1111, 000000,... } Σ = {00, 11} L = Σ 4. Σ 5. {0 n : n N} {0} {0} {1 n : n N} {1} {1} {0 i 1 j : i, j N} {0} {0} {1} {1} 6. a {w Σ : w }. b {w Σ : w }.

58 c {w Σ : w 0 }. 7. a {0} Σ {1} {1} Σ {0}. b Σ (Σ Σ). c {1} {0} {1} ({0} {1} {0} {1} ). 8. {1} {1 n : n N {0}} {01} {1 n : n N {0}} {011 n : n N {0}} 9. A 0 10. 11. 12. {1} ({01, 001} {1} ) {ϵ, 0, 00} 1. a {1} {0} b {0} {1} c {0} ({10} {0} ) {ϵ, 1} d {1} ({01} {1} ) {0} e 2. a b {ϵ, 1} {01} {ϵ, 0} c {ϵ, 1, 11} ({0, 00} {1, 11}) {ϵ, 0, 00} 3. a {w Σ : w 0 1 }. b {w Σ : w 00 }. c {w Σ : w 000 }. 1. a {w Σ : w 1 } b {w Σ : w 1 } c {w Σ : w 1 } 2. a 010

59 1 0 0, 1 0 0 1 1 2 0 3 1 b c 010 1 0 0 0 0 1 1 2 0 3 1 1 d e 0 0 1 1 1 2 0 3 3. δ(q 0, 1) = {q 0, q 1 } 4. a {w Σ : w 0 1 } b {w Σ : w 1 0 } 5. a 010 0, 1 0, 1 0 0 1 1 2 0 3 b 010

60 0, 1 0 0 1 1 2 0 3 6. 0 1 1 0 1 1 2 1 0 0 0 3 7. DFA NFA 8. N x δ (q 0, x) F D x δd (q D, x) F D F D δ (q 0, x) = δd (q D, x) N D 9. x = 0 x = ϵ δd (q D, x) = δ (q 0, x) = {q 0 } 10. a b 11. 0, 1 1 1 2 0 0 1 0 3 4 12.

61 a b c b c 0 1 2 c 13. a L = Σ b L = ϵ Σ Σ c L = {x} Σ x Σ 14. i = 0, 1, 2 N i = (Q i, Σ, δ i, p i, F i ) N = (Q, Σ, δ, q 0, F ) δ δ i a δ(q 0, ϵ) = {q 1, q 2 } b q F 1 δ(q, ϵ) = {p 2 } c δ(q 0, ϵ) = {p 0 } q F 0 δ(q, ϵ) = {p 0 } 15. M q 0 F G q start q accept δ(q start, q 0 ) = {ϵ} q F δ(q, q accept ) = {ϵ} δ(q, a) = q δ(q, q ) = {a} q, q q q accept, q q start δ(q, q ) =

62 16. G w G 17. xyyz = 0 k 1 p k > p 18. a 1 p 0 p 1 p 0 p L 1 p 0 p 1 p 0 p = xyz xy p xy = 1 i, z = 1 j 0 p 1 p 0 p xyyz L b 1 p 0 p 0 p 1 p L 1 p 0 p 0 p 1 p = xyz xy p xy = 1 i, z = 1 j 0 p 0 p 1 p xyyz L c 0 p 10 p L 0 p 10 p = xyz xy p xy = 0 i, z = 0 j 10 p xyyz L 1. 2. 3. L 1, L 2, L M 1, M 2, M R 1, R 2 L 1, L 2 a R 1 R 2 L 1 L 2 M 1 M 2 L 1 L 2 b L 1 L 2 = L 1 L 2 R 1 R 2 L c L 1. G 1 G 2 S 0S1 00S11 001B11 00111 S 0S1 00S11 000A11 0000A11 000011 2. a V 1 = {S, A}, R 1 = {S A010A, A A0 A1 ϵ}. b V 2 = {S, A}, R 2 = {S A010, A A0 A1 ϵ}. c V 3 = {S, A}, R 3 = {S A1A, A A0 A1 ϵ}. 3. a S (S) (SS) ((S) ) (( ) ) b S SS (S)(S) ( )(SS) ( )((S)(S)) ( )(( )( )) 4. a < exp > < term > < exp >

63 < fact > < term > < exp > 1 < fact > < term > 1 2 < fact > 1 2 3 b c < exp > < term > < fact > < term > (< exp >) < fact > / < term > (< term > < exp >) (< exp >)/ < fact > (< fact > < term >) (< term > < exp >)/(< exp >) (1 < fact >) (< fact > < term >)/(< term > < exp >) (1 2) (2 < fact >)/(< fact > < term >) (1 2) (2 3)/(3 < fact >) (1 2) (2 3)/(3 1) < exp > < term > + < exp > < fact > + < term > 1+ < fact > / < term > 1 + 1/ < fact > 1 + 1/(< exp >) 1 + 1/(1 + 1/(< exp >)) 1 + 1/(1 + 1/(< term > + < exp >)) 1 + 1/(1 + 1/(< fact > + < term >)) 1 + 1/(1 + 1/(1+ < fact > / < term >)) 1 + 1/(1 + 1/(1 + 1/ < fact >)) 1 + 1/(1 + 1/(1 + 1/2)) 5. a L 1 = {w Σ : w 1 } b L 2 = {ww R : w {0, 1} } c L 3 = {w {0, 1} : w = w R } 6. a V 1 = {S, A}, R 1 = {S A1A1A, A A0 ϵ}. b V 2 = {S, A}, R 2 = {S 1S 0A ϵ, A 1S ϵ}. c V 3 = {S, A}, R 3 = {S ASA 1, A 0 1}. d V 4 = {S, A}, R 4 = {S 0S1 0A, A 0A ϵ}. e V 5 = {S}, R 5 = {S 0S1S 1S0S ϵ}. ( )

64 7. 1. L(G) = {xy Σ : x = y x y}. 2. a V 1 = {S, A}, R 1 = {S 00S1 0A, A 0A ϵ}. b V 2 = {S, A, B}, R 2 = {S AB, A 0A1 ϵ, B 2 ϵ}. c V 3 = {S, A}, R 3 = {S 0S2 A, A 1A ϵ}. 1. a L 1 = {ww R : w Σ }. b L 2 = {w Σ : w = w R }. 2. a b 0, ε # 0, # ε 1, ε # 1, # ε ε, ε $ 1, ε ε ε, $ ε 0 1 2 3 c 0, ε 0 1, 0 ε ε, ε $ 1, 0 ε ε, 0 ε 0 1 2 3 0, ε ε 4 0, ε ε d

65 0, ε 0 1, 0 ε 1, $ $ ε, ε $ 1, 0 ε 0 1 2 1, $ $ 3 1, ε ε 4 1, ε ε e 0, ε 0 1, 0 ε 0, ε 0 2 ε, $ ε 1, $ $ ε, ε 0 0 ε, ε $ 1 4 5 6 ε, ε 1 0, $ $ 1, ε 1 3 ε, $ ε 1, ε 1 0, 1 ε 0, ε 0 0, 1 ε 1, ε 1 1, 0 ε 0 ε, ε $ 1 ε, $ ε 2

66 3. ε, S 0S1 ε, S 0A ε, S 1B 0, 0 ε 1, 1 ε ε, ε S ε, $ ε 0 loop 1 ε, A 0A ε, B 1B ε, A ε, B ε ε 4. A BC A a 5. w p w p l 2 l p = 2 V +1 l V + 1 6. v i, v i+1,..., v V +1 T i 7. xyz = 0 i i p xz > 0 n > p axxyzzb = 0 n 1 p 0 p 1 p L 8. p w L w = 0 p 1 p 2 p 1. a b c 2. a p w L w = 0 p 1 p 2 p b p w L w = 0 p2 w = axyzb xyz p ax 2 yz 2 b p 2 + 2p < (p + 1) 2 3. a L 1 S 1 L 2 S 2 S S 1 S 2 b L 1 = {0 i 1 j 2 j : i, j N {0}}, L 2 = {0 j 1 j 2 i : i, j N {0}} L 1, L 2 *3 L 1 L 2 = {0 n 1 n 2 n : n N} c L 1 = {0 i 1 j 2 j : i, j N {0}}, L 2 = {0 j 1 j 2 i : i, j N {0}} *3

67 L 1, L 2 L = L 1 L 2 L L = L 1 L 2

69 1. 1. Introduction to the Theory of Computation, Michael Sipser, Cengage Learning, 2005. 2. 3. J. R. J.

70, 1, 29 ϵ-, 24, 3, 1, 15, 2, 16, 20, 46, 7, 8, 9, 37, 8, 9, 26, 42, 41, 36, 1, 16, 20, 47, 45, 19, 37, 35, 1, 15, 3

2024 © docsplayer.net プライバシー | 利用規約 | フィードバック