Undecidability of CFL Equivalence

1. Why is $E{Q}_{CFG}$ Harder Than $E{Q}_{DFA}$?

Let's start by recalling a problem we've already solved. In a previous module, we showed that the equivalence problem for DFAs ($E{Q}_{DFA}$) is decidable. Why can't we just use the same method for CFGs?

The solution for DFAs was constructive. Given two DFAs, $A$ and $B$, we could construct a third DFA, $C$, that accepted the symmetric difference of their languages:
$L(C)=(L(A)\cap \overline{L(B)})\cup (\overline{L(A)}\cap L(B))$
The languages $L(A)$ and $L(B)$ are equivalent if and only if $L(C)$ is empty. Since emptiness is a decidable problem for DFAs, we could decide equivalence.

This entire strategy hinges on the fact that regular languages are closed under complement ($\overline{L}$), intersection ($\cap$), and union ($\cup$).

This is where the strategy breaks down for Context-Free Languages.

As the notes explain, CFLs are not closed under intersection or complement. A classic example is:

• $L_1=\{a^n{b}^n{c}^m\mid n,m\ge 0\}$ is a CFL.
• $L_2=\{a^m{b}^n{c}^n\mid m,n\ge 0\}$ is also a CFL.
• But their intersection, $L_1\cap L_2=\{a^n{b}^n{c}^n\mid n\ge 0\}$, is the canonical example of a language that is not context-free.

Since we cannot reliably construct a CFG for the symmetric difference, we need a completely different approach to assess the decidability of $E{Q}_{CFG}$. This leads us back to our powerful tool: proof by reduction.

2. The Undecidability of $E{Q}_{CFG}$

We will prove that $E{Q}_{CFG}$ is undecidable using a two-step reduction:

1. First, we'll show that the Universality Problem for CFGs ($AL{L}_{CFG}$) is undecidable.
2. Then, we'll show that $AL{L}_{CFG}$ reduces to $E{Q}_{CFG}$.

This establishes the chain of reasoning: $A_{TM}{\le }_{m}AL{L}_{CFG}{\le }_{m}E{Q}_{CFG}$. Since $A_{TM}$ is undecidable, $E{Q}_{CFG}$ must also be undecidable.

Step 1: The Universality Problem ($AL{L}_{CFG}$) is Undecidable

The universality problem asks whether a given CFG generates all possible strings over its alphabet:
$AL{L}_{CFG}=\{⟨G⟩\mid G\text{ is a CFG and }L(G)={\Sigma }^{\ast }\}$
To prove this is undecidable, we will reduce $A_{TM}$ to it. The core of the reduction is this: for any Turing Machine $M$ and input $w$, we will construct a CFG, $G$, that generates the language of all strings that are NOT an accepting computation history of $M$ on $w$.

To formalize this, let's first define a computation history.

The logic of the reduction is as follows:

• If $M$ accepts $w$: There is exactly one accepting computation history. Our constructed grammar $G$ generates every string except this one. Therefore, $L(G)\ne {\Sigma }^{\ast }$.
• If $M$ does not accept $w$: There is no accepting computation history. Therefore, the set of non-accepting computation histories includes all strings. Thus, $G$ generates everything, and $L(G)={\Sigma }^{\ast }$.

So, $L(G)={\Sigma }^{\ast }$ if and only if $M$ does not accept $w$. A decider for $AL{L}_{CFG}$ could be used to decide $A_{TM}$ (by inverting the answer). Since $A_{TM}$ is undecidable, $AL{L}_{CFG}$ must be too.

The ingenious part, as described in the notes, is how a CFG (or more intuitively, a PDA) can generate this language. A string fails to be an accepting computation history if:

1. It doesn't start with the correct initial configuration.
2. It doesn't end in an accepting configuration.
3. An intermediate configuration $C_i$ does not correctly yield $C_{i+1}$.

A PDA can nondeterministically guess which of these flaws a string has. Checking the start and end configurations is easy. The brilliant trick is checking the intermediate transitions. By representing the history as #C1#C2^R#C3#C4^R..., a PDA can use its stack to compare $C_i$ with $C_{i+1}^R$ (the reverse of the next configuration) to see if a valid TM transition occurred. Your experience designing complex systems with validation rules might give you an appreciation for this "local flaw detection" approach. The PDA only needs to find one flaw to accept the string as a "non-accepting history."

