Suppose that G is a context-free grammar. How can I show that “Is L(G) regular?” is undecidable. Also, prove that L is always context-free but is regular if and only if L(G) = Σ∗.

This is what I have so far

Let N be some language that is known to be context-free but not regular (for example, {a^nb^n | n ≥ 0}). Consider the language L = N#Σ∗ ∪ Σ∗#L(G), where # is some symbol that is not in L(G) or N.

Where to? I just know my prof is going to put this on my exam :s.

  • 1
    $\begingroup$ If your prof is going to put this on your exam, perhaps you would like to ask your prof or one of your TAs the very same question. It might be too late for the prof to change the exam. $\endgroup$ – Yuval Filmus Nov 26 '13 at 10:41
  • $\begingroup$ I think your question is missing something. It is not true that a context-free grammar generates a regular language if and only if it generates $\Sigma^*$. $\endgroup$ – Yuval Filmus Nov 26 '13 at 10:42

This proof-snippet is what you are probably looking for.

We follow your definition. $N$ is a fixed non-regular context-free language over $\Sigma$, $\#$ is a new symbol. For a given grammar $G$ let $L = N\#\Sigma^* \cup \Sigma^* \# L(G)$. Assume $L(G) = \Sigma^*$, then $L = \Sigma^*\#\Sigma^*$ which is a regular language. On the other hand, if $w\notin L(G)$, then $L\cap \Sigma^*\#w = N\#w $, which is not regular (as regular languages are closed under quotient, and $N$ is not regular). Thus also $L$ itself is not regular (as regular languages are closed under intersection).

Conclusion: $L$ is context-free, and $L$ is regular iff $L(G) = \Sigma^*$.

| cite | improve this answer | |
  • 1
    $\begingroup$ (This proof works for other classes of languages, and the result is called Greibach's theorem.) $\endgroup$ – sdcvvc Jan 19 '14 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.