Computer Science 456/656: Automata and Formal Languages
Fall 2011
Homework Assignment 6.
Due December 6, 2011
-
Find a general grammar that generates the language consisting of
all strings of the form anbncn.
-
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.
-
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.
-
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.
-
Prove that the clique problem is NP-complete.
-
Prove that the diagonal language is co-RE.
Past homework assignments
using the same textbook.

Back to
Course Page