CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 321
GRAMMARS
12.47. Determine the type of grammarGwhich consists of the productions:(a)S→aAB; S→AB; A→a; B→b
(b)S→aB; B→AB; aA→b; A→a; B→b
(c)S→aB; B→bB; B→bA; A→a; B→b12.48. Find a regular grammarGwhich generates the languageLwhich consists of all words inaandbsuch that no two
a’s appear next to each other.
12.49. Find a context-free grammarGwhich generates the languageLwhich consists of all words inaandbwith twice as
manya’s asb’s.
12.50. Find a grammarGwhich generates the languageLwhich consists of all words inaandbwith an even number ofa’s.
12.51. FindagrammarGwhich generates the languageLwhich consists of all words of the formanbanwithn≥0.
12.52. Show that the languageGin Problem 12.51 is not regular. (Hint: Use the Pumping Lemma.)
12.53. Describe the languageL=L(G)whereGhas the productionsS→aA,A→bbA,A→c.
12.54. Describe the languageL=L(G)whereGhas the productionsS→aSb,Sb→bA,abA→c.
12.55. Write each grammarGin Problem 12.47 in Backus-Naur form.
12.56. LetGbe the context-free grammar with productionsS→(a, aAS)andA→bS.
(a) WriteGin Backus-Naur form. (b) Find the derivation tree of the wordw=abaa.
12.57. Figure 12-12 is the derivation tree of a wordwin a languageLof a context-free grammarG.
(a) Findw. (b) Which terminals, variables, and productions must belong toG?Fig. 12-12Answers to Supplementary Problems
12.30. (a)uv = ab^2 a^4 ba^2 b^2 ; (b)vu= aba^2 b^2 ab^2 a^3 ;
(c)u^2 =ab^2 a^4 b^2 a^3 ; (d)lu=u;
(e)vlv=v^2 =aba^2 b^2 aba^2 b^2.
12.31. 6, 6, 12, 12, 12.
12.32. (a)l,a,b,c,d,e,ab,bc,cd,de,abc,bcd,cde,
abcd,bcde,w=abcde.
(b)l, a, ab, abc, abcd, w=abcde.
12.33. Ifu=lthenn=1; otherwise,n= 1 +[r+
(r− 1 )+···+ 2 + 1 ]= 1 +r(r+ 1 )/2.
12.34. (a)LK={a^3 ,a^3 b, a^2 b^2 , aba, abab, ab^3 };
(b)KL={a^3 ,a^2 b, aba^2 , abab, b^2 a^2 ,b^2 ab};
(c)L∨K={a^2 ,ab,a,b^2 }; (d)K∧L not defined.
12.35. (a)L^0 ={l}; (b)L^2 ={a^4 ,a^3 b, aba^2 ,abab};
(c) L^3 ={a^6 ,a^5 b, a^3 ba^2 ,a^3 bab, aba^4 ,aba^3 b,
ababa^2 , ababab}.
12.36. (a)L∗={an|nis even}. (b) All wordswinaandb
with only even powers ofb.(c)All words ina, b, cwith each power ofbeven and
each power ofca multiple of 3.
12.37. No.(L^2 )∗⊆(L∗)^2.
12.38. (a)a 1 a 1 a 1 ,a 1 a 2 ,a 2 a 1 a 3 (b)a 1 a 1 a 1 a 1 a 1 ,a 1 a 1 a 1 a 2 ,
a 1 a 1 a 2 a 1 , a 1 a 2 a 1 a 1 , a 2 a 1 a 1 a 1 , a 1 a 1 a 3 , a 1 a 3 a 1 ,
a 3 a 1 a 1 ,a 2 a 3 ,a 3 a 2 ,a 1 a 4 ,a 4 a 1 ,a 5
12.39. (a)L(r)={abnc|n≥ 0 }. (b) All words inxandc
wherex=ab. (c)L(r)=ab∪{cn|n≥ 0 }.
12.40. (a)r=b∗ab∗ab∗ab∗; (b)r=(b∗ab∗ab∗ab∗)∗.
12.41. (a) No; (b) yes; (c) no.
12.42. (a) Yes; (b) no; (c) no.
12.43. See: (a) Fig. 12-13(a); (b) Fig. 12-13(b).
12.44. See: (a) Fig. 12-14; (b) Fig. 12-15(a).
12.45. See: Fig. 12-15(b).
12.46. L(M)consists of all wordswwhich containaabbas
a subword.