Decidability of DCFL and Undecidability of CFL with respect to regularity

Question

I synced with this Hendrik Jan's answer that to prove undecidability of regularity for CFL is usually obtained from two properties of the context-free languages: (1) they are closed under union, and (2) universality is undecidable.

And for DCFL (1) are not closed under union, (2) have decidable universality.

My question is that how can we say CFL regularity is undecidable if it closed under union and $\Sigma^*$ is undecidable. And my second question is that how DCFL is decidable if it are not closed under union, and have decidable universality. I don't want any concrete proof, I just need to understand the intuition which is brief.

Answer 1

Here are two statements that are true about context-free grammars:

1. The union of context-free languages is context-free.
2. You can't decide whether a context-free language accepts all strings.

The clever part of the proof is showing that the following is also true:

3. If $G$ is any context-free grammar, you can make two new languages $G_1$ and $G_2$ based on $G$ with the following properties:

   3a. $G_1$ and $G_2$ are context-free.

   3b. If $G$ accepts all strings, then $G_1\cup G_2$ is regular. Otherwise, $G_1\cup G_2$ is non-regular.
   I won't explain the definition of $G_1$ and $G_2$ in detail; just ask you to accept their properties for now.

Taking these statements as given, the proof is intuitively like this:

• Assume you have the power to decide whether any context-free language is regular.
• Given any grammar $G$, form the grammars $G_1$ and $G_2$ using the procedure in (3).
• By (3a), $G_1$ and $G_2$ are context-free.
• So, by (1), their union $G_1 \cup G_2$ is context free.
• By your assumption, you have the power to decide whether $G_1\cup G_2$ is regular.
• By construction (3b), $G_1\cup G_2$ is regular if and only if $G$ accepts all strings.
• Therefore, you have the power to decide whether any context-free language $G$ accepts all strings.
• This is impossible, per (2). So the assumption was wrong—you can't actually decide whether any context-free language is regular.
• The problem of deciding regularity for CFLs is undecidable, Q.E.D.

---

Please note

Please note that the properties (1) and (2) don't directly imply that the problem is undecidable. Instead, we had a clever construction (3) that used those properties to help show a contradiction. If we had invented a different construction than the one in (3), we might have used different properties than (1) or (2).

Answer 2

First answer's of @user326210 was also good intuition.I just paste the @user326210 deleted answer.

If you can decide whether a CFG is regular, then you can decide whether a CFG accepts all strings.

Give me a CFG $G$. You want to know if the language of $G$ is regular. Let me define two useful new languages (for example, I can write down a context-free grammar for them).

• $L_1$ is the language $\{a^mb^n\# w : m,n\geq0, w\in L(G)\}$. Meaning it consists of strings of the form "Any number of a's followed by any number of b's followed by #, followed by a word that is accepted by your grammar $G$."
• $L_2$ is the language $\{a^kb^k \# w : k\geq 0, w\in\Sigma^*\}$. Meaning it consists of strings of the form "A string of an equal number of a's and b's, followed by #, followed by any word."

Notice the following key facts:

1. $L_1$ and $L_2$ are context free. (Think about how you would write down a grammar for them in terms of the grammar $G$.)

2. If your grammar $G$ accepts all strings, then $L(G)=\Sigma^*$, so the union of $L_1\cup L_2$ is just "Any number of a's followed by any number of b's followed by # followed by any word." This is a regular language.

3. If your grammar $G$ doesn't accept all strings, then the union $L_1 \cup L_2$ will not be regular. Intuitively, you need to decide whether the left side of the string is $a^kb^k$ (so it belongs to $L_2$) and/or whether the right half of the string is in $L(G)$, a context-free language. You can't use a regular language to do it.

4. So the language $L_1 \cup L_2$ is regular if and only if the language $L(G)$ accepts all strings.

5. So if you can decide whether a context-free language is regular, you can take any grammar $G$, quicky write down the corresponding grammar for $L_1\cup L_2$, and use your decider to determine whether $L_1 \cup L_2$ is regular. If it is, then $G$ accepts all strings. Otherwise,$G$ rejects some strings.

6. We said it was impossible to decide whether a CFG accepts all strings. Deciding whether a CFG is regular gives you the power to decide whether a CFG accepts all strings. Therefore, it is impossible to decide whether a CFG is regular.