Ch.6: Context-Free Grammars

Week 6 of the book "Automata, Formal Languages, and Turing Machines" by Emre Sermutlu (2020) 6.1. Grammars and Languages 6.2. Parse Trees 6.3. Ambiguity

55 flashcards · Computer Science · by lakesare

Part of Textbooks › Automata, Formal Languages, and Turing Machines (Emre Sermutlu) · 14 courses

1. [Grammars and Languages] In a grammar, what are variables and terminals?

   Variables are the symbols that rules replace; terminals are the symbols of the generated strings. Example: in S→0S1∣εS \to 0S1 \mid \varepsilonS→0S1∣ε , SSS is the only variable and 0,10, 10,1 are the terminals.

2. [Grammars and Languages] How does a grammar generate a string?

   Start with the start variable SSS and apply rules until the string contains only terminals. The symbol ∣\mid∣ in a rule is read as or: A→0∣1A \to 0 \mid 1A→0∣1 means A→0A \to 0A→0 or A→1A \to 1A→1 .Example: with S→0S1∣εS \to 0S1 \mid \varepsilonS→0S1∣ε : S→0S1→00S11→0011S \to 0S1 \to 00S11 \to 0011S→0S1→00S11→0011 .

3. [Grammars and Languages] S→ABCDA→I∣YouB→will∣can∣mustC→not∣εD→continue∣stop\begin{aligned}S &\to ABCD\\A &\to \text{I} \mid \text{You}\\B &\to \text{will} \mid \text{can} \mid \text{must}\\C &\to \text{not} \mid \varepsilon\\D &\to \text{continue} \mid \text{stop}\end{aligned}SABCD​→ABCD→I∣You→will∣can∣must→not∣ε→continue∣stop​ How many sentences does this grammar generate?

   24\boldsymbol{24}24 2⋅3⋅2⋅2=242 \cdot 3 \cdot 2 \cdot 2 = 242⋅3⋅2⋅2=24 : one independent choice for each of A,B,C,DA, B, C, DA,B,C,D .Example: "I will not continue", "You must continue" (with C→εC \to \varepsilonC→ε ).

4. [Grammars and Languages] What are the four parts of a context-free grammar (CFG) (V,Σ,R,S)(V, \Sigma, R, S)(V,Σ,R,S) ?

   VVV : variables A finite set. Example: V={S,A}V = \{S, A\}V={S,A} Σ\SigmaΣ : terminals A finite set, disjoint from VVV . Example: Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} RRR : rules (productions) A finite set of rules, each connecting a variable to a string of variables and terminals. Example: S→0A1S \to 0A1S→0A1 , A→0A∣1A∣ε\ A \to 0A \mid 1A \mid \varepsilon A→0A∣1A∣ε SSS : start variable An element S∈VS \in VS∈V .

5. [Grammars and Languages] Another name for a rule of a grammar is a production.

   Example: A→0AA \to 0AA→0A is a production with left side AAA and right side 0A0A0A .

6. [Grammars and Languages] S→0A1A→0A∣1A∣ε\begin{aligned}S &\to 0A1\\A &\to 0A \mid 1A \mid \varepsilon\end{aligned}SA​→0A1→0A∣1A∣ε​ Give a derivation of 001100110011 .

   S→0A1→00A1→001A1→0011\boldsymbol{S \to 0A1 \to 00A1 \to 001A1 \to 0011}S→0A1→00A1→001A1→0011 The last step uses A→εA \to \varepsilonA→ε .

7. [Grammars and Languages] S→0A1A→0A∣1A∣ε\begin{aligned}S &\to 0A1\\A &\to 0A \mid 1A \mid \varepsilon\end{aligned}SA​→0A1→0A∣1A∣ε​ Which language does this CFG generate?

   Strings of length at least 2 that start with 000 and end with 111 . AAA generates every string over {0,1}\{0, 1\}{0,1} .

