edited by
2,787 views
24 votes
24 votes

Which of the following statements is TRUE?

  1. Every turning machine recognizable language is recursive.
  2. The complement of every recursively enumerable language is recursively enumerable.
  3. The complement of a recursive language is recursively enumerable.
  4. The complement of a context-free language is context-free.
  5. The set of turning machines which do not halt on empty input forms a recursively enumerable set.
edited by

2 Answers

Best answer
22 votes
22 votes
  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)
edited by
5 votes
5 votes
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.
Answer:

Related questions