Step 2: Reducing $AL{L}_{CFG}$ to $E{Q}_{CFG}$

Now that we have established that $AL{L}_{CFG}$ is undecidable, the final step is surprisingly straightforward. We will show that if we could decide $E{Q}_{CFG}$, we could decide $AL{L}_{CFG}$.

Here is the argument in text:

Assume you have a decider for $E{Q}_{CFG}$, let's call it decider_E. We can use it to build a decider for $AL{L}_{CFG}$, let's call it decider_A.

decider_A on input $⟨G⟩$:

1. Construct a simple CFG, $G_{all}$, that is known to generate ${\Sigma }^{\ast }$. For an alphabet $\Sigma =\{a,b\}$, $G_{all}$ could have the single rule $S\to aS|bS|ϵ$.
2. Run decider_E on the input pair $⟨G,G_{all}⟩$.
3. If decider_E accepts, it means $L(G)=L(G_{all})={\Sigma }^{\ast }$. So, decider_A accepts.
4. If decider_E rejects, it means $L(G)\ne L(G_{all})$, which implies $L(G)\ne {\Sigma }^{\ast }$. So, decider_A rejects.

We have successfully built a decider for $AL{L}_{CFG}$. But we just proved that $AL{L}_{CFG}$ is undecidable. This is a contradiction. The only flawed assumption was that decider_E exists.

Therefore, $E{Q}_{CFG}$ is undecidable.

3. Recognizability and $E{Q}_{CFG}$

We've answered the question of decidability, but we can go one step further. Is $E{Q}_{CFG}$ Turing-recognizable? What about its complement?

Let's look at the complement, $\overline{E{Q}_{CFG}}$, which is the language of pairs of CFGs that generate different languages.
$\overline{E{Q}_{CFG}}=\{⟨G_1,G_2⟩\mid L(G_1)\ne L(G_2)\}$

If two languages are different, there must be at least one string $w$ that is in one but not the other. This string acts as a "witness" to their inequality. We can search for such a witness.

The recognizer for $\overline{E{Q}_{CFG}}$ works as follows:

1. Take as input $⟨G_1,G_2⟩$.
2. Systematically generate every possible string $w$ over the alphabet $\Sigma$.
3. For each string $w$, use the decider for $A_{CFG}$ (the membership problem for CFGs, which is decidable) to check if $w\in L(G_1)$ and if $w\in L(G_2)$.
4. If the answers differ for any $w$, then we have found our witness. Accept.
5. If the answers are the same, continue to the next string.

If $L(G_1)\ne L(G_2)$, this recognizer will eventually find a witness string and halt. If $L(G_1)=L(G_2)$, it will run forever. This perfectly fits the definition of a Turing-recognizable language.

So, $\overline{E{Q}_{CFG}}$ is recognizable. Now, recall a key theorem:

A language is decidable if and only if it is Turing-recognizable and its complement is also Turing-recognizable.

We already proved that $E{Q}_{CFG}$ is undecidable. Since its complement, $\overline{E{Q}_{CFG}}$, is recognizable, it must be the case that $E{Q}_{CFG}$ itself is not Turing-recognizable.

Conclusion

This lesson marks a significant point in our study of computability. We've moved beyond problems directly about Turing Machines and used the principle of reducibility to uncover a fundamental limitation in the realm of context-free languages, a cornerstone of compiler design and parsing.

Key Takeaways:

• The equivalence problem for Context-Free Grammars ($E{Q}_{CFG}$) is undecidable.
• The proof strategy involves a reduction from $A_{TM}$ via the undecidable universality problem for CFGs ($AL{L}_{CFG}$).
• The proof for $AL{L}_{CFG}$ being undecidable relies on constructing a grammar that generates strings that are not accepting computation histories of a TM.
• The reduction from $AL{L}_{CFG}$ to $E{Q}_{CFG}$ is achieved by comparing the input grammar $G$ to a standard grammar $G_{all}$ that generates ${\Sigma }^{\ast }$.
• Furthermore, $\overline{E{Q}_{CFG}}$ is Turing-recognizable, which implies that $E{Q}_{CFG}$ is not Turing-recognizable.

Preview of the Next Lesson:
We have now reached the end of our exploration of what is and is not computable. In the next module, we will shift our perspective. For problems that are decidable, we will start asking a new question: how efficiently can they be solved? This will lead us into the world of computational complexity, where we will formally define concepts like time complexity, and the famous complexity classes P and NP.