- G is not a type 1 grammar because the production rule C violates the condition of type 1 grammar.
So G is a type 0 grammar (structural grammar). 1b) G = (N, T, P, S); in which:
N = {S, A, B, C, D} ; T = {a, b};
P ={S ABC; AB aADb; Dab bDb; DbC BaC; aB Ba; AB ; C };
S = S.
2a) - G is not a type 3 grammar because the production rule DF B violates the condition of type 3 grammar;
- G is not a type 2 grammar because the production rule DF B violates the condition of type 2 grammar;
- G is not a type 1 grammar because the production rule DF B violates the condition of type 1 grammar.
So G is a type 0 grammar (constructive grammar).
2b) G = (N, T, P, S); in which:
N = {S, A, B, C, D, E, F} ; T = {a, b};
P = {S ABaDF; BD DCB; BC bB; AD AAE; EC AE; EB BE; EF BBDF; DF B | };
S = S.
3a) - G is not a type 3 grammar because the production rule S SS violates the condition of type 3 grammar;
- G is a type 2 grammar (context-free grammar) because all of its productions satisfy the conditions of type 2 grammar.
3b) G = (N, T, P, S) with: N = {S};
T = {a, b};
P = {S SS; S aSb; S bSa; S ab; S ba}.
S = S.
4a) G is a type 3 grammar (regular grammar) because all its productions satisfy the conditions of a right linear grammar.
4b) G = (N, T, P, S) with: N = {S};
T = {a};
P = {S aS; S a; A abB | B| }; S = S.
1.18. 1) - G is a type 3 grammar (left linear grammar) because all of its productions satisfy the conditions of left linear grammar.
- G = (N, T, P, S) with:
N = {S, A};
T = {a, b};
P = {S Sab; S Aa; A Sa; A Abba; A a; S }; S = S.
2) - G is a type 1 grammar (context-sensitive grammar) because:
+ G is not a type 3 grammar because the production rule AB BA violates the condition of type 3 grammar;
+ G is not a type 2 grammar because the production rule AB BA violates the condition of type 2 grammar;
+ All of its productions satisfy the conditions of type 1 grammar.
- G = (N, T, P, S) with:
N = {S, A, B};
T = {a, b};
P = {S AB; AB BA; A aA; B Bb; A a; B b}; S = S.
3) - G is a type 1 grammar (context-sensitive grammar) because:
+ G is not a type 3 grammar because the production rule Bb Abb violates the condition of type 3 grammar;
+ G is not a type 2 grammar because the production rule Bb Abb violates the condition of type 2 grammar;
+ All of its productions satisfy the conditions of type 1 grammar.
- G = (N, T, P, S) with:
N = {S, A, B};
T = {a, b};
P = {S A; S AAB; Aa Aba; A aa; Bb Abb; AB
ABB; B b};
S = S.
1.19. 1) - G is a type 3 grammar (left linear grammar) because all of its productions satisfy the conditions of left linear grammar.
- G = (N, T, P, S) with:
N = {S};
T = {a};
P = {S Sa; S a; S }; S = S.
2) - w = .
Applying the production law S , we have the one-step derivation S .
- w = a.
Applying the production rule S a, we have a one-step derivation S a.
Or
Applying the production rule S Sa, then applying the production rule S , we have the two-step derivation S
Sa a.
- w = aa.
S Sa Saa aa or S Sa aa.
- w = a i ; with i N.
Applying i-1 times the production rule S Sa and once the production rule S a, we have S i a i . Or applying i times the production rule S Sa and once the production rule S , we have S i+1 a i .
3) L(G) = {a i i N}.
1.20. 1) - G is a type 3 grammar (right linear grammar) because all of its productions satisfy the conditions of right linear grammar.
- G = (N, T, P, S) with:
N = {S, A, B};
T = {a, b};
P = {S aA; A aA; A aB; B bB; B b}; S = S.
2) - w = aab.
S aA aaB aab.
- w = aaaaabb.
S aA aaA aaaA aaaaA aaaaaB aaaaabB aaaaabb.
- w = a i b j ; with i, j N + ; i 2.
Apply the production rule S aA once
Applying i-2 times the production rule A aA and once the production rule A aB, we have S i a i B. Applying j-1 times the production rule B bB and once the production rule B b, we have S i+j a i b j .
3) L(G) = {a i b j ; with i, j N + ; i 2}.
1.21. 1) - G is a type 2 grammar.
- G = (N, T, P, S) with:
N = {S};
T = {a, b};
P = {S bSa; S }; S = S.
2) - w = .
S .
- w = three.
S bSa ba.
- w = b i a i ; with i N.
Applying the production rule S bSa i-1 times and the production rule S once , we have S i b i a i .
3) L(G) = {b i a i ; with i N}.
1.22. 1) - G is a type 2 grammar.
- G = (N, T, P, S) with:
N = {S, A};
T = {a, b};
P = {S aAb; S ; A aAb; A }; S = S.
2) - w = .
S .
- w = ab.
S aSb ab.
- w = aaaabbbb.
S aAb aaAbb aaaAbbb aaaaAbbbb aaaabbbb.
- w = b i a i ; with i N.
Applying the production rule S once , we have S . Applying the production rule S aAb once
Applying the production rule A aAb i -1 times and the production rule A once , we have S i+1
a i b i with i N + .
3) L(G) = {a i b i ; with i N}.
1.23. 1) - G is a type 2 grammar.
- G = (N, T, P, S) with:
N = {S, A, B};
T = {a, b};
P = {S AB; A aA; A a; B aB; B b}; S = S.
2) - w = aab.
S AB aAB aaB aab.
- w = aaaaab.
S AB aAB aaAB aaaAB aaaaB aaaaaB aaaaab.
- w = a i b; with i N + .
Apply the production law S AB once.
Applying the production rule A aA i-1 times and the production rule B aB once , we have S i+1 a i b. Applying B b once , we have S i+2 a i b.
3) L(G) = {a i b; with i N + }.
1.24. 1) S aA; A aA|b|c.
2) S Aab; A aA|b|c.
3) S Aba; A aA|b|c.
4) S Abcd; A aA|b|c. 1.25. 1) S A1; A A0|0.
2) S 0A; A 0A|1.
3) S 0A1; A 0A|0.
Or S AB; A 0A|0; B 1
1.26. 1) S A1; A A1|B; B C000; C .
2) S 000A; A 1A|1.
3) S 000AB; A 1A|1; B .
Or S AB; A 000; B 1B|1.
1.27. S AB; A 0A1|01; B 2B3 | .
1.28. S AB; A aAb| ab; B cB| .
1.29. 1) S abA; A abA| B; B cB|c;
2) S Ac; A Ac| B; B Bab| ab;
3) S abAB; A abA| ; B cB|c. Or S AB; A abA|ab; B cB|c.
1.30. 1) S A2; A A2|B; B B1|C; C 000.
2) S 000A; A 1A| B; B 2B| 2.
3) S 000AB; A 1A|1; B 2B|2.
1.31. 1) S S2| A; A A1|C; C C0| .
2) S 0S|A; A 1A|B; B 2B| .
3) S ABC; A 0A| ; B 1B| ; C 2C| .
1.32. 1) S S3|A; A A2|B; B B1|C; C C0| .
2) S 0S|A; A 1A|B; B 2B|C;C 3C| .
3) S ABCD; A 0A| ; B 1B| ; C 2C| ; D 1D| .
2. Chapter 2 exercises
2.16. 1) Representation of M
a) Tabular form:
- q 0 = A ;
- F = C, E ;
- :
Q
a | b | |
A | A | B |
B | D | E |
C | E | D |
D | C | E |
E | E |
Maybe you are interested!
-
Formal Coordination Mechanisms -
Some measures to help students in the first grades of primary school use mathematical language effectively - 14 -
Han Mac Tu's Poetic Language - Rich in Imagery: -
Assessments and Research on Phan Khoi's Influence on National Language -
Language and Tone:
b) Graph form: a a
b a
Start A b B
C b D b E a
a
2) Automat M is a deterministic finite automaton; since q Q and a , we have:
(q, a) 1
3) - (A, aaabbaaaa)
+ (A, a) = A; (A, a) = A; (A, a) = A;
+ (A, b) = B;
+ (B, b) = E;
+ (E, a) = E; (E, a) = E; (E, a) = E; (E, a) = E
(A, aaabbaaaa) = E.
- (B, aaaabbaa);
+ (B, a) = D;
+ (D, a) = C;
+ (C, a) = E;
+ (E, a) = E;
+ (E, b) = ;
+ ( , b) = ;
+ ( , a) = .
+ ( , a) = .
(B, aaaabbaa) = .
4) - w = aabaaaaa$
We present the algorithm using a single deterministic automaton to obtain w in the following table:
Step
q | c | |
initialize | A | a |
1 | A | a |
2 | A | b |
3 | B | a |
4 | D | a |
5 | C | a |
6 | E | a |
7 | E | a |
8 | E | $ |
We have q = E F. So the above automaton guesses that it gets from w = aabaaaaa.
- w = aaaababbb$
Step
q | c | |
initialize | A | a |
1 | A | a |
2 | A | a |
3 | A | a |
4 | A | b |
5 | B | a |
6 | D | b |
7 | E | b |
8 | | b |
9 | | $ |
We have q = F. So the above automaton cannot guess from w = aaaababbb.