8. [Grammars and Languages] When is a language LLL a context-free language (CFL)?

   When there is a context-free grammar GGG with L=L(G)L = L(G)L=L(G) . L(G)L(G)L(G) is the set of strings of terminals that can be derived from the start variable of GGG .Example: {0n1n∣n≥0}\{0^n1^n \mid n \ge 0\}{0n1n∣n≥0} is a CFL, generated by S→0S1∣εS \to 0S1 \mid \varepsilonS→0S1∣ε .

9. [Grammars and Languages] Which language does the CFG S→0S1∣εS \to 0S1 \mid \varepsilonS→0S1∣ε generate?

   {0n1n∣n≥0}\boldsymbol{\{0^n1^n \mid n \ge 0\}}{0n1n∣n≥0} S→0S1→00S11→⋯→0nS1nS \to 0S1 \to 00S11 \to \dots \to 0^nS1^nS→0S1→00S11→⋯→0nS1n , and the rule S→εS \to \varepsilonS→ε ends the derivation with 0n1n0^n1^n0n1n .

10. [Grammars and Languages] How is the class of regular languages related to the class of context-free languages?

    Every regular language is context-free, and some context-free languages are not regular. Example: {0n1n∣n≥0}\{0^n1^n \mid n \ge 0\}{0n1n∣n≥0} is context-free ( S→0S1∣εS \to 0S1 \mid \varepsilonS→0S1∣ε ) but not regular (pumping lemma).

11. [Grammars and Languages] Give a CFG over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} for the strings that end with 111111 .

    S→0S∣1S∣11\boldsymbol{S \to 0S \mid 1S \mid 11}S→0S∣1S∣11 Example: S→0S→01S→0111S \to 0S \to 01S \to 0111S→0S→01S→0111 .

12. [Grammars and Languages] Give a CFG over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} for the strings that contain 101101101 .

    S→A101AA→0A∣1A∣ε\boldsymbol{\begin{aligned}S &\to A101A\\A &\to 0A \mid 1A \mid \varepsilon\end{aligned}}SA​→A101A→0A∣1A∣ε​ AAA generates any string over {0,1}\{0, 1\}{0,1} .

13. [Grammars and Languages] Give a CFG over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} for the strings www with ∣w∣≤4|w| \le 4∣w∣≤4 .

    S→AAAAA→0∣1∣ε\boldsymbol{\begin{aligned}S &\to AAAA\\A &\to 0 \mid 1 \mid \varepsilon\end{aligned}}SA​→AAAA→0∣1∣ε​ A→εA \to \varepsilonA→ε lets any of the four positions stay empty. Without ε\varepsilonε the grammar generates the strings with ∣w∣=4|w| = 4∣w∣=4 .

14. [Grammars and Languages] Give a CFG over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} for the strings www with ∣w∣≡0(mod3)|w| \equiv 0 \pmod 3∣w∣≡0(mod3) .

    S→AAAS∣εA→0∣1\boldsymbol{\begin{aligned}S &\to AAAS \mid \varepsilon\\A &\to 0 \mid 1\end{aligned}}SA​→AAAS∣ε→0∣1​ Each use of S→AAASS \to AAASS→AAAS adds exactly 3 symbols.

15. [Grammars and Languages] Give a CFG over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} for the strings that start and end with the same symbol.

    S→0A0∣1A1∣0∣1A→0A∣1A∣ε\boldsymbol{\begin{aligned}S &\to 0A0 \mid 1A1 \mid 0 \mid 1\\A &\to 0A \mid 1A \mid \varepsilon\end{aligned}}SA​→0A0∣1A1∣0∣1→0A∣1A∣ε​ S→0∣1S \to 0 \mid 1S→0∣1 : a string of length 1 starts and ends with the same symbol.

16. [Grammars and Languages] What is a palindrome, and what is wRw^RwR ?

    A string equal to its reverse, w=wRw = w^Rw=wR , where wRw^RwR is the reverse of www . Example: abbaabbaabba , aaaaaa , abaaabaabaaabaabaaaba are palindromes; (abb)R=bba(abb)^R = bba(abb)R=bba .

