Computer Science 456/656: Automata and Formal Languages

Fall 2011

Homework Assignment 6.

Due December 6, 2011

  1. Find a general grammar that generates the language consisting of all strings of the form anbncn.
  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? That is, is P = co-P? Explain.
  4. A language L is said to be co-NP if its complement, L', is NP. Is there any difference between those concepts? That is, is NP = co-NP? Explain.
  5. Prove that the clique problem is NP-complete.
  6. Prove that the diagonal language is co-RE.
Past homework assignments using the same textbook.

Back to Course Page