TIFR CSE 2014 | Part B | Question: 14

Question

Which the following is FALSE?

• A. Complement of a recursive language is recursive.
• B. A language recognized by a non-deterministic Turing machine can also be recognized by a deterministic Turing machine.
• C. Complement of a context free language can be recognized by a Turing machine.
• D. If a language and its complement are both recursively enumerable then it is recursive.
• E. Complement of a non-recursive language can never be recognized by any Turing machine.

Comments

Why is D incorrect my reasoning is that recursively enumerable languages do not have a complement.So what is the complement of a recursively enumerable language?

Isn't Recursively Enumerable superset of Recursive so how does its complement become recursive.

Please correct my reasoning,so that this misconception is eliminated.

---

@sripo

U can use the fact that recursive languages are closed under the compliment and every recursive language is recursively enumerable.

If u r saying that if a language and its complement is recursively enumerable, then it means u want to say that Even recursively enumerable languages are closed under complement and if this is true then there will be no difference between recursively enumerable and recursive languages, I mean the same set can represent both languages and  So language will become recursive..

---

$A:true$

$B:true$

$C:true$

$D:true$

$E:false$

Image for D

---

Note: A language is Recursively enumerable (RE) but not recursive (REC) then it complement is non-RE.

---

option E is false.

Answer 1

• A. True. For a recursive language, we have a TM which says for any string "w", "yes" if it belongs to the language and "no" if it does not. For the complement of a recursive language we just have to reverse 'yes' and 'no' conditions and this is possible with a slight modification to the original TM. So, the new language is also recursive.
• B. True. Non-determinism does not add any recognizing power to a Turing machine though it can affect the time complexity in solving a problem.
• C. True. Complement of CFL is recursive. and recursive language is recognized by Turing machine. So, complement of a context free language can be recognized by TM
• D. True. If a language is r.e., we have a TM which says "yes" whenever a given string belongs to L. Similarly, if its complement is r.e., we have a TM which says "yes", whenever a string does not belong to the language. So, combining both we can always say "yes" if a string belongs to the language and "no" if a string does not belong to L $\implies$ L is recursive.
• E. False.
  Non-recursive Language can be:- (a) r.e. or (b) Non r.e.
  As seen in option D, if the language is RE but not recursive, its complement cannot be r.e. (recognized by a TM). But, if the language is not r.e. its complement may be r.e. (which Can be recognized by TM).  option E is false.
  Example:- 
  $L=\{\langle M,w\rangle \mid M \text{ is a TM and it does not halt on string } w\}.$ //Non RE (complement of halting problem)
  $L^c=\{\langle M,w \rangle \mid M \text{ is a TM and it halts on string } w\}$ //RE but not Recursive //recognized by TM (halting problem)

So, answer is (E).

Comments

@Srivathsa   I guess your assumption is wrong; the Turing machine does read epsilon.

https://gateoverflow.in/83694/turing-machine

---

Thank u very much @Aadesh i did not know that

---

As seen in option D, if the language is RE but not recursive, its complement cannot be r.e. (recognized by a TM).

 

If language is RE its complement MAY OR MAY NOT be RE should be the correct statement, right?

Answer 2

According to me
Option C and Option E both are false.
As TM cannot recognise epsilon, complement of a CFL can have epsilon.