Computer Science 456/656: Automata and Formal Languages

Spring 2009

Homework Assignment 6.

Due April 23, 2009

1. Find a general grammar that generates the language consisting of all strings of the form aⁿbⁿcⁿ.
2. We know that the problem of whether a given context-free grammar generates a given string is decidable. Prove that the problem of whether a given general grammar generates a given string is undecidable.
3. A language L is said to be co-P if its complement, L', is P. Is there any difference between those concepts? Explain.
4. A language L is said to be co-NP if its complement, L', is NP. Is there any difference between those concepts? Explain.
5. Prove that the clique problem is NP-complete.
6. Prove that the diagonal language is co-RE.