COT 6315/CM 710-R Formal Languages and Computation Theory (Summer 2000)

Examination 2

NOTE: Complete exactly 5 of the following 6 questions. Clearly note which question you do NOT want graded.

I am NOT answering the following question: _______.

1. Prove or disprove: the context-free languages are closed under set subtraction.
   (Hint: What CFL has the more strings than any other?)

2. Write a grammar generating the language accepted by the following PDA:

   

   Note that you need not apply Sipser's method to generate this grammar, but you may if you wish.

3. You've seen how to convert a PDA such as Sipser has described into a machine that empties its stack before accepting.

   Consider an epsilon-PDA P = (Q, S, G, d, q₀) with state set Q, input alphabet S, stack alphabet G, transition function d, and start state q₀ in Q, that starts with an empty stack and accepts a string if its input is empty and its stack is empty. How we can convert such a machine to one that accepts by final state?

   What language is a subset of every language accepted by such a machine?

4. Is the language aⁱb^jcⁱ context-free?
   Demonstrate the correctness of your answer by either showing a CFG for the language and arguing its correctness or showing that the language does not satisfy the CFL pumping lemma.

5. Convert the following grammar to Chomsky Normal Form:

   S -> aB | bA
   A -> a | bAA
   B -> b | aBB

6. Is the language L = { aⁱb^jc^k | none of i, j, and k are equal } context-free?
   Demonstrate the correctness of your answer by either showing a CFG for the language and arguing its correctness or showing that the language does not satisfy the CFL pumping lemma.