Question

Show that $\mathit{E}{\mathit{Q}}_{\mathbf{C}\mathbf{F}\mathbf{G}}$ is co-Turing-recognizable.

Short answer

It is proved that $E{Q}_{CFG}$ is co-Turing-recognizable

Step-by-step solution

Defining Co-Turing Recognizable

A language is considered as Co-Turing Recognizable if it is able to construct an algorithm which confirms that, if a string theoretically not exist in a language, then that algorithm also show same.

Proving EQCFG is Co-Turing Recognizable

For that $E{Q}_{CFG}$to be co-Turing-recognizable, complement of $E{Q}_{CFG}$i.e., ($E{Q}_{CFG}\text{'}$) is a Turing Recognizable.

Consider a Turing Machine M. So we define M as,

M: on the input of (G₁, G₂) where G₁ and G₂ are Context Free Grammar over alphabet $\sum$:

• On repeatedly generating all possible string in lexicographical order from $\sum ^{*}$.
• Consider each string generated above as ‘w’, we will check if $w\in L\left(G_1\right)$and $w\notin L\left(G_2\right)$or $w\notin L\left(G_1\right)$and $w\in L\left(G_2\right)$.
• If one of the above conditions is true, that means M is accepted, otherwise again check for next string w.

So, from above it can be said that will only loop if in case: $L\left(G_1\right)=L\left(G_2\right)$. But if $L\left(G_1\right)\ne L\left(G_2\right)$, then M will find a string w which is in one language but not in other language.

Hence, M accepts if and only if $L\left(G_1\right)\ne L\left(G_2\right)$and this is also recognizer for $E{Q}_{CFG}\text{'}$. Thus M is co turning recognizable.