B形式语言和自动操作

1、Copyright by 2010Programming Languages Lab.Copyright by 2010Programming Languages Lab.392 11 v : 1. 2. 3. 4. 5. : Copyright by 2010Programming Languages Lab.39311 1 (Formal Language) v : v , (natural language) (formal language) v : 4 v - type 2, v 11 1 (alphabet) (symbol) . 【 11.1】 . 1 = , , , , , ,

2、 , , , , 2 = a, b, c, , z Copyright by 2010Programming Languages Lab.39411 1 (Formal Language) v 11 2 (string) (finite sequence). 11.2】 =a, b, c a, ca, ccba . (sentence) (word) w = abaaa abaaa w.v 11 3 (length) , w |w| , w cardinality . 11.3】 u = apple |u|=5. Copyright by 2010Programming Languages L

3、ab.39511 1 (Formal Language) v 11 4 (concatenation) . , u, v u=a1a2a3 an, v=b1b2b3 bm uv uv uv= a1a2a3 anb1b2b3 bm 11.5】 udog, vhouse uv = doghouse vu = housedog . v 11 5 (empty string) 0 (epsilon) . u, v . u = u = u uv = uv .v an = aaa a (a n)Copyright by 2010Programming Languages Lab.39611 1 (Form

4、al Language) v WR w (reverse) w . 【 11.6】 wccba wR=abcc. v 11 6 , w = uv u w (prefix) , u (proper prefix) . , w v w (suffix) , v (proper suffix) . 11.7】 whouse w h, ho, hou, hous, house house, ouse, use, se, e Copyright by 2010Programming Languages Lab.39711 1 (Formal Language) v 11 7 *(reflexive tr

5、ansitive closure, Kleene closure) -( star) . +(transitive closure, positive closure) * -( dagger) +=*-. 11.9】 = a, b * = , a, b, aa, ab, ba, bb, aaa, + = a, b, aa, ab, ba, bb, aaa, . Copyright by 2010Programming Languages Lab.39811 1 (Formal Language) v 11 8 L * . (finite language) (infinite languag

6、e) 11.10】=a, b (1) L1 = * = , a, b, aa, ab, ba, bb, aaa, . (2) L2 = a, ba, bbbb . (3) L3 = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 . (4) L4 = ap | p (prime number) . (5) L5 = anbn | n 1 . Copyright by 2010Programming Languages Lab.39911 1 (Formal Language) v 11 9 L M (concatenation) LM L M . LM = st | s L t M

7、11.11】 11.10 L4L5 = a p+nbn | p , n 1. v 11 10 L . L0 = Ln = LLn-1 , n 1 11.12】 L=a, ba L3=aaa, aaba, abaa, ababa, baaa, baaba, babaa, bababa Copyright by 2010Programming Languages Lab.40011 1 (Formal Language) v 11 11 (union) L M LM L M . LM = s | s L s M 11.13】 11.10 L2 L3 = a, ba, bbbb, b, bb, bb

8、b. v 11 12 L (zero or more concatenation) L* L*L0L1L2 Ln , L (one or more concatenation) L+ L+ L0L1L2 Ln L*-L0 11.14】 L = 0, 1 L* 0 1 L+ 0 1 . 0iiL1iiLCopyright by 2010Programming Languages Lab.40111 2 v : (finite language) , (infinite language) . , , . . . v 11 13 G=(VN, VT, P, S) VN : VT : VNVT ,

9、VNVTV P : (production rule) , V+, V* (left-hand side) , (right-hand side) . . S : VN (start symbol). Copyright by 2010Programming Languages Lab.40211 2 v , , . (grammar symbol) V(vocabulary) . 11.15】 G (S, A, 0, 1, P, S) P : S 0AS S 0 A S1A A 10 A SS S, A , 0 1 , S . 5. G 0 1 0, 0000, 001100, . v -

10、1, 2 1 |2 . 11.15 S 0AS | 0 v A S1A | 10 | SS . Copyright by 2010Programming Languages Lab.40311 2 v 11 14 , (directed derive) , , V*, . , . (zero or more derivation) (one or more derivation) . 1,2,3,n V* 123n , 1 n , 1 n (produce) (derive) , n 1 reduce . v 11 15 S w w V* w (sentential form) , w VT*

