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 ๐ฟ