17. [Grammars and Languages] Is the language of palindromes over {a,b}\{a, b\}{a,b} regular? Is it context-free?

    Not regular, but context-free. Not regular by the pumping lemma: an NFA would need infinitely many states to remember the first half. Context-free: S→aSa∣bSb∣a∣b∣εS \to aSa \mid bSb \mid a \mid b \mid \varepsilonS→aSa∣bSb∣a∣b∣ε generates it.

18. [Grammars and Languages] Give a CFG for the palindromes of even length over Σ={a,b}\Sigma = \{a, b\}Σ={a,b} .

    S→aSa∣bSb∣ε\boldsymbol{S \to aSa \mid bSb \mid \varepsilon}S→aSa∣bSb∣ε Example: S→bSb→baSab→baabS \to bSb \to baSab \to baabS→bSb→baSab→baab .

19. [Grammars and Languages] Give a CFG for the palindromes of odd length over Σ={a,b}\Sigma = \{a, b\}Σ={a,b} .

    S→aSa∣bSb∣a∣b\boldsymbol{S \to aSa \mid bSb \mid a \mid b}S→aSa∣bSb∣a∣b The derivation ends with the middle symbol.Example: S→aSa→abaS \to aSa \to abaS→aSa→aba .

20. [Grammars and Languages] Give a CFG for all palindromes over Σ={a,b}\Sigma = \{a, b\}Σ={a,b} .

    S→aSa∣bSb∣a∣b∣ε\boldsymbol{S \to aSa \mid bSb \mid a \mid b \mid \varepsilon}S→aSa∣bSb∣a∣b∣ε The union of the rules for even length ( ε\varepsilonε ) and odd length ( a∣ba \mid ba∣b ).

21. [Grammars and Languages] To prove that a CFG GGG generates exactly a language PPP , which two parts does the proof have?

    P⊆L(G)P \subseteq L(G)P⊆L(G) : every string of PPP can be derived; and L(G)⊆PL(G) \subseteq PL(G)⊆P : every derived string is in PPP . Both parts are usually proved by induction: the first on the length of the string, the second on the number of derivation steps.

22. [Grammars and Languages] GGG : S→aSa∣bSb∣a∣b∣εS \to aSa \mid bSb \mid a \mid b \mid \varepsilonS→aSa∣bSb∣a∣b∣ε .How does the induction on ∣w∣|w|∣w∣ show that every palindrome www can be derived in GGG ?

    A palindrome with ∣w∣≥2|w| \ge 2∣w∣≥2 is w=avaw = avaw=ava or w=bvbw = bvbw=bvb with vvv a shorter palindrome, so S→aSaS \to aSaS→aSa (or bSbbSbbSb ) followed by a derivation of vvv gives www . Base case ∣w∣≤1|w| \le 1∣w∣≤1 : w=εw = \varepsilonw=ε , aaa or bbb , derived by S→εS \to \varepsilonS→ε , S→aS \to aS→a , S→bS \to bS→b .

23. [Grammars and Languages] GGG : S→aSa∣bSb∣a∣b∣εS \to aSa \mid bSb \mid a \mid b \mid \varepsilonS→aSa∣bSb∣a∣b∣ε .How does the induction on the number nnn of derivation steps show that every string derived in GGG is a palindrome?

    A derivation with n≥2n \ge 2n≥2 steps starts with S→aSaS \to aSaS→aSa or S→bSbS \to bSbS→bSb , so w=avaw = avaw=ava or w=bvbw = bvbw=bvb where vvv is derived in n−1n - 1n−1 steps, hence a palindrome. Base case n=1n = 1n=1 : w=εw = \varepsilonw=ε , aaa or bbb .

