11,279 views
37 votes
37 votes

Which of the following is true?

  1. The complement of a recursive language is recursive
  2. The complement of a recursively enumerable language is recursively enumerable
  3. The complement of a recursive language is either recursive or recursively enumerable
  4. The complement of a context-free language is context-free

5 Answers

Best answer
36 votes
36 votes

When a language is Recursive then there is a Total Turing machine means a Turing machine which have only two options either accept or rejects so if we complement a recursive language it works according to second figures hence it is recursive too. 

For a recursively enumerable language there is Turing machine and so it has three options either accept, reject or loop. Hence its complement can be either recursively enumerable or not even recursively enumerable.

Among the options A is the best one though C is also not wrong as it includes the statement of A in an either clause. 

Best Option: A

edited by
20 votes
20 votes
Complement of recursive language is always recursive.
edited by
0 votes
0 votes
If a language L and L' are both recursively enumerable then both languages are recursive.

If L is recursive then L' is  also recursive and consequently bothe are Recursively enumerable.
0 votes
0 votes
Option A) is true, The complement of a recursive language is recursive.
Answer:

Related questions

23 votes
23 votes
3 answers
1
Kathleen asked Sep 15, 2014
5,831 views
The decimal value $0.25$is equivalent to the binary value $0.1$is equivalent to the binary value $0.01$is equivalent to the binary value $0.00111$cannot be represented pr...
41 votes
41 votes
1 answer
2
Kathleen asked Sep 15, 2014
8,107 views
The language accepted by a Pushdown Automaton in which the stack is limited to $10$ items is best described asContext freeRegularDeterministic Context freeRecursive
28 votes
28 votes
4 answers
4
Kathleen asked Sep 15, 2014
6,796 views
Dynamic linking can cause security concerns becauseSecurity is dynamicThe path for searching dynamic libraries is not known till runtimeLinking is insecureCryptographic p...