91影视

Any problem whose corresponding Turing Machine never halt to answer 鈥榊ES鈥� or 鈥楴O鈥� 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)={鈭�}^{*}\}$

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鈫�aS$and $S鈫�鈭�\left(\text{terminal}\right)$and $L\left(G_1\right)=\stackrel{*}{鈭�}$i.e., language L of Grammar $G_1$contain all the strings in $鈭�$.
• Execute R on
• If R got accepted then S will also be 鈥渁ccepted鈥�

Else

If R got rejected then S will also be 鈥渞ejected鈥�.

This clearly shows that S is a decider for $AL{L}_{CFG}$. But S doesn鈥檛 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.