11、 , w (sentence) . , . Copyright by 2010Programming Languages Lab.40411 2 11.16】 11.15 S 0AS ( S0AS ) 010S ( A10 ) 0100 ( S0 ) . , S 0100 S, 0AS, 010S, 0100 , 0100 . , 0100 S . v 11 16 G G L(G) . L(G)wS w, wVT* 11.17 G=(S, E, a, P, S) P : Sa | aE EaS . Sa a . S aE . S aE aaS aaa aaa . G L(G)=a2n+1 |

12、n0 .Copyright by 2010Programming Languages Lab.40511 2 v -Type 0 A w , unrestricted , wi wi+1 w , wi+1 wi (contracting) . type 0 . 1 , | | V+, V* | (non-contracting) (context-sensitive) .2 A , AVN VT(Context-free) .3 A tB | t ABt | t, tVT* A,BVN(regular) , . AtB, At (right-linear) ABt, At (left-line

13、ar) .Copyright by 2010Programming Languages Lab.40611 2 v 11-1 4 v 11-2 , , Type 0Type 0Type 1Type 1Type 2Type 2Type 3Type 3Type 0(unrestricted )RecursivelyEnumeratable setTuring machineType 1(context-sensitive )Context-sensitiveLinear-boundedAutomataType 2(context-free )Context-free Push-downAutoma

14、taType 3( ) Finite automataCopyright by 2010Programming Languages Lab.40711 2 v . 1. (simple matching language) : Lm = anbn | n 0 2. (double matching language) : Ldm = anbncn | n 0 3. (mirror image language) : Lmi = wwR | w VT* 4. (palindrome language) : Lr = w | w = wR 5. (parenthesis language) : L

15、p = w | w .v . , context- free , context-sensitive . context-sensitive context-free .Copyright by 2010Programming Languages Lab.40811 2 11.18】 G1 = (S, A, C, a, b, P, S) P : S A A abC | aABC bB bb CB BC bC bb G1 . A abC . bB bb . | G1 . , G1 L(G1) = anbm | n, m 1 type 1 . 11.19】 G2 = (S, C, a, b, P,

16、 S) P : S aCa C aCa C b G2 . S aCa . A A V*. G2 . , G2 L(G2) = anban | n 1 type 2 . Copyright by 2010Programming Languages Lab.40911 2 11.20】 G3 = (S, B, C, a, b, P, S) P : S aS | aB B bC C aC | a G3 . G3 . , G3 L(G3) = anbam | n,m 1 type 3 . Copyright by 2010Programming Languages Lab.41011 3 v - BN

17、F, EBNF, , BNF(Backus-Naur Form) - , ALGOL 60 , , :=, | 11.22】 (identifier) , . BNF . := | | := a | b | c | | z := 0 | 1 | 2 | | 9 8 BNF . := | | | | | | | | := a | b | c | | z := 0 | 1 | 2 | | 9 Copyright by 2010Programming Languages Lab.41111 3 v . BNF . BNF EBNF. EBNF(Extended BNF) - , , , a a ,

18、, 0 7 . , x x . , x . - 70 10 xCopyright by 2010Programming Languages Lab.41211 3 11.24】 11.22 8 EBNF . := := | := a | b | c | | z := 0 | 1 | 2 | | 9 11.25】 if else . := if then else 11.26】 . := := := | 70Copyright by 2010Programming Languages Lab.41311 3 v (syntax diagram) , , . 1. a a , . 2. A A ,

19、 . 3. AX1X2Xn . Xi . Xi . a aA AX X1 1X X2 2X Xn nCopyright by 2010Programming Languages Lab.41411 3 4. A X1 | X2 | | Xn . Xi . 5. EBNF A := . X X2 2X X1 1X Xn nA AA Aa aCopyright by 2010Programming Languages Lab.41511 3 11.27】 EBNF . := a | (B) := bC := c A, B, C a, (, ), b, c . . . a aA A( () )B B

20、 B Bb bC CB B C CC C Copyright by 2010Programming Languages Lab.41611 3 a aA A( (b b C C ) )Copyright by 2010Programming Languages Lab.41711 4 v (regular grammar) : type 3 . , , context-free , (front-end) . v 9 17 1. . 2. . 3. a VT a a . 4. r, s Lr, Ls , (1) (r) + (s) Lr Ls . (2) (r)(s) Lr Ls . (3)

