Which of the folowing are R.E

Question

Which of the following problem(s) is/are Recursively enumerable or its complement is recursively enumerable?

I. The language of all Turing machines that accept nothing.

II. The language of all Turing machines that accept everything.

III. The language of all CFG’s that are ambiguous.

Comments

https://stackoverflow.com/questions/46140969/how-is-turing-machine-which-accepts-nothing-is-not-recursively-enumerable

Answer 1

1. $L_1 = \left\{\langle M \rangle \mid L(M) = \phi \right\}$

2. $L_2 = \left\{\langle M \rangle \mid L(M) = \Sigma^* \right\}$

3. $L_3 = \left\{\langle G \rangle \mid G \text { is ambiguous }\right \}$

All 3  languages are not recursive. 

$L_1$ and $L_2$ are not even recursively enumerable.

$L_1$ not being recursively enumerable can be proved by Rice's theorem part 2 using $T_{yes}$ and $T_{no}$ such that $L(T_{yes}) = \phi$ and $L(T_{no}) = \{a\}$ (any non-empty set) thus $L(T_{yes}) \subset L(T_{no})$.

Proof for $L_2$ being not recursively enumerable is shown here.  

${L_1}'$ is recursively enumerable as here we can fed the TM all strings from the language and as long as it is accepting a string, we are guaranteed to stop at some point.

${L_2}'$ is not even recursively enumerable. Again we can use Rice's second theorem for this using $T_{yes}$ and $T_{no}$ such that $L(T_{yes} = \phi$ (any set other than $\Sigma^*$ would do) and $L(T_{no}) = \Sigma^*$  thus $L(T_{yes}) \subset L(T_{no})$. 

Proof for $L_3$ being undecidable can be done by reduction from Post Correspondence Problem. But ${L_3}$ must be recursively enumerable as here we have to check if a given grammar is ambiguous- we can take each word from $L$ and see if multiple parse tree exists- as long as grammar is ambiguous, we will eventually get a word for which there are multiple parse trees.  $L_3$ being recursively enumerable but not recursive would mean ${L_3}'$ is not recursively enumerable. 

Comments

Hello sir

I think L₁^'=L₂   and you claimed L2 to be not RE and L₁^' to be RE.

please check.

---

L3 must be recursively enumerable as here we have to check if a given grammar is ambiguous- we can take each word from LL and see if multiple parse tree exists- as long as grammar is ambiguous, we will eventually get a word for which there are multiple parse trees.

@Arjun sir,

what does this word eventually means here ??.....since the language is infinite, that string(which give multiple parse tree) could be at the end, but that end we can not imagine since language is infinite...

so how could we say that it will accept that ambigous language in finite time??

in more simple language, can we say that within 2 days or 3 days...this particular language(given that it is ambigous) will be accepted....and also assuming that TM will countinously run??........i dont think so because that particular string which give multiple parse tree could be found on 4th day, or 5th day......so on(though it will be definately found on some day)......so we can not put upper bound on time of accetpance, so how the language is recursively enurable??

---

@joshi_nitish

We can design our Turing machine in such a way that for each word in the language it will try to generate two parse tree. If there exists such a word in the language then our Turing machine generate two parse tree of it and accept the language.

Now your doubt is what if such a word is present in the end of the language and language can be infinite.

How much at the end this word will be present.?
You gave me such a word. I will input the word into my Turing machine in lexicographical order. After rejecting all those words for which no two parse tree possible. We will get to that word in some finite time.

Now you can argue that it will take a lot of time to reach that word. It is not a problem at all. But still, if you feel that it will take a lot of time we can design our Turing machine, in such a way that for each word it will run one step, in lexicographical order. To know more about it please see these links (Enumeration process of RE language).

https://gateoverflow.in/120/gate2003-15?show=97256#a97256

https://gateoverflow.in/?qa=blob&qa_blobid=7955873120759532505

Now this language is not recursive, because what if we don't have such a word in our language (for which we don't have two parse tree). Then our Turing machine keeps executing forever.