Show that $\mathit{E}{\mathit{Q}}_{\mathbf{C}\mathbf{F}\mathbf{G}}$ is undecidable.

Any problem whose corresponding Turing Machine never halt to answer ‘YES’ or ‘NO’ is known as Undecidable. So for such problem, we cannot create an algorithm which gives the result in infinite time.

In order to prove that $E{Q}_{CFG}$is undecidable, we will reduce our desired result from $AL{L}_{CFG}$.

$AL{L}_{CFG}$is defined as:

$AL{L}_{CFG}=\left\{⟨G⟩\right|G\text{isa}CFG\text{and}L\left(G\right)={\sum }^{*}\}$

By contraction method, $AL{L}_{CFG}$is undecidable.

Let assume:

$E{Q}_{CFG}=\left\{(G_1,G_2)\right|G_1\text{and}{G}_2$

are $CFGs$such that $L\left(G_1\right)=L\left(G_2\right)\}$

Here,

$CFG=\text{ContestFreeGrammar}$

$G_1\text{and}{G}_2=\text{Grammar}1\text{andGrammar}2\text{respectively}$

$L\left(G_1\right)=\text{Languagefor}{G}_1$

$L\left(G_2\right)=\text{Languagefor}{G}_2$

Let, $R=\text{Deciderfor}E{Q}_{CFG}$

So by the use of R, construct Decider S for $AL{L}_{CFG}$by following steps:

S: By input where G is the Context Free Grammar on the set of terminals :

• Let $G_1$is Context Free Grammar that have S as starting non-terminal for which every follow the rule $S\to aS$and $S\to \in \left(\text{terminal}\right)$and $L\left(G_1\right)=\sum ^{*}$i.e., language L of Grammar $G_1$contain all the strings in $\sum$.
• Execute R on
• If R got accepted then S will also be “accepted”

Else

If R got rejected then S will also be “rejected”.

This clearly shows that S is a decider for $AL{L}_{CFG}$. But S doesn’t exist as $AL{L}_{CFG}$is undecidable, so our assumption is contradicted.

Hence conclude that $E{Q}_{CFG}$is undecidable by using the result that $AL{L}_{CFG}$ is undecidable.