[SOLVED] CSE3064 Homework #2 

2.  Consider the context-free grammar S à ySx | yySx | e
   1. Show that the grammar is ambiguous.
   2. Derive an equivalent unambiguous grammar.
3.  Design a PDA for the following languages:
4. 𝐿_! ^$# |           𝑘 ≥ 0}
5. 𝐿_” ^’ |           𝑎, 𝑏, 𝑐 ≥ 0       and      𝑎 + 𝑏 = 𝑐        }

3. Prove or disprove the following statements:
4. The class of context-free languages are closed under the union operation.

1. The class of context-free languages are closed under the intersection operation. Hint: Consider the following two languages:

𝐿_! = {𝑎⁽𝑏⁾𝑐⁾                |           𝑚, 𝑛 ≥ 0}

𝐿_” = {𝑎⁾𝑏⁾𝑐⁽               |           𝑚, 𝑛 ≥ 0}

4.  Given the following context-free grammar:

S à XY | e

• à xY
• à Sy

1. What is the language generated by this grammar?
2. Draw the parse tree for the string xxyyyy.

5.  Convert the following context-free grammar to an equivalent grammar in Chomsky Normal Form.

S à ASA | A | e

A à 11 | e

6.  What is the language on {a,b} recognized by the following Turing Machine (a,b,x, and box are the tape symbols where box denotes the empty cell) ?
7.  Prove or disprove the following statement:

Turing-recognizable languages are closed under the intersection operation.

8. Prove that the following languages are decidable (give the deciders for each of the language):

1. 𝐿_! = { < 𝐷, 𝑅 > |           𝐷         is         a          DFA, 𝑅 is         a          regular           expression         and      𝐿(𝐷) = 𝐿(𝑅)   }
2. 𝐿_” = { < 𝑁 > |           𝑁         is         an        NFA     and      𝐿