CSE3064-Homework 2 Solved

1.     Consider the context-free grammar S à ySx | yySx | e 

a.     Show that the grammar is ambiguous.  

b.     Derive an equivalent unambiguous grammar.  

 

2.     Design a PDA for the following languages: 

 

a.     𝐿!  $#     |              𝑘 ≥ 0} 

b.     𝐿"  ’    |              𝑎, 𝑏, 𝑐 ≥ 0         and       𝑎 + 𝑏 = 𝑐           } 

 

3.     Prove or disprove the following statements: 

 

a.     The class of context-free languages are closed under the union operation. 

 

b.     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 

X  à xY 

Y  à Sy 

 

a.     What is the language generated by this grammar? 

b.     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): 

 

a.     𝐿! = { < 𝐷, 𝑅            |              𝐷            is           a             DFA, 𝑅 is           a            regular               expression      and       𝐿(𝐷) = 𝐿(𝑅)    } 

b.     𝐿" = {               < 𝑁  |              𝑁           is           an          NFA      and       𝐿