TIFR CSE 2012 | Part B | Question: 19

Question

Which of the following statements is TRUE?

• A. Every turning machine recognizable language is recursive.
• B. The complement of every recursively enumerable language is recursively enumerable.
• C. The complement of a recursive language is recursively enumerable.
• D. The complement of a context-free language is context-free.
• E. The set of turning machines which do not halt on empty input forms a recursively enumerable set.

Answer 1

1. False. Turing recognizable language are recursive enumerable and recursive set is a proper subset of it.
2. False, Complement of r.e. need not be r.e.
3. True. Complement of recursive language is recursive and every recursive language is recursive enumerable.
4. False. Complement of CFL need not  be CFL (but is guaranteed to be a CSL).
5. False. We cannot make a Turing machine to determine if a given Turing machine does not halt on empty string (for that matter any string). But the complement  of this is r.e. (of course not recursive)

Comments

Every turning machine recognizable language is recursive enumerable...not recursive(tighest bound or closest answer)...its like type 0 grammars are recursive enumerable not recursive at first place....closest bound...

---

@arjun Sir,option e

Not halt on empty input

why yes is difficult(as empty input is of length 0)

Unable to do such question

---

How compliment of e option is RE

Tyes for phi

Tno for €*

Tyes is subset of Tno

Not RE

Answer 2

For option e)

Say L = {turning machines which do not halt on empty input}

So L' =  {turning machines which halt on empty input}

See L' is REL but not Recursive.

So L = (L')' is out of REL circle. hence option e) is false.