_auto

Transcription

1 0 0 pdf pdf Turing mchine

2 . set 0 element, member A A A finite set infinite set A A A A crdinlity A A {} {,,, } {,,, } x P (x) {x P (x)} P (x) x A Q(x) {x x A Q(x)} {x A Q(x)} N { N b =b } A B A B A B B A B A) A B A B subset A B A A

3 A B A B B A A B proper subset A B A B A B A B A B A B = {x x A x B}. A B = {x x A x B}. A B = {x x A x/ B}. 0 A B = {(x, y) x A y B}. A = {B B A}. A B A B A B A B A B A A = {,, } B = {, } A B = {(, ), (, ), (, ), (, ), (, ), (, )} A B b (, b) A B A m B n A B m n A B = A B

4 v v v v.: m = n = A B m n = = A = {,, } A = {, {}, {}, {}, {, }, {, }, {, }, {,, }} A A A A A A A m A m A = A A A = A = = B = B = { } C = {} C C = {, {}}. grph G vertex, node V edge, rc E e v, v ( ) v v v e strt vertex v e end vertex v v predecessor v v successor G = (V,E ) V = {v,v,v,v } E = {v v,v v,v v, v v } 0. B B = {, { }} B B = {, { }, {{ }}, {, { }}}

5 E E + E id E * E id id.: G = (V,E) v v E v v E undirected grph directed grph G =(V,E) v v, v v,...,v k v k G v v k 0 pth v = v k closed pth, cyclic pth L v V l L f f(v) v lbel e E l L g g(e) v lbel lbelled grph

6 tree 0. root.. prent child, children ncestorr descendnt lef internl vertex. E,+,,id E + E +EE EE+.... E E 0. D D domin D codomin, rnge D function D D D D type f D D f : D D lbeled tree structure. rnge codomin codomin rnge

7 f D D type C D f(d ); D D D D D D f C D f(d, D ); D D D D D D D C C return C D D D D C C bit D

8 . / / 0 symbol / / symbol string 0 string lphbet Σ Σ={, b, c} bbc bbbccc Σ Σ u u length bbc = bbbccc = 0 empty string ε ε =0 0 u v uv u v conctention u = m v = n uv = m + n bbb bbb

9 ε u uε = εu = u 0 x +0=0+x = x, x = x = x n } {{ } n 0 n u n uuu } uuu {{ } u n n u 0 = ε u n = uu n (u) n u v w u = vw v u prefix w u postfix bbc ε b b bb bbc proper 0 bbc bbbccc bbc= bbc. Σ Σ forml lnguge lnguge : L = {@ n+ n 0} @@@@@@@, } ()

10 @ : L = {@ n n } @@@@@@@, } Σ ={0,,,,, } 0 L = {n n 0 } = {,,,,,, } 0 {ε} {ε} u L membership L Σ Σ Σ Σ Σ Σ Σ Σ 0 / 0

11 H F R.: () 00 (b) 0 (c) (d) (e)

12 . 0 H F R... H F R HFRHHF H 00 F 0 R H 00 H 00 F 0 0 HHFFRF H 00 H 00 F 0 F 0 R F 0

13 0 HFRHHF 00 0 u v w. u H F R 0. v H FF. w H F... u R u u v w w u v w uvw L J L J = {uvw u {H, F, R},v {H, FF}, w {H, F} }

14 L J = {uvw u {H, F, R},v {H, FF}, w {H, F} } (H F R) (H FF)(H F) 0. L L conctention L L L L = {xy x L,y L } {b, bb} {, ccc} {b, bb}{, ccc} = {b, bccc, bb, bbccc}

