91Ó°ÊÓ

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.

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 $∑$:

• On repeatedly generating all possible string in lexicographical order from $\stackrel{*}{∑}$.
• Consider each string generated above as ‘w’, we will check if $w∈L\left(G_1\right)$and $w∉L\left(G_2\right)$or $w∉L\left(G_1\right)$and $w∈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)≠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)≠L\left(G_2\right)$and this is also recognizer for $E{Q}_{CFG}\text{'}$. Thus M is co turning recognizable.