retagged by
810 views
0 votes
0 votes

Let $L1$ be a recursive language, and let $L2$ be a recursively enumerable but not recursive language. Which one of the following is TRUE?

  1. $L1’$ is recursive and $L2’$is recursively enumerable.
  2. $L1’$ is recursive and $L2’$is not recursively enumerable.
  3. $L1’$ and $L2’$is recursively enumerable.
  4. $L1’$ is recursively enumerable and $L2’$is recursive.
retagged by

3 Answers

0 votes
0 votes
Option B
0 votes
0 votes
Recursive languages are closed under complementation.
But, recursive enumerable languages are not closed under complementation.
If L1 is recursive, then L1', is also recursive.
If L2 is recursive enumerable, then L2', is not recursive enumerable language.
Answer:

Related questions

1 votes
1 votes
1 answer
2
admin asked Mar 30, 2020
859 views
What is the complement of the language accepted by the NFA shown below?$\not{O}$$\{\epsilon\}$$a^*$$\{a,\epsilon\}$$1$$2$$3$$4$
0 votes
0 votes
0 answers
4
admin asked Mar 30, 2020
1,166 views
Which of the following statements is/are TRUE for an undirected graph?Number of odd degree vertices is evenSum of degrees of all vertices is evenP onlyQ onlyBoth P and QN...