24. [Grammars and Languages] Which language does the CFG S→aSb∣SS∣εS \to aSb \mid SS \mid \varepsilonS→aSb∣SS∣ε generate?

    Strings with as many aaa 's as bbb 's, where every prefix has at least as many aaa 's as bbb 's. With aaa as an opening and bbb as a closing parenthesis: the correctly balanced parenthesis strings.Example: aabbabaabbabaabbab is in the language; abbaabbaabba is not (the prefix abbabbabb has more bbb 's).

25. [Grammars and Languages] Give a CFG over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} for the strings of odd length that contain at least two 000 's.

    S→A0A0A∣A0B0B∣B0A0B∣B0B0AA→0B∣1BB→ε∣00B∣01B∣10B∣11B\boldsymbol{\begin{aligned}S &\to A0A0A \mid A0B0B \mid B0A0B \mid B0B0A\\A &\to 0B \mid 1B\\B &\to \varepsilon \mid 00B \mid 01B \mid 10B \mid 11B\end{aligned}}SAB​→A0A0A∣A0B0B∣B0A0B∣B0B0A→0B∣1B→ε∣00B∣01B∣10B∣11B​ AAA generates the strings of odd length, BBB those of even length. The string is ? 0 ? 0 ??\,0\,?\,0\,??0?0? , and the three pieces have odd total length, so either one or all three of them have odd length.

26. [Parse Trees] What properties must a parse tree for a CFG (V,Σ,R,S)(V, \Sigma, R, S)(V,Σ,R,S) have?

    Root The root is labeled SSS . Interior vertices Each interior vertex is labeled by a variable. Leaves Each leaf is labeled by a terminal or ε\varepsilonε . ε\varepsilonε -leaves A leaf labeled ε\varepsilonε is the only child of its parent. Children If a vertex labeled AAA has children labeled B1,B2,…,BnB_1, B_2, \dots, B_nB1​,B2​,…,Bn​ (left to right), then A→B1B2…BnA \to B_1B_2 \dots B_nA→B1​B2​…Bn​ is a rule of the grammar. Example: a vertex SSS with children a,S,aa, S, aa,S,a needs the rule…

27. [Parse Trees] A parse tree is also called a derivation tree.

28. [Parse Trees] How do you read off the string that a parse tree derives?

    Read the leaves from left to right (the ε\varepsilonε leaves contribute nothing). Example: the parse tree of abbbaabbbaabbba in S→aSa∣bSb∣a∣b∣εS \to aSa \mid bSb \mid a \mid b \mid \varepsilonS→aSa∣bSb∣a∣b∣ε .

29. [Parse Trees] S→SS∣AA→aAa∣BB→bB∣ε\begin{aligned}S &\to SS \mid A\\A &\to aAa \mid B\\B &\to bB \mid \varepsilon\end{aligned}SAB​→SS∣A→aAa∣B→bB∣ε​ Show that w=abaaabbaaw = abaaabbaaw=abaaabbaa is generated by this grammar.

    S→SSS \to SSS→SS , where the first SSS derives abaabaaba and the second derives aabbaaaabbaaaabbaa . S→A→aAa→aBa→abBa→abaS \to A \to aAa \to aBa \to abBa \to abaS→A→aAa→aBa→abBa→aba S→A→aAa→aaAaa→aaBaa→aabBaa→aabbBaa→aabbaaS \to A \to aAa \to aaAaa \to aaBaa \to aabBaa \to aabbBaa \to aabbaaS→A→aAa→aaAaa→aaBaa→aabBaa→aabbBaa→aabbaa

30. [Parse Trees] S→ABA→00A∣εB→1B∣ε\begin{aligned}S &\to AB\\A &\to 00A \mid \varepsilon\\B &\to 1B \mid \varepsilon\end{aligned}SAB​→AB→00A∣ε→1B∣ε​ Draw the parse tree of 001100110011 .

    SSS has children A,BA, BA,B ; AAA derives 000000 , BBB derives 111111 :

31. [Ambiguity] When is a derivation a leftmost derivation?

    When at every step the leftmost remaining variable is the one replaced. In a rightmost derivation, the rightmost remaining variable is replaced at every step.Example: with S→ABS \to ABS→AB , A→00A∣εA \to 00A \mid \varepsilonA→00A∣ε , B→1B∣εB \to 1B \mid \varepsilonB→1B∣ε , the leftmost derivation of 001100110011 is S→AB→00AB→00B→001B→0011B→0011S \to AB \to 00AB \to 00B \to 001B \to 0011B \to 0011S→AB→00AB→00B→001B→0011B→0011 .

