Question

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

Short answer

We will show that $E{Q}_{CFG}$ is undecidable.

Step-by-step solution

Defining Undecidablity

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.

Proving EQCFG is undecidable

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.