15 {ε} L L = L =, {ε}l = L{ε} = L L L n L n L } L {{ } n L 0 = {ε}, L n = LL n (n ) L L L Kleenen closure L = L i = L 0 L L L... = {ε} L LL LLL... i=0 L L L L Σ Σ Σ n... n i Σ... n Σ n Σ n Σ... n Σ Σ Σ 0. Σ regulr expression r r lnguge L(r) L(r). Σ L() ={}. regulr expression

16 . ε L(ε) ={ε} ε. L( ) =. r r (r) L((r)) = L(r) (). r r r r L(r r ) = L(r )L(r ) r ε L(r r ) = L(ε)L(r ) = {ε}l(r )=L(r ) r ε L(r r )=L(r )L(ε) =L(r ){ε} = L(r ) 0. r r r r L(r r )=L(r ) L(r ) L(r r ) L(r ) L(r ) r r r r. r r L(r )=L (r) L(r ) L(r) r r 0. r r + L(r + )=L(r)L (r) r + r () > > + > > Σ={H, F, R} (H F R) (H FF)(H F) L((H F R) (H FF)(H F) )={H, F, R} {H, FF}{H, F} 0 (H F R) H FF(H F) H F R (H FF)(H F) H F R H FFH F

17 . Σ ={, b} : ( b) Σ L(( b) )=L( b) = {, b} =Σ : ε L(ε) ={ε} 0 : L( ) = r r r L(r ) =L( r) = L(ε) L( ) ε L(ε) L( ) : L() ={} : b 0 b L(b) ={}{b}{} = {b} L(r ) =L(r)L( ) =L(r) = L( r)

18 : ε b ( b)( b) + Σ {} L() {}. r L(r )=Σ L(r) r : 0 L( )={ i i 0} { i i } + { i i } + + : b b L( b )=L( ) L(b )={ i i 0} {b i i 0} : (b) b (b) n = bb...b L((b) )= {(b) n n 0} = {ε, b, bb, bbb,...} 0 0: (b b ) b b 0 ε bbb b bb... () b () b 0 b

19 : ( b) ( b) L(( b) ) ={u u {, b} } : 0 { n b n n 0} b b N { n b n N n 0} ε b bb bbb... N b N N b { n b n n 0} b { m b n m, n 0} m n L( b ) { n b n n 0} 0 : 0 ( )(0 ) Σ={0,,,,,,,,, } N N = N

20 :(0 ) +.(0 ) (0 ).(0 ) + Σ={0,,.} :(+ ε)((0 ) +.(0 ) (0 ).(0 ) + ) Σ={0,,.,+, } r r L(r )=L(r ) r r equivlent r r r r r r L(r r )= L(r ) L(r )=L(r ) L(r )=L(r r ) 0 Σ={, b} () b b () ε () ε () b b () () () ( b) ( b ). r =(0 ) +.(0 ) (0 ).(0 ) L(r )

21 : : ε- : : : C.: 0.

22 ε- ε- ε- ε- C C r L(r) C. ε- ε- regulr lnguge

23 C

24 0 0. deterministic finite stte utomton / n n / n n n = n ( n) ( n)..

25 R q 0 R H q F H,F R q H,F.: 0 stte trnsition grph stte trnsition digrm. q 0 q q stte H F R q finl stte. initil stte. q 0 HFRFHF HFRFHF q 0 H q F q R q F 0 q H q F q 0 q 0 ccepted q q HFRFHF rejected FFRFHRF

26 q 0 F q F q R q F 0 q H q R q F 0 q q q FFRFHRF. L J. L J. L J M (Q, Σ,δ,q 0,F) Q Σ δ δ : Q Σ Q trnsition function q 0 Q F Q δ ˆδ : Q Σ Q ˆδ(q, ε) = q, ˆδ(q, u) = ˆδ(δ(q, ),u) Σ u Σ δ ˆδ u Σ ˆδ(q 0,u) F q 0 u ˆδ(q 0,u) u M M L(M) M

27 L(M) ={u Σ ˆδ(q 0,u) F }. M J M J =(Q J, Σ,δ J,q 0,F J ) Q J Σ δ J F J Q J = {q 0,q,q }, Σ={H, F, R}, δ J (q 0, H) = q, δ J (q 0, F) = q, δ J (q 0, R) = q 0, δ J (q, H) = q, δ J (q, F) = q, δ J (q, R) = q 0, δ J (q, H) = q, δ J (q, F) = q, δ J (q, R) = q 0, F J = {q }. Q J Σ F J M J =({q 0,q,q }, {H, F, R},δ J,q 0, {q }) M J L(M J )={u {H, F, R} ˆδ J (q 0,u) {q }} HRHF ˆδ J (q 0, HRHF) ˆδ J (q 0, HRHF) = ˆδ J (δ J (q 0, H), RHF) = ˆδ J (q, RHF) = ˆδ J (δ J (q, R), HF) = ˆδ J (q 0, HF) = ˆδ J (δ J (q 0, H), F) = ˆδ J (q, F) = ˆδ J (δ J (q, F),ε) ( F=Fε) = ˆδ J (q,ε) = q ˆδ J (q 0, HRHF) {q } = F J HRHF

28 q 0 q,b 0 q,b q 0,b,b () () () q 0 q q 0 q b,b b,b () q,b () q,b q 0 b q b b q,b q q,b ().:. Σ={, b}. : L(( b) )=L(M )=Σ 0 Σ = {, b} = {ε,, b,, b, b, bb,,...} Σ M. () M = ({q 0 }, Σ,δ,q 0, {q 0 }) δ (q 0,)=q 0, δ (q 0,b)=q 0.

29 q 0 : L(ε) =L(M )={ε} 0 M. () M =({q 0,q }, Σ,δ,q 0, {q 0 }) δ (q 0,)=q, δ (q 0,b)=q, δ (q,)=q, δ (q,b)=q. q q q q q q ded stte : L( ) =L(M )= M. () M =({q 0 }, Σ,δ,q 0, ) δ (q 0,)=q 0, δ (q 0,b)=q 0. 0 q 0 : L() =L(M )={} M. () M =({q 0,q,q }, Σ,δ,q 0, {q }) δ (q 0,)=q, δ (q 0,b)=q, δ (q,)=q, δ (q,b)=q, δ (q,)=q, δ (q,b)=q. q

30 : L(b) =L(M )={b} b M. () M =({q 0,q,q,q,q }, Σ,δ,q 0, {q }) δ (q 0,)=q, δ (q 0,b)=q, δ (q,)=q, δ (q,b)=q, δ (q,)=q, δ (q,b)=q, δ (q,)=q, δ (q,b)=q, δ (q,)=q, δ (q,b)=q. q : L(ε b ( b)( b) + )=L(M )=Σ {} 0 0 L(M ) Σ {} M. () M =({q 0,q,q }, Σ,δ,q 0, {q 0,q }) δ (q 0,)=q, δ (q 0,b)=q, δ (q,)=q, δ (q,b)=q, δ (q,)=q, δ (q,b)=q. M M M M M M M M L(M) M M. Σ L() ε b ( b)( b) + {, b} 0

31 ,b q b 0 q () b b q 0 q q () q b,b q 0 q b b () q,b b q 0 q b b q 0 q b b q (0) ().: : L( )=L(M )={ n n 0} 0 M. () M =({q 0,q }, Σ,δ,q 0, {q 0 }) δ (q 0,)=q 0, δ (q 0,b)=q, δ (q,)=q, δ (q,b)=q. n n. () q 0 q 0 q { n n } ε 0 : L( b )=L(M )={ n n 0} {b n n 0} 0 0 b M. () M =({q 0,q,q,q }, Σ,δ,q 0, {q 0,q,q }) δ (q 0,)=q, δ (q 0,b)=q, δ (q,)=q, δ (q,b)=q, δ (q,)=q, δ (q,b)=q, δ (q,)=q, δ (q,b)=q.

32 q q n b n n q 0 q : L((b) )=L(M )={(b) n n 0} b M. () M =({q 0,q,q }, Σ,δ,q 0, {q 0 }) δ (q 0,)=q, δ (q 0,b)=q, δ (q,)=q, δ (q,b)=q 0, δ (q,)=q, δ (q,b)=q q 0 q q 0 (b) n n 0 0: L((b b ) b )=L(M 0 )={u Σ u } 0 b 0 ε bbb b bb... M 0. (0) M 0 =({q 0,q }, Σ,δ 0,q 0, {q 0 }) δ 0 (q 0,)=q, δ 0 (q 0,b)=q 0, δ 0 (q,)=q 0, δ 0 (q,b)=q. q 0 q b b (b b ) b {u Σ u u b } 0 : L(( b) ) =L(M )={u u Σ } u Σ u M. () M = ({q 0,q,q }, Σ,δ,q 0, {q }) δ (q 0,)=q, δ (q 0,b)=q 0, δ (q,)=q, δ (q,b)=q 0, δ (q,)=q, δ (q,b)=q 0.

33 q 0 q q b q 0 q 0.. R q 0 {uv u, v Σ } 0 b b bbbbb :. { n b n n 0} N N =,,,... { n b n N n 0}. C C 0 b chr ASCII b b chr [] chr in[] 0 M 0. int M0(chr in[]) M 0 goto \0 q 0 q 0 \0 q q 0

34 int M0(chr in[]){ int n = 0; } q_0: q_: switch(in[n++]){ cse : goto q_; cse b : goto q_0; cse \0 : return ; defult: return -; } switch(in[n++]){ cse : goto q_0; cse b : goto q_; cse \0 : return 0; defult: return -; } int min(){ chr* input = "bb"; printf("\n%s : %d\n",input,m0(input)); }.: M 0 C goto - min input M0(). goto goto recursive cll.... C/C++/Jv 0.. Σ () (c) L = {() n n 0} = {ε,,,,...}

35 int q_0(chr in[]){ switch(in[0]){ cse : return q_(in+); cse b : return q_0(in+); cse \0 : return ; defult: return -; } } int q_(chr in[]){ switch(in[0]){ cse : return q_0(in+); cse b : return q_(in+); cse \0 : return 0; defult: return -; } } int M0(chr in[]){ return q_0(in); }.: M 0 C () Σ={} (b) Σ={, b} (c) Σ={, b, c}... Σ={, b} 0 () b bb, bb, bb (b) bb b bb, bb, bb (c) b b bb, bb, bb, (d) bb b bb, bbb, bbbb (e) 0 b 0 ε,, bbb, bbb, bbb (f) bb, bbbbbbbbbbb bbbb b

36 .. () R (b) T

37 q q. () q q, q,.... () nondeterministic q. (). ()

38 q q q q q q () () ().:. 0 0 / /

39 u v w H,F,R H,F q 0 H q F F q.: deterministic finite stte utomton DFA (nondeterministic finite stte utomton NFA... L J. L J = {uvw u {H, F, R},v {H, FF}, w {H, F} } 0 L J u v w DFA. uvw NFA. NFA u v w q 0 H F R q 0 u ( {H, F, R} ) q 0 q v ( {H, FF}) q H F q w ( {H, F} ) DFA q 0 H q 0 q q 0 F q 0 q DFA q H R DFA DFA q

40 NFA. HFRFHF q 0 H q 0 F q q 0 q q R q 0 F q 0 H q q 0 F q 0 q q q 0 q 0 H q 0 q q q F q q R HFRFHF. FFRFHRF q 0 F q 0 F q q 0 q R q 0 F q 0 H q q 0 q R q 0 F q 0 q q 0 FFRFHRF NFA / 0

41 . NFA M =(Q, Σ,δ,q 0,F) Q Σ q 0 F DFA Q Σ q 0 Q F Q δ DFA Q Σ Q δ ˆδ : Q Σ Q ˆδ(q, ε) = {q}, ˆδ(q, u) = p δ(q,) ˆδ(p, u) Σ u Σ u ˆδ(q 0,u) F q 0 u ˆδ(q 0,u)) u M M L(M) M L(M) ={u Σ ˆδ(q 0,u) F }. M J, M J, =({q 0,q,q }, {H, F, R},δ J,,q 0, {q }) δ J, (q 0, H) = {q 0,q }, δ J, (q 0, F) = {q 0,q }, δ J, (q 0, R) = {q 0 }, δ J, (q, H) = {q }, δ J, (q, F) = {q }, δ J, (q, R) =, δ J, (q, H) =, δ J, (q, F) = {q }, δ J, (q, R) =. M J, L(M J, )={u {H, F, R} ˆδ J, (q 0,u) {q } = }

42 HRHF M J, ˆδ J, (q 0, HRHF) ˆδ J, (q 0, HRHF) = ˆδ J, (p, RHF ) p δ J, (q 0,H) = ˆδ J, (q 0,RHF) ˆδ J, (q,rhf) = ˆδ J, (p, HF ) ˆδ J, (p, HF ) p δ J, (q 0,R) p δ J, (q,r) = ˆδ J, (q 0,HF) = ˆδ J, (p, F ) p δ J, (q 0,H) = ˆδ J, (q 0,F) ˆδ J, (q,f) = ˆδ J, (p, ε) ˆδ J, (p, ε) p δ J, (q 0,F) p δ J, (q,f) = (ˆδ J, (q 0,ε) ˆδ J, (q,ε)) ˆδ J, (q,ε) = ({q 0 } {q }) {q } = {q 0,q,q } ˆδ J, (q 0, HRHF) {q } = {q } HRHF L J = {uvw...} u v w. u {H, F, R} δ J, (q 0, H) q 0, δ J, (q 0, F) q 0, δ J, (q 0, R) q 0. v {H, FF} 0 δ J, (q 0, H) q, δ J, (q 0, F) q, δ J, (q, F) q w {H, F} δ J, (q, H) q, δ J, (q, F) q. NFA DFA DFA NFA DFA M J. M J =({q 0,q,q }, {H, F, R},δ J,q 0, {q })

43 δ J (q 0, H) = q, δ J (q 0, F) = q, δ J (q 0, R) = q 0, δ J (q, H) = q, δ J (q, F) = q, δ J (q, R) = q 0, δ J (q, H) = q, δ J (q, F) = q, δ J (q, R) = q 0. NFA M J M J =({q 0,q,q }, {H, F, R},δ J,q 0, {q }) δ J (q 0, H) = {q }, δ J (q 0, F) = {q }, δ J (q 0, R) = {q 0 }, δ J (q, H) = {q }, δ J (q, F) = {q }, δ J (q, R) = {q 0 }, δ J (q, H) = {q }, δ J (q, F) = {q }, δ J (q, R) = {q 0 }. DFA NFA. NFA DFA. NFA DFA NFA Σ={, b} 0 NFA DFA : L(ε) =L(M )=L(M )={ε} 0 NFA M. () M = ({q 0 }, Σ,δ,q 0, {q 0 }) δ (q 0,)=, δ (q 0,b)=. () NFA NFA : L( ) =L(M )=L(M )= NFA M. () M =({q 0 }, Σ,δ,q 0, ) δ (q 0,)=, δ (q 0,b)= 0 M. () DFA NFA q 0 q 0

44 q 0 q 0 q 0 q () () () q 0 q b q q q 0 () () q 0 q q 0 q b b () b q (),b q 0 q q ().: NFA : L() =L(M )=L(M )={} {} NFA M. () M =({q 0,q }, Σ,δ,q 0, {q }) δ (q 0,)={q }, δ (q,)=, δ (q 0,b)=, δ (q,b)=. M. () NFA NFA Σ {} NFA 0 NFA. ()

45 : L(b) =L(M )=L(M )={b} {b} NFA M. () M =({q 0,q,q,q }, Σ,δ,q 0, {q }) δ (q 0,)={q }, δ (q 0,b)=, δ (q,)=, δ (q,b)={q }, δ (q,)={q }, δ (q,b)=, δ (q,)=, δ (q,b)=. DFA M. () NFA : L( )=L(M )=L(M )={ n n 0} 0 NFA M. () M =({q 0 }, Σ,δ,q 0, {q 0 }) δ (q 0,)={q 0 }, δ (q 0,b)=. 0 M. () : L( b )=L(M )=L(M )={ n n 0} {b n n 0} NFA M. () M =({q 0,q,q }, Σ,δ,q 0, {q,q }) δ (q 0,)={q }, δ (q 0,b)={q }, δ (q,)={q }, δ (q,b)=, δ (q,)=, δ (q,b)={q }. NFA b M. () : L((b) )=L(M )=L(M )={(b) n n 0} 0 NFA M. () M =({q 0,q }, Σ,δ,q 0, {q 0 }) δ (q 0,)={q }, δ (q 0,b)=, δ (q,)=, δ (q,b)={q 0 }.

46 NFA DFA M. () q NFA DFA NFA DFA NFA : L(( b) ) =L(M )=L(M )={u u Σ } 0 NFA M. () M =({q 0,q,q }, Σ,δ,q 0, {q }) δ (q 0,)={q 0,q }, δ (q 0,b)={q 0 }, δ (q,)={q }, δ (q,b)=, δ (q,)=, δ (q,b)=. DFA M. () b q 0 NFA NFA δ (q 0,)={q 0,q } q 0 q q {uv u, v Σ } NFA b b bbbbb NFA. NFA DFA 0 NFA NFA DFA NFA DFA NFA. HFRFHF NFA

47 q 0 H q 0 F q q 0 q q R q 0 F q 0 H q q 0 F q 0 q q q NFA NFA DFA NFA DFA NFA q 0 H q 0 F q 0 R F q0 q 0 H q0 F q 0 q q q q q q q q 0 H NFA q 0 q 0 DFA q 0 q F NFA q 0 q 0 q q q DFA q 0 q q 0 q q q 0 q q DFA q 0 HFRFHF q 0 q q q 0 q q NFA q 0 q q q DFA q 0 q q NFA q q 0 q q DFA 0 DFA DFA NFA DFA NFA DFA NFA NFA DFA NFA n DFA n DFA NFA DFA n n

48 q q 0, 0, q 0 q q NFA: M 0 0, q 0 q 0 q 0 q 0 q q 0 0 q q 0, q q 0 0 q 0 q q 0, DFA: M 0 0, DFA: M 0.: NFA DFA M =(Q, Σ,δ,q 0,F) NFA M DFA: M =(Q, Σ,δ,q 0,F ) u u L(M) u L(M ) u / L(M) u/ L(M ) M M Q Q = Q Q M M δ : Q Σ Q M δ : Q Σ Q δ (P, ) = δ(p, ) p P q 0 = {q 0 } M P F Q P F Q Q M F 0. NFA: M 0 M 0 =({q 0,q,q }, {0, },δ,q 0, {q }) δ

49 δ(q 0, 0) = {q,q }, δ(q 0, ) =, δ(q, 0) =, δ(q, ) =, δ(q, 0) =, δ(q, ) = NFA DFA. M 0 M 0 = (Q 0, {0, },δ 0,q 0,F 0) Q 0 = {q 0,q,q } = {, {q 0 }, {q }, {q }, {q 0,q }, {q 0,q }, {q,q }, {q 0,q,q }} q 0 = {q 0 } F 0 = {{q }, {q 0,q }, {q,q }, {q 0,q,q }} δ 0(, 0) =, δ 0(, ) =, δ 0({q 0 }, 0) = {q,q }, δ 0({q 0 }, ) =, δ 0({q }, 0) =, δ 0({q }, ) =, δ 0({q }, 0) =, δ 0({q }, ) =, δ 0({q 0,q }, 0) = {q,q }, δ 0({q 0,q }, ) =, δ 0({q 0,q }, 0) = {q,q }, δ 0({q 0,q }, ) =, δ 0({q,q }, 0) =, δ 0({q,q }, ) =, δ 0({q 0,q,q }, 0) = {q,q }, δ 0({q 0,q,q }, ) =.. M 0 q 0 = {q 0 } {q 0 } {q,q } {q 0 } {q,q } M 0. M 0 M 0 = (Q 0, {0, },δ 0,q 0,F 0) Q 0 = {, {q 0 }, {q,q }} q 0 = {q 0 } F 0 = {{q,q }} δ 0(, 0) =, δ 0(, ) =, δ 0({q 0 }, 0) = {q,q }, δ 0({q 0 }, ) =, δ 0({q,q }, 0) =, δ 0({q,q }, ) =. Q 0, {q 0}, {q }, {q }, {q 0,q }, {q 0,q } [], [q 0 ], [q ], [q ], [q 0,q ], [q 0,q ] {} [ ]

50 R R q 0 () q 0 q H 0 q () q 0 H F q 0 q q 0 q () R q 0 H F R q 0 q F H R q 0 H F R q 0 q F H q 0 q q 0 q q H R F q 0 q H q 0 q q F R () () DFA M J,.: NFA. DFA DFA M 0 M 0 0 {q 0 } DFA δ δ (,)= DFA NFA NFA NFA DFA M J,. DFA DFA {q 0,q,q } DFA {q 0 } DFA. () H 0

51 {q 0,q }. () {q 0,q } NFA q DFA {q 0,q } F {q 0,q }. () {q 0,q } F {q 0,q,q }. (). () DFA. () M J, M J, =(Q J,, {H, F, R},δ J,,q 0,F J,) Q J, = {{q 0 }, {q 0,q }, {q 0,q }, {q 0,q,q }}, q 0 = {q 0 }, F J, = {{q 0,q }, {q 0,q,q }}. 0 δ J, ({q 0}, H) = {q 0,q }, δ J, ({q 0}, F) = {q 0,q }, δ J, ({q 0}, R) = {q 0 }, δ J, ({q 0,q }, H) = {q 0,q }, δ J, ({q 0,q }, F) = {q 0,q,q }, δ J, ({q 0,q }, R) = {q 0 }, δ J, ({q 0,q }, H) = {q 0,q }, δ J, ({q 0,q }, F) = {q 0,q,q }, δ J, ({q 0,q }, R) = {q 0 }, δ J, ({q 0,q,q }, H) = {q 0,q }, δ J, ({q 0,q,q }, F) = {q 0,q,q }, δ J, ({q 0,q,q }, R) = {q 0 }.. NFA DFA NFA M =(Q, Σ,δ,q 0,F) DFA M =( Q, Σ,δ,q 0,F ) u ˆδ(q 0,u)= ˆδ ({q 0 },u) u u P ˆδ(q, u) = ˆδ (P, u) q P

52 : u = ε u =0 q ˆδ. ˆδ(q, ε) = q = P q P q P ˆδ. ˆδ (P, ε) =P ˆδ(q, ε) = ˆδ (P, ε) : P n u ˆδ(q, u) = ˆδ (P,u) q P ˆδ. ˆδ(q, u) = ˆδ(q,u) q P q P q P q δ(q,) ˆδ. δ ˆδ (P, u) = ˆδ (δ (P, ),u) = ˆδ(q, u) = q δ (P,) q P q δ (q,) ˆδ(q, u) ˆδ(q, u) = ˆδ (P, u) q P. C NFA NFA DFA 0 lex

53 .. Σ () (c) L = {() n n 0} = {ε,,,,...} NFA () Σ={} (b) Σ={, b} (c) Σ={, b, c}... Σ={, b} NFA NFA NFA DFA 0 () b bb, bb, bb (b) b b bb, bb, bbb, bbb, bbbb (c) bb b bb, bbb, bbbb

54 ε-. ε- 0 ε- ε-trnsition ε ε ε- nondeterministic finite stte utomton with ε-trnsition ε- ε- ε-nfa. ε-nfa q 0 q q q HFRFHF q 0 H q0 ε ε q F q 0 q ε R q0 q ε F q 0 q ε H q0 q ε F q 0 q ε q q q ε q q q q q ε q q ε ε- q 0 H ε- q H q 0 q ε- q 0 q q q ε HFRFHF 0

55 ε- u H,F,R v w H,F q 0 q H q q F F q.: q 0 H q0 F q0 R q0 F q0 ε q H q ε q F q HFRFHF NFA NFA. L J = {uvw...} u v w ε-nfa. ε-. ε-nfa u v w {q 0 } {q,q,q } {q } ε- q 0 q u v q q v w 0. ε-nfa M =(Q, Σ,δ,q 0,F) Q Σ q 0 F NFA Q Σ q 0 ( Q F ( Q δ NFA ε ( Q (Σ {ε}) Q q q ε- ε-closure(q) ( Q) ε-closure(q) ={q} {q Q ε-closure(q) q, δ(q,ε) q } ε-closure(q) q q ε-closure(q) q ε- q q

56 ε- δ ˆδ : Q Σ Q ˆδ(q, ε) = ε-closure(q), ˆδ(q, u) = q ε-closure(q) q δ(q,) ˆδ(q,u) Σ u Σ u ˆδ(q 0,u) F q 0 u ( ˆδ(q 0,u) u M M L(M) M L(M) ={u Σ ˆδ(q 0,u) F } M J, M J, =({q 0,q,q,q,q }, {H, F, R},δ J,,q 0, {q }) δ J, (q 0, H) = {q 0 }, δ J, (q 0, F) = {q 0 }, δ J, (q 0, R) = {q 0 }, δ J, (q 0,ε)={q }, δ J, (q, H) = {q }, δ J, (q, F) = {q }, δ J, (q, R) =, δ J, (q,ε)=, δ J, (q, H) =, δ J, (q, F) =, δ J, (q, R) =, δ J, (q,ε)={q }, δ J, (q, H) =, δ J, (q, F) = {q }, δ J, (q, R) =, δ J, (q,ε)=, δ J, (q, H) = {q }, δ J, (q, F) = {q }, δ J, (q, R) =, δ J, (q,ε)=, M J, L(M J, )={u {H, F, R} ˆδ J, (q 0,u) {q } = } ε-nfa. ε-nfa NFA NFA DFA. ε-nfa NFA

57 ε- M =(Q, Σ,δ,q 0,F) ε-nfa M ε- NFA: M =(Q, Σ,δ,q 0,F ) u u L(M) u L(M ) u / L(M) u/ L(M ) M M Q = Q q 0 = q 0. M δ : Q (Σ {ε}) Q M δ : Q Σ Q δ (q, ) = ˆδ(q, ) = ε-closure(q ) q ε-closure(q) q δ(q,) M q M q ε- ε- F F = F {q Q ε-closure(q) F } ε- q Σ={, b} 0. () ε-nfa M q 0 q ε- q 0 M q 0 q q {ε} M ({q 0,q }, Σ,δ, {q }) δ (q 0,)=, δ (q 0,b)=, δ (q 0,ε)={q }, δ (q,)=, δ (q,b)=, δ (q,ε)=. { F F {q0 }, if ε-closure(q = 0 ) F F, otherwise

58 ε- q 0 q q 0 q M () M q 0 q q 0 q q q M () M q 0 q q 0 q b q b q q b q M () M q 0 q b q,b,b q 0 q,b,b b q b M () M.: ε-nfa NFA

59 ε- M ({q 0,q }, Σ,δ,F ) δ F δ δ (q 0,)=, δ (q,)=, δ (q 0,b)=, δ (q,b)=. F {q 0,q } F = F {q Q ε-closure(q) F } = {q } {q Q ε-closure(q) {q } } ε-closure(q 0 )={q } F q 0. () ε-nfa M q 0 q ε q () NFA M q 0 q M q ε- q M q {}. () () M b 0 b b q0 q q q 0 q q M b q 0 q ε q b q ε- / M. () () () M q 0 ε q q0 q ε q b q ε- M M q0 q 0. M M

60 ε- H,F,R H H H,F q 0 H,F,R q H q H,F q F F H F F q.: ε-nfa. NFA :.. ε- NFA. q 0 H q q q. DFA ε-nfa M =(Q, Σ,δ,q 0,F) NFA M =( Q, Σ,δ,q 0,F ). ε-closure(q 0 ) F q 0 F. u u ˆδ(q 0,u)= ˆδ (q 0,u) 0.. u u u ˆδ(q 0,u)= ˆδ (q 0,u) 0

61 ε- M 0 : q 0 q q b? M : q 0 q b q? M : q 0 q q b? M : q 0 q q c b? c M : q 0 b, q q? M : q 0 c b, q, q?.: ε-nfa NFA. C ε-nfa ε-nfa NFA NFA DFA... ε-nfa M 0,...,M M 0 M

62 ε-.. ε-nfa NFA.. NFA DFA M 0... M Σ={, b} M... Σ={, b, c}

63 . DFA. ε-nfa ε-nfa r Σ L(r) ε-nfa: 0 M =(Q, Σ,δ,q 0,F) u u L(r) u L(M) u / L(r) u/ L(M) M M r r = ( Σ) r = ε r = r r ε-nfa: M M r = r r r = r r r = r r =(r ) r = r r = ( Σ) ε-nfa.() ε-nfa M M =({q 0,q f }, Σ,δ,q 0, {q f }) δ (q 0,)={q f } δ. r = ε ε-nfa.() ε-nfa M ε M ε =({q 0,q f }, Σ,δ ε,q 0, {q f }) δ ε (q 0,ε)={q f } δ ε

64 r= r= r= q 0 q f q 0 q f q 0 q f () () () r=r r q 0 q 0 q f q 0 q f q f () r=r r q 0 q f q 0 q f () r=r * q 0 q 0 q f q f ().: ε-nfa

65 . r = ε-nfa.() ε-nfa M M =({q 0,q f }, Σ,δ,q 0, {q f }) δ r r ε-nfa: M M M =(Q, Σ,δ,q0, {qf }) M =(Q, Σ,δ,q0, {qf }). r = r r ε-nfa.() ε-nfa M A M A =(Q Q {q 0,q f }, Σ,δ A,q 0, {q f }) δ A (q 0,ε)={q 0,q 0} δ A (qf,ε)={q f } δ A (qf,ε)={q f } Σ δ A (q 0,)=δ A (qf,)= δa(qf,)= M q Q Σ {ε} 0 δ A (q, ) =δ (q, ) M q Q Σ {ε} δ A (q, ) =δ (q, ). r = r r ε-nfa.() ε-nfa M C M C =(Q Q, Σ,δ C,q0, {qf }) δ C(qf,ε)={q 0} q Q {qf } Σ {ε} δ C(q, ) =δ (q, ) q Q Σ {ε} δ C (q, ) =δ (q, ). r = r ε-nfa.() ε-nfa MK MK =(Q {q0,qf }, Σ,δK,q0, {qf }) δk(q0,ε)={q0,q f } δ K (qf,ε)={q 0,q f } q Q {qf } Σ {ε} δk(q, ) =δ(q, ) 0. r =(r ) ε-nfa M. r = r + r = r r r = r r (H F R) ε-nfa H F R ε-nfa. () () () (q 0 q f H F ε-nfa.() () ε-nfa.().() H F R (H F) R ε-nfa.() () ε-nfa.().() (H F R) ε-nfa.() ε-nfa.().() A Alterntion C Conctention K Kleene :

66 r=h r=f r=r H () F () R () r=h F H F () r=(h F) R=H F R H F R () r=(h F R) * H F R ().: (H F R) ε-nfa

67 H F R H F F H F.: (H F R) (H FF)(H F) ε-nfa 0 (H F R) (H FF)(H F) ε-nfa. (H F R) (H FF)(H F) ε-nfa... ε-

68 . ε- ε DFA NFA ε-nfa. DFA NFA ε- ε-nfa ε-nfa ε-nfa NFA NFA DFA DFA DFA ε-nfa NFA DFA DFA DFA DFA DFA DFA Σ ={}. () ε-nfa NFA. () DFA. () DFA. C n (n ) ε-

69 q 0 q q q q q () -NFA q 0 q q q q q () NFA q 0 q q q q q q q () DFA.: ε-nfa NFA DFA 0 lex DFA. () DFA DFA DFA DFA C

70 C 0 0. DFA M =(Q, Σ,δ,q 0,F) p, q ( Q) p q equivlent p q u ( Σ ) δ(p, u) δ(q, u) / p q p / q p q u ( Σ ) δ(p, u) δ(q, u). p F q/ F p/ F q F p / q.. ( Σ) δ(p, ) / δ(q, ) p / q. p q p q p q p q 0

71 q 0 q q q 0 [q, q ] () ().: DFA 0 q 0 q q q q q q q.: DFA p q [p, q] p q p q [p, q] p q [p, q] p q.. () DFA. () DFA DFA. q 0 /q, q 0 /q q q. δ(q,)(=q ) δ(q,)(=q ) δ(q,) / δ(q,) q /q q q q q [q,q ].() DFA. (). () 0. DFA C (=!/!! = ).

72 .: q q q q q q q q 0 q q q q q q.: q q q q q q q q 0 q q q q q q... DFA q q q i i q /q i... δ(q, ) =p δ(q,)=p p / p q / q q / q δ(q, ) =p / p = δ(q,). q 0 /q δ(q 0, ) = q /q = δ(q, ) q 0 /q δ(q 0, 0) = q 0 /q = δ(q, 0) q 0 /q δ(q 0, 0) = q /q = δ(q, 0) q 0 /q δ(q 0, ) = q /q = δ(q, ) q /q δ(q, 0) = q /q = δ(q, 0) δ(q, ) = q /q = δ(q, )

73 .: q q q q q q q q 0 q q q q q q q /q δ(q, ) = q /q = δ(q, ) q /q δ(q, ) = q /q = δ(q, ) q /q δ(q, ) = q /q = δ(q, ) q /q δ(q, 0) = q /q = δ(q, 0) q /q δ(q, 0) = q /q = δ(q, 0) q /q δ(q, 0) = q /q = δ(q, 0) δ(q, ) = q /q = δ(q, ) q /q δ(q, 0) = q /q = δ(q, 0) q /q δ(q, ) = q /q = δ(q, ) q /q δ(q, 0) = q /q = δ(q, 0) q /q δ(q, 0) = q /q = δ(q, 0) δ(q, ) = q /q = δ(q, ) q /q δ(q, ) = q /q = δ(q, )... q 0 /q δ(q 0, 0) = q /q = δ(q, 0) δ(q 0, ) = q /q = δ(q, ) q /q δ(q, 0) = q /q = δ(q, 0) δ(q, ) = q /q = δ(q, ).... q 0 q q q q q

74 .: q q q q q q q q 0 q q q q q q 0 0 [q, q ] q [q 0, q ] 0 q 0 0 [q, q ].: DFA.. q 0 q q q q q p q [p, q] 0.. () DFA NFA DFA.... DFA q q q i i q /q i... {q 0 } / {q 0,q } δ({q 0 },F)={q 0,q } / {q 0,q,q } = δ({q 0,q },F)...

75 R R q 0 q H 0 q H F F H R H F q 0 q q 0 q q R F DFA M J,.: DFA.: {q 0,q } {q 0,q } {q 0,q,q} {q 0 } {q 0,q } {q 0,q }. {q 0,q } {q 0,q,q }. DFA. DFA DFA... DFA M J, DFA. DFA

76 .: {q 0,q } {q 0,q } {q 0,q,q} {q 0 } {q 0,q } {q 0,q }.: {q 0,q } {q 0,q } {q 0,q,q} {q 0 } {q 0,q } {q 0,q } R q 0 R H q 0 q q 0 q q F R H,F q 0 q H,F.: DFA

77 0 lex UNIX lex lex , 0,, 00, 0,, +0, 0,, + 0 ( ( )(0 ) )@

78 0 lex // %% { return ; }. { return 0; } %% // int min(){ if(yylex()) printf("yes, %s is ccepted\n",yytext); else printf("no, rejected\n"); } int yywrp(){ return ; } lex lex lex 0. lex lex C lex 0. lex %%. 0.. ction

79 0 lex 0 { return [-][0-]*)@ exception { return 0; } 0. lex C int yylex() yylex() C.. C min yylex() C 0 YES,... is ccepted... yylex() yytext C 0 NO, rejected 0 printf() C lex C++ C++ cout C printf(). int ( )(0 ) )@ lex C++ lex++ flex++ lex -+ C++

80 0 lex * : 0 r r ASCII lex r* 0 [ ] - : () lex [] lex [ ] - lex [0-] (0 ) 0 [-b] ASCII b lex lex exmple.l UNIX > lex exmple.l > flex exmple.l 0 lex.yy.c C > cc lex.yy.c > gcc lex.yy.c.out >./.out 0

81 0 lex YES, NO, rejected 0 +,, +, + lex "-"))*@ + lex + "

82 0 lex { return ; }. { return 0; } %% int min(){ if(yylex()) printf("yes, %s is ccepted\n",yytext); else printf("no, rejected\n"); } int yywrp(){ return ; } lex 0. F R) (H FF)(H FF)[HF]*@ [] [HFR] [HF] H F R H F F R)*(H FF)(H F)*@ 0 lex

83 0 lex { return ; }. { return 0; } %% int min(){ if(yylex()) printf("yes, %s is ccepted\n",yytext); else printf("no, rejected\n"); } int yywrp(){ return ; } lex

84 0. Moore mchine {0, } DFA. DFA. 0.. q 0 0 q

85 0 0 q 0 q 0.: q 0 q q 0.: q 0 0 q 0 q 0 0 q 0 q 0 q bit v v v mod. 00 q 0 q 0 0 q 0 q q 0 0 q 0 0 ε v p p =0,, v p mod v + p + mod

86 0/ q 0 /0 q 0/ /0.: (Q, Σ,,δ,λ,q 0 ) Q Σ δ : Q Σ Q q 0 Q DFA λ : Q 0. Mely mchine 0. DFA... b /b q 0 0 q 0 q 0 q 0 q q H

87 0/0 / 0/ q 0 q q /0 0/ /.:

88 { n b n n 0} = {ε, b, bb, bbb,...} DFA.. Chomsky { n b n n 0} b ) : {( n ) n n 0} = {, (), (()), ((())), (((()))),...} 0 C/C++ +b, +b+c, *b+c, -b*c C C++ Jv. Σ Σ Σ

89 0 terminl symbol terminl nonterminl symbol nonterminl Σ T T T N (T N) u T u α (T N) α T N T (T N) production rule production syntx rule X β X N β (T N) β ε X ε αxγ X N, α,γ (T N) X β αxγ X β αβγ αxγ αβγ αxγ αβγ P α α... α k k α α, α α,, α k α k α α α k vrible

90 derivtion sequence α α k 0 α α k α α k context-free grmmr G (N,T,P,S) N T P S S ( N S (T N) sententil form S T sentence G context-free lnguge L(G) G L(G) ={u T S u} G L(G) { n b n n 0} G = ({S}, {, b},p,s) P = {S ε, S Sb} S ε S Sb b S Sb Sbb bb S Sb Sbb Sbbb bbb... L(G )={u T S u} = { n b n n 0} L(G ) {ε} G = ({S}, {, b},p,s) P = {S b, S Sb} 0 0

91 b G = ({S, A, B}, {, b},p,s) P = {S B, S ba, A, A S, A baa, B b, B bs, B BB} G b : A b B b :. G E E E + / id ( ) E E + E E + E E E + id E E + id id id + id id 0 id + id id id. :

92 : E E + E : E E E : E E E : E E/E : E id : E ( E ).: : G E + E E E leftmost derivtion E + E E E E + E id + E id + E E id + id E id + id id rightmost derivtion E E + E E + E E E + E id E + id id id + id id

93 . A A B...B k A B...B k A B... B k B...B k B i i k B i C...C j B...B i C...C j B i+...b k A B... B i B i B i+... B k C... C j 0 0 S t t...t n S t t...t n syntx tree root S lef t t... t n G t t...t k mbiguous unmbiguous. id + id id.

94 E E E E E E E E E E id + id id id + id id () (b).: id + id id E E E E E E E E E E id + id + id id + id + id () (b).: id + id + id id + id + id.. G opertor precedence id + id id id + (id id). (b) left ssocitive id + id + id (id + id) + id. ().. T term F fctor E T F E + T / F id ( )

95 : E E + T : E E T : E T : T T F : T T/F : T F : F id : F ( E ).: : G E E T E E T F E T T F T T F F F F id + id + id id + id id () id + id + id (b) id + id id.: : id, () >, / > +, id + id id id + id + id.... (). / : E T + E : E T E : E T : T F T : T F/T : T F

96 pushdown utomton stck PDA 0. { n b n n } PDA n 0 PDA. PDA. pop push..... q 0 q q q 0 q b q 0. # initil stck symbol #. q 0 FILO first in, lst out LIFO lst in, first out

97 q 0 # A A A bb... (,# #A) (,A AA) (b,a ) (b,a ) q 0 q (,# #) q.: n b n 0 () A (b) b A A q (c). q () b A A (b) # q ε (c). q A b A b # DFA NFA ε-nfa

98 p Z q Z Z Z... Z k k 0 p q (, Z Z Z...Z k ) ε (ε, Z Z Z...Z k ) (, Z ε).. bbbb q γ u q γ u 0 instntneous description PDA bbbb q 0 # bbbb.() q 0 #A bbbb q 0 #AA bbbb q 0 #AAA bbbb q 0 #AAAA bbbb b.(b) q A

99 q 0 #A bbbb q 0 #AA bbbb q 0 #AAA bbbb q 0 #AAAA bbbb q #AAA bbb q #AA q #A q # q #.:. q #AAA bbb.() q #AA q #A q #.(b) q # q bbbb. ε bb bbb 0 { n b n n 0} PDA n =0

100 PDA : E E + F : F id : E F : F ( E ). PDA q PDA. Z. Z ε 0 PDA DFA NFA NFA DFA PDA PDA PDA PDA {0,, c} {ucu R u {0, } + } u R u 0c0, c, 0c0, 0c0, 00c00, 0c0 S 0c0, S c, S 0S0, S S 0 PDA. PDA. PDA u c u R. 0c0 q {0, } {uu R u {0, } + } c S 00, S, S 0S0, S S u 00

101 (0,# #A) (0,A AA) (0,B BA) (,# #B) (,A AB) (,B BB) (0,A ε) (,B ε) q 0 q (c,a A) (c,b B) (ε,# #) q.: {ucu R u {0, } + } 0 0 uu R ucu R ucu R c uu R PDA. q 0 0 A B. 00 q. uu R uu R u q 0 q. 0

102 q 0 # 0c0 q 0 #A c0 q 0 #AB c0 q 0 #ABB c0 q #ABB 0 q #AB 0 q #A 0 q # q #.:.. PDA PDA 0.. PDA M (Q, Σ, Γ,δ,q 0,Z 0,F) Q Σ q 0 F Q Σ q 0 ( Q) F ( Q) Γ stck lphbet stck symbol 0

103 (0,# #A) (0,A AA) (0,B BA) (,# #B) (,A AB) (,B BB) (0,A ε) (,B ε) q 0 q (0,A ε) (,B ε) (ε,# #) q.: {uu R u {0, } + } Z 0 ( Γ) stck strt symbol stck bottom symbol δ Q Γ (Σ {ε} Q Γ PDA (q, γ, u) ( Q Γ Σ ) s s...s k s s k Z 0 (q, Z 0 γ,u) Q {Z 0 }Γ Σ PDA M =(Q, Σ, Γ,δ,q 0,Z 0,F) (q 0,Z 0,u) u M (q, γz, w) (q Q, γ Γ,Z Γ, Σ, w Σ ) δ(q, Z, ) (p, γ ) M (q, γz, w) (p, γγ,w) (q, γz, w) M (p, γγ,w) 0 M q Z M p Z γ Σ ε ε ε- 0

104 q 0 # 00 q 0 #A 0 q 0 #AB 0 q 0 #ABB 0 q #AB 0 q #A 0 q # q #.:. D,D,,D k (k ) : D M D,D M D,, D k M D k D M D k M M PDA M L(M) L(M) ={u Σ (q 0,Z 0,u) M (p, γ, ε), p F, γ Γ } M u u M. M =({q,q,q }, {, b}, {#,A},δ,q 0, #, {q }) 0

105 q 0 # 00 q 0 #A 0 q 0 #AB 0 q 0 #ABB 0 q 0 #ABBB 0 q 0 #ABBBB 0 q 0 #ABBBBA.:. δ (q 0, #,)={(q 0, #A)}, δ (q 0, #,b)=, δ (q 0, #,ε)=, δ (q 0, A, ) ={(q 0, AA)}, δ (q 0, A, b) ={(q,ε)}, δ (q 0, A, ε) =, δ (q, #,)=, δ (q, #,b)=, δ (q, #,ε)={(q, #)}, δ (q, A, ) =, δ (q, A, b) ={(q,ε)}, δ (q, A, ε) =, δ (q, #,)=, δ (q, #,b)=, δ (q, #,ε)=, δ (q, A, ) =, δ (q, A, b) =, δ (q, A, ε) =. bbbb... PDA 0

106 (q 0, #,bbbb) M (q 0, #A, bbbb) M M M M M (q 0, #AA, bbbb) (q 0, #AAA, bbbb) (q 0, #AAAA, bbbb) (q, #AAA, bbb) (q, #AA, bb) M (q, #A, b) M M (q, #,ε) (q, #,ε).: PDA M 0

107 0 phrse structure grmmr context-sensitive grmmr regulr grmmr α β α (T N) N(T N),β (T N) α β Turing mchine 0 liner bounded utomton. 0

108 Σ={, b, c} { i b j c k i, j, k 0} b c A A, A B, B bb, B C, C cc, C ε. A { m c n m, n 0} {b m c n m, n 0} c b c S ε, S A, S bb, A C, A A, B C, C ε, B bb, C cc. X X N, T {ε}. X Y X, Y N, T {ε} 0 right regulr grmmr X Y X Y left regulr grmmr X X Y u right liner grmmr u left liner grmmr 0

109 .. α β α, β (T N) α β α β Σ ={, b, c} { n b n n } { n b n c n n } S bc, S SBc, cb Bc, bb bb S SBc SBcBc bcbcbc bbbccc 0 0 n n b n c n { n b n c n n } monotonic grmmr / 0

110 . α β 0

111 0. tpe tpe hed finite control prt. cell /. 0 () n... n n blnk symbol B Church s Thesis

112 i n B B B.: (b) (c) q 0. q q () q q (b) (c) δ(q, ) =(q,,l) δ(q, ) =(q,,r) 0 L R. () δ(q, ) (b) q δ

113 . Σ={, b} { m b n m>n} u u b. x 0. b b B b b b x.. 0 q 0 q q q q f q 0 q f q f δ(q f,...) δ(q 0,)=(q,x,R), δ(q 0,b)=, δ(q 0,x)=, δ(q 0,B)= δ(q,)=(q,,r), δ(q,b)=(q,x,l), δ(q,x)=(q,x,r), δ(q,b)=(q f,b,l) δ(q,)=(q,,l), δ(q,b)=, δ(q,x)=(q,x,l), δ(q,b)= δ(q,)=(q,,l), δ(q,b)=, δ(q,x)=(q 0,x,R), δ(q,b)= bb. m>n m b n m DFA PDA

114 q 0 b b B B B q x b b B B B q x x x b B B B q x b b B B B q x x x x B B B q x b b B B B q x x x x B B B q q q q 0 q q x x x x x x x b x b x b x b x x b x x b B B B B B B B B B B B B B B B B B B q q 0 q q q q f 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 B B B B B B B B B B B B B B B B B B.: bb... n n

115 & B B B B B.: += 0 m n m & n m + n. +=. { m b n m>n} m n m n m/n m n 0.. specil-purpose computer universl Turing mchine TM TM... TM i S

116 S B B P[TM i ] B S B B TM i TM U TM i (S) TM U (P[TM i ],S).: S TM i TM i (S). () TM U TM i P[TM i ] TM i S P[TM i ] δ(q 0,)=(q,x,R), δ(q,)=(q,,r), δ(q,)=(q,,l), x R R L... 0,,,,,x,R,L Σ. (b) P[TM i ] S B TM U TM U (P[TM i ],S) TM U S P[TM i ] S S... TM i (S) TM U (P[TM i ],S) TM i (S) TM U (P[TM i ],S) TM i (S) TM i S TM i (S)

117 0 TM U P[TM i ] S TM U (P[TM i ],S) stored progrm method ENIAC ON/OFF : Wikipedi ENIAC EDVAC λ 0...

118 computbility 0 0 Church-Turing thesis Church s thesis Turing complete PC C/C++/Jv/Ruby C++ C++ Web HTML HyperText Mrkup Lnguge SQL Structured Query Lnguge.. / Turing computble

119 ... / semi-lgorithm. x + bx + c b c 0 YES NO b b YES/NO /0 / decision problem decidble undecidble 0 n n N. 0 YES NO 0 semi-decidble n N n N n N n N N N N... n

120 Turing Mchine Hlting Problem 0.. S TM TM(S) S TM TM(S) H H(P[TM],S) P[TM] TM.. H(P[TM],S). TM(S)... H(P[TM],S) YES. TM(S)... H(P[TM],S) NO 0 H S S P[TM] H H(P[TM], P[TM]) H M H H M. H(P[TM], P[TM]) YES... M(P[TM]), H M H(P[TM], P[TM]) M H YES M 0

121 . H(P[TM], P[TM]) NO... M(P[TM]) M M P[M] M(P[M]) M(P[M]) M. M(P[M])... H(P[M], P[M]) NO. M(P[M])... H(P[M], P[M]) YES H 0. H(P[M], P[M]) NO... M(P[M]) H(P[TM],S) NO... TM(S). H(P[M], P[M]) YES... M(P[M]) H(P[TM],S) YES... TM(S). M(P[M])... M(P[M]). M(P[M])... M(P[M]) 0 S TM TM(S) H M(P[M]) M M C/C++ for (int i = 0; ; i++) return brek H NO M

122