32. [Ambiguity] S→ABA→00A∣εB→1B∣ε\begin{aligned}S &\to AB\\A &\to 00A \mid \varepsilon\\B &\to 1B \mid \varepsilon\end{aligned}SAB​→AB→00A∣ε→1B∣ε​ 001100110011 has the derivations S→AB→00AB→00B→001B→0011B→0011S \to AB \to 00AB \to 00B \to 001B \to 0011B \to 0011S→AB→00AB→00B→001B→0011B→0011 and S→AB→A1B→A11B→A11→00A11→0011S \to AB \to A1B \to A11B \to A11 \to 00A11 \to 0011S→AB→A1B→A11B→A11→00A11→0011 . Are these essentially different?

    No: they have the same parse tree and only replace the variables in a different order. The first is the leftmost derivation, the second the rightmost derivation.

33. [Ambiguity] When is a CFG ambiguous?

    When some string has two different parse trees, equivalently two different leftmost derivations. Different parse trees give the string different meanings, which is a problem in programming languages.Example: S→S×S∣S+S∣(S)∣a∣b∣cS \to S \times S \mid S + S \mid (S) \mid a \mid b \mid cS→S×S∣S+S∣(S)∣a∣b∣c is ambiguous: a×b+ca \times b + ca×b+c has two parse trees.

34. [Ambiguity] Why does the definition of ambiguity count leftmost derivations (or parse trees) instead of all derivations?

    A string usually has many derivations that differ only in the order of replacing variables and have the same parse tree. Fixing the order (always the leftmost variable) leaves one derivation per parse tree.

35. [Ambiguity] S→S×SS→S+SS→(S)∣a∣b∣c\begin{aligned}S &\to S \times S\\S &\to S + S\\S &\to (S) \mid a \mid b \mid c\end{aligned}SSS​→S×S→S+S→(S)∣a∣b∣c​ Show that this grammar is ambiguous.

    a×b+ca \times b + ca×b+c has two parse trees: one with ×\times× at the root, one with +++ at the root. a×(b+c)a \times (b + c)a×(b+c) (a×b)+c(a \times b) + c(a×b)+c

36. [Ambiguity] Give an unambiguous grammar that generates the same language as S→S×S∣S+S∣(S)∣a∣b∣cS \to S \times S \mid S + S \mid (S) \mid a \mid b \mid cS→S×S∣S+S∣(S)∣a∣b∣c .

    S→S+A∣AA→A×B∣BB→(S)∣a∣b∣c\boldsymbol{\begin{aligned}S &\to S + A \mid A\\A &\to A \times B \mid B\\B &\to (S) \mid a \mid b \mid c\end{aligned}}SAB​→S+A∣A→A×B∣B→(S)∣a∣b∣c​ Outside parentheses, +++ comes only from SSS and ×\times× only from AAA , so a×b+ca \times b + ca×b+c has only the parse tree of (a×b)+c(a \times b) + c(a×b)+c .

37. [Ambiguity] When is a context-free language inherently ambiguous?

    When every CFG that generates it is ambiguous. For many ambiguous grammars an unambiguous grammar for the same language exists; for an inherently ambiguous language none exists.Example: {akbmcn∣k=m or k=n}\{a^kb^mc^n \mid k = m \text{ or } k = n\}{akbmcn∣k=m or k=n} .

38. [Ambiguity] L={akbmcn∣k=m or k=n}L = \{a^kb^mc^n \mid k = m \text{ or } k = n\}L={akbmcn∣k=m or k=n} over {a,b,c}\{a, b, c\}{a,b,c} is inherently ambiguous.What is the idea behind this?

    L=L1∪L2L = L_1 \cup L_2L=L1​∪L2​ with L1={ambmcn}L_1 = \{a^mb^mc^n\}L1​={ambmcn} , L2={anbmcn}L_2 = \{a^nb^mc^n\}L2​={anbmcn} , and the strings anbncna^nb^nc^nanbncn lie in both, so they get two different parse trees. A full proof that every grammar for LLL is ambiguous is harder; the book gives only this idea.

