edited by
7,488 views
25 votes
25 votes

Which the following is FALSE?

  1. Complement of a recursive language is recursive.
  2. A language recognized by a non-deterministic Turing machine can also be recognized by a deterministic Turing machine.
  3. Complement of a context free language can be recognized by a Turing machine.
  4. If a language and its complement are both recursively enumerable then it is recursive.
  5. Complement of a non-recursive language can never be recognized by any Turing machine.
edited by

2 Answers

Best answer
29 votes
29 votes
  1. 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.
  2. True. Non-determinism does not add any recognizing power to a Turing machine though it can affect the time complexity in solving a problem.
  3. 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
  4. 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.
  5. 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).
edited by
0 votes
0 votes
According to me
Option C and Option E both are false.
As TM cannot recognise epsilon, complement of a CFL can have epsilon.
Answer:

Related questions