# Showing Context Free Grammars that are regular if and only if L(G) = Σ∗.

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.

• 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. – Yuval Filmus Nov 26 '13 at 10:41
• 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^*$. – Yuval Filmus Nov 26 '13 at 10:42

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^*$.