39. [Ambiguity] S→B∣ABA→aA∣aB→Bbb∣A\begin{aligned}S &\to B \mid AB\\A &\to aA \mid a\\B &\to Bbb \mid A\end{aligned}SAB​→B∣AB→aA∣a→Bbb∣A​ Give two different leftmost derivations of aabbaabbaabb .

    S→B→Bbb→Abb→aAbb→aabb\boldsymbol{S \to B \to Bbb \to Abb \to aAbb \to aabb}S→B→Bbb→Abb→aAbb→aabb and S→AB→aB→aBbb→aAbb→aabb\boldsymbol{S \to AB \to aB \to aBbb \to aAbb \to aabb}S→AB→aB→aBbb→aAbb→aabb The aaa 's can come from the AAA inside BBB , or partly from the AAA in S→ABS \to ABS→AB .

40. [Ambiguity] S→B∣ABA→aA∣aB→Bbb∣A\begin{aligned}S &\to B \mid AB\\A &\to aA \mid a\\B &\to Bbb \mid A\end{aligned}SAB​→B∣AB→aA∣a→Bbb∣A​ Which language does this grammar generate, and what is an unambiguous grammar for it?

    {anb2m∣n≥1, m≥0}\boldsymbol{\{a^nb^{2m} \mid n \ge 1, \ m \ge 0\}}{anb2m∣n≥1, m≥0} ; unambiguous: drop the rule S→ABS \to ABS→AB . S→BS \to BS→B , A→aA∣a\ A \to aA \mid a A→aA∣a , B→Bbb∣A\ B \to Bbb \mid A B→Bbb∣A Another one: S→ABS \to ABS→AB , A→aA∣a\ A \to aA \mid a A→aA∣a , B→Bbb∣ε\ B \to Bbb \mid \varepsilon B→Bbb∣ε .

41. [Ambiguity] What is the dangling else ambiguity in if S1 if S2 A else B?

    The else can belong to the inner if (if S2) or to the outer if (if S1). else belongs to if S2. else belongs to if S1.

42. [Exercises] Find a CFG for L={a2nb2m+1cn∣m,n≥0}L = \{a^{2n}b^{2m+1}c^n \mid m, n \ge 0\}L={a2nb2m+1cn∣m,n≥0} over {a,b,c}\{a, b, c\}{a,b,c} .

    S→aaSc∣TT→bbT∣b\boldsymbol{\begin{aligned}S &\to aaSc \mid T\\T &\to bbT \mid b\end{aligned}}ST​→aaSc∣T→bbT∣b​ Each aaaaaa on the left is paired with one ccc on the right; TTT generates the odd numbers of bbb 's.

43. [Exercises] Find a CFG for L={anbm∣n<m}L = \{a^nb^m \mid n < m\}L={anbm∣n<m} over {a,b}\{a, b\}{a,b} .

    S→aSb∣AA→bA∣b\boldsymbol{\begin{aligned}S &\to aSb \mid A\\A &\to bA \mid b\end{aligned}}SA​→aSb∣A→bA∣b​ anbna^nb^nanbn around at least one extra bbb .

44. [Exercises] Find a CFG over {0,1}\{0, 1\}{0,1} for the strings of odd length that contain more 000 's than 111 's.

    S→T0TT→0T1∣1T0∣0T0∣TT∣ε\boldsymbol{\begin{aligned}S &\to T0T\\T &\to 0T1 \mid 1T0 \mid 0T0 \mid TT \mid \varepsilon\end{aligned}}ST​→T0T→0T1∣1T0∣0T0∣TT∣ε​ TTT generates the strings of even length with at least as many 000 's as 111 's; the extra 000 makes the length odd and the 000 's the majority.