21、(r)* (Lr)* . Copyright by 2010Programming Languages Lab.41811 4 (precedence) * + (parentheses) . *(Kleene closure) , (concatenation) , +(or, alternate) . 11.28】 (ab)*abb a b abb . 11.29】 0 1 . (1) 0*(01)* (1) 0 1 0+1 . 0* (01)* . 0*(01)* .Copyright by 2010Programming Languages Lab.41911 4 v , , , 11

22、1 . v 11 1 (1) ()() (2) ()() (3) (4) (5) () (6) () (7) (8) (9) (10) * (11) *()* (12) (*)* (13) * (14) ()*(*)* (15) ()*(*)*(16) * (17) * (18) * (19) ()* (20) ()*()* Copyright by 2010Programming Languages Lab.42011 4 v G L(G) , . (coefficient) (regular expression equation) (solution) . v 11 2 , , X=X+

23、 (unique solution) X=*. * X=X . X = X = (*) = + = (+) = * X=X+ * .Copyright by 2010Programming Languages Lab.42111 4 v 11 1 G G = (VN, VT, P, S) , VN： VT： P： AtB, At ABt, At , t VT* A, B VN S : . G L(G) (1) . (2) XX X* . (3) . XX X* , G L(G) . Copyright by 2010Programming Languages Lab.42211 4 11.30

24、】 G = (S, A, B, a, b, P, S) L(G) ? SaAbS AaSbB BaBbB SaAbS -(1) AaSbB -(2) BaBbB -(3) . (3) B=aB + bB + = (a+b)B + X=X+ . B =(a+b)* = (a+b)* -(4) X=X+ S (1) . SaA + bS a(aS + bB) + bS (2) ) aaS + abB +bS aaS + ab(a+b)* +bS (4) ) (aa +b)S + ab(a+b)* X=X+ S = (aa +b)*ab(a+b)* . Copyright by 2010Progra

25、mming Languages Lab.42311 4 v - , , (cell) , (control) . v (accepter) (transducer) - . /(accept/reject) . . Moore Mealy . Copyright by 2010Programming Languages Lab.42411 4 v - (transition diagram) (informal) (formal) . - (state) (node) , (q, a) = p q p (label) a . (double circle) , . 11.31】 11.28 .

26、 := | := a | b | c | | z := 0 | 1 | 2 | | 9 q0q1a|b|c|za|b|c|z|0|1|2|9Copyright by 2010Programming Languages Lab.42511 4 - 5-(tuple) . , M , M = (Q, , , q0, F) , Q： ： q0： (start state, initial state) q0Q F： F Q ： Q 2Q(Q ). , (q, a) = P1, P2, , Pn , P1, P2, , Pn Q Copyright by 2010Programming Languag

27、es Lab.42611 4 v - (DFA) (NFA) DFA (q, a) = P1, P2, , Pn n=1 . , Q Q NFA (q, a) = P1, P2, , Pn n1 . , Q 2Q Copyright by 2010Programming Languages Lab.42711 4 11.32】 11.31 . M = (Q, , , q0, F) , Q = q0,q1 = a, b, c, , z, 0 , 1, 2, , 9 q0 = q0 F =q1 abcz0129q0q1q1q1q1 q1q1q1q1q1q1q1q1q1Copyright by 20

28、10Programming Languages Lab.42811 4 v , , v ( ) Copyright by 2010Programming Languages Lab.42911 4 v NFA NFA DFA DFA . v -NFA - 1. , a 2. N1+N2, N1N2, N* i if f : :i if fa aa :a :i iA AB BC CD Df fN N1 1N N2 2 N N1 1+N+N2 2 : :Copyright by 2010Programming Languages Lab.43011 4 v v 11.33】 (a+b)* f fi iA AB BN N1 1 N N2 2N N1 1NN2 2 : :f fi iA AB B N NN N* * : :2 23 35 54 46 6a ab b 7 71 18 8startstart Copyright by 2010Programming Languages Lab.43111 4 v M = (Q, , , q0, F) G = (VN, VT, P, S) -VN, VT, P, S Q, , , q0, F . , VN = Q VT = S = q0 P : if (q, a) = r, then q ar; if qF, then q ; 1