Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

322 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12

Fig. 12-13

Fig. 12-14

Fig. 12-15

12.47. (a) Type 2; (b) Type 0; (c) Type 3.

12.48. S→(a,b,aB,bA),A→(bA, ab, a, b),B→

(b, bA).

12.49. S → (AAB, ABA, BAA),A→ (a, BAAA,

ABAA, AABA, AAAB),

B → (b, BBAA, BABA, aBAAB, ABAB,

AABB).

12.50. S → (aA, bB),A→ (aB, bA, a),B →

(bB, aA, b)

12.51. S→(aSa, b).

12.53. L={ab^2 nc|n≥ 0 }

12.54. L={ancbn|n> 0 }

12.55. (a)〈S〉 ::=a〈A〉〈B〉|〈A〉〈B〉,〈A〉 ::=a, 〈B〉 ::=b.

(b) Not defined for Type 0 language.

(c)〈S〉 ::=a〈B〉,〈B〉 ::=b〈B〉|b〈A〉,〈A〉 ::=a|b.

12.56. (a)〈S〉 ::= a|a〈A〉〈S〉,〈A〉 ::= b〈S〉; (b) See

Fig. 12-16.

Fig. 12-16

12.57. (a)w=aababa; (b)S→aAB,A→aB,B→ba.