45. [Exercises] Find a CFG for L={akbmcn∣k,m,n≥0, k+n=2m}L = \{a^kb^mc^n \mid k, m, n \ge 0, \ k + n = 2m\}L={akbmcn∣k,m,n≥0, k+n=2m} over {a,b,c}\{a, b, c\}{a,b,c} .

    S→AC∣aAbCcA→aaAb∣εC→bCcc∣ε\boldsymbol{\begin{aligned}S &\to AC \mid aAbCc\\A &\to aaAb \mid \varepsilon\\C &\to bCcc \mid \varepsilon\end{aligned}}SAC​→AC∣aAbCc→aaAb∣ε→bCcc∣ε​ AAA gives a2ibia^{2i}b^ia2ibi and CCC gives bjc2jb^jc^{2j}bjc2j . k+nk + nk+n even means kkk and nnn are both even ( ACACAC ) or both odd ( aAbCcaAbCcaAbCc ).

46. [Exercises] Find a CFG for L={akbmcn∣m=k or m=n}L = \{a^kb^mc^n \mid m = k \text{ or } m = n\}L={akbmcn∣m=k or m=n} over {a,b,c}\{a, b, c\}{a,b,c} .

    S→TC∣AUT→aTb∣εU→bUc∣εA→aA∣εC→cC∣ε\boldsymbol{\begin{aligned}S &\to TC \mid AU\\T &\to aTb \mid \varepsilon\\U &\to bUc \mid \varepsilon\\A &\to aA \mid \varepsilon\\C &\to cC \mid \varepsilon\end{aligned}}STUAC​→TC∣AU→aTb∣ε→bUc∣ε→aA∣ε→cC∣ε​ TCTCTC gives ambmcna^mb^mc^nambmcn , AUAUAU gives akbmcma^kb^mc^makbmcm .

47. [Exercises] Describe the language of the CFG S→aSbb∣TS \to aSbb \mid TS→aSbb∣T , T→Tb∣ε\ T \to Tb \mid \varepsilon T→Tb∣ε .

    {anbm∣2n≤m}\boldsymbol{\{a^nb^m \mid 2n \le m\}}{anbm∣2n≤m} Each aaa comes with bbbbbb , and TTT adds any number of further bbb 's.

48. [Exercises] Describe the language of the CFG S→aST∣εS \to aST \mid \varepsilonS→aST∣ε , T→b∣bb∣bbb\ T \to b \mid bb \mid bbb T→b∣bb∣bbb .

    {anbm∣n≤m≤3n}\boldsymbol{\{a^nb^m \mid n \le m \le 3n\}}{anbm∣n≤m≤3n} SSS derives anTna^nT^nanTn , and each TTT gives 1, 2 or 3 bbb 's.

49. [Exercises] S→BTAT→abT∣εA→a∣εB→b∣ε\begin{aligned}S &\to BTA\\T &\to abT \mid \varepsilon\\A &\to a \mid \varepsilon\\B &\to b \mid \varepsilon\end{aligned}STAB​→BTA→abT∣ε→a∣ε→b∣ε​ Describe the language of this CFG.

    The strings over {a,b}\{a, b\}{a,b} that contain neither aaaaaa nor bbbbbb ( aaa 's and bbb 's alternate). An optional bbb , then (ab)i(ab)^i(ab)i , then an optional aaa .

50. [Exercises] Describe the language of the CFG S→TST∣cS \to TST \mid cS→TST∣c , T→a∣b∣c\ T \to a \mid b \mid c T→a∣b∣c .

    The strings over {a,b,c}\{a, b, c\}{a,b,c} of odd length whose middle symbol is ccc .

51. [Exercises] S→0S1∣A∣BA→0A∣0B→B1∣1\begin{aligned}S &\to 0S1 \mid A \mid B\\A &\to 0A \mid 0\\B &\to B1 \mid 1\end{aligned}SAB​→0S1∣A∣B→0A∣0→B1∣1​ Describe the language of this CFG.

    {0n1m∣n≠m}\boldsymbol{\{0^n1^m \mid n \ne m\}}{0n1m∣n=m} AAA adds at least one extra 000 , BBB at least one extra 111 .

52. [Exercises] S→0S1∣0S11∣0S111∣TT→000\begin{aligned}S &\to 0S1 \mid 0S11 \mid 0S111 \mid T\\T &\to 000\end{aligned}ST​→0S1∣0S11∣0S111∣T→000​ Describe the language of this CFG.

    {0n+31m∣n≥0, n≤m≤3n}\boldsymbol{\{0^{n+3}1^m \mid n \ge 0, \ n \le m \le 3n\}}{0n+31m∣n≥0, n≤m≤3n} Each 000 from SSS comes with one, two or three 111 's; TTT adds three more 000 's.Example: 0412∈L0^41^2 \in L0412∈L ( n=1n = 1n=1 , m=2m = 2m=2 ), 031∉L0^31 \notin L031∈/L .

53. [Exercises] S→0S∣1A∣0B0A→0A∣εB→0B0∣1\begin{aligned}S &\to 0S \mid 1A \mid 0B0\\A &\to 0A \mid \varepsilon\\B &\to 0B0 \mid 1\end{aligned}SAB​→0S∣1A∣0B0→0A∣ε→0B0∣1​ Find a string with two leftmost derivations, and an equivalent unambiguous grammar.

    010010010 ; unambiguous: S→0S∣1A, A→0A∣ε\boldsymbol{S \to 0S \mid 1A, \ A \to 0A \mid \varepsilon}S→0S∣1A, A→0A∣ε S→0S→01A→010A→010S \to 0S \to 01A \to 010A \to 010S→0S→01A→010A→010 and S→0B0→010S \to 0B0 \to 010S→0B0→010 .The language is 0∗10∗0^*10^*0∗10∗ ; 0B00B00B0 only adds strings 0k10k0^k10^k0k10k that 0S∣1A0S \mid 1A0S∣1A already generates.

54. [Exercises] S→AB∣BAA→A0∣εB→1B∣ε\begin{aligned}S &\to AB \mid BA\\A &\to A0 \mid \varepsilon\\B &\to 1B \mid \varepsilon\end{aligned}SAB​→AB∣BA→A0∣ε→1B∣ε​ Find a string with two leftmost derivations, and an equivalent unambiguous grammar.

    000000 ; unambiguous: S→ε∣A∣B∣AB∣BA, A→A0∣0, B→1B∣1\boldsymbol{S \to \varepsilon \mid A \mid B \mid AB \mid BA, \ A \to A0 \mid 0, \ B \to 1B \mid 1}S→ε∣A∣B∣AB∣BA, A→A0∣0, B→1B∣1 S→AB→A0B→A00B→00B→00S \to AB \to A0B \to A00B \to 00B \to 00S→AB→A0B→A00B→00B→00 and S→BA→A→A0→A00→00S \to BA \to A \to A0 \to A00 \to 00S→BA→A→A0→A00→00 : BBB can be empty in both ABABAB and BABABA .The language is 0∗1∗∪1∗0∗0^*1^* \cup 1^*0^*0∗1∗∪1∗0∗ .

55. [Exercises] S→AB∣CA→0A1∣εB→0B1∣εC→0C1∣DD→1D0∣ε\begin{aligned}S &\to AB \mid C\\A &\to 0A1 \mid \varepsilon\\B &\to 0B1 \mid \varepsilon\\C &\to 0C1 \mid D\\D &\to 1D0 \mid \varepsilon\end{aligned}SABCD​→AB∣C→0A1∣ε→0B1∣ε→0C1∣D→1D0∣ε​ Find a string with two leftmost derivations. Is there an equivalent unambiguous grammar?

    010101010101 ; no, the language is inherently ambiguous. S→AB→0A1B→01B→010B1→0101S \to AB \to 0A1B \to 01B \to 010B1 \to 0101S→AB→0A1B→01B→010B1→0101 and S→C→0C1→0D1→01D01→0101S \to C \to 0C1 \to 0D1 \to 01D01 \to 0101S→C→0C1→0D1→01D01→0101 .The language is {0i1i0j1j}∪{0i1j0j1i}\{0^i1^i0^j1^j\} \cup \{0^i1^j0^j1^i\}{0i1i0j1j}∪{0i1j0j1i} , and the strings 0i1i0i1i0^i1^i0^i1^i0i1i0i1i lie in both parts.