retagged by
962 views
4 votes
4 votes
Let L be a regular language, and R be a turing recognizable language but not acceptable language. Which of the following is possible?

a) Set of strings common in L and R' can be in not RE(where ' is a complement operation)

b)Set of strings common in L and R' can be recursive.

1) only a

2)only b

3) both

4) none
retagged by

2 Answers

Best answer
3 votes
3 votes
1. Set of strings common in $L$ and $R' = L \cap R'$.

Now recursively enumerable languages are not closed under complement- meaning the complement of a r.e. language may or may not be r.e. So, lets say it is not r.e. Now, let our regular language $L$ be $\Sigma^*$. So, we get $\Sigma^* \cap A = A$, where $A = R'$ is a not r.e. language.

2. Possible. One such case is if we take $L = \emptyset$.

So, C is the answer here.
selected by
0 votes
0 votes
L regular language . so L'  is also regular language.

now (L intersect R')=(L' union R)'=RE'  so option a right. it can be in not RE.
edited by

Related questions

2 votes
2 votes
2 answers
1
resilientknight asked Aug 2, 2016
1,272 views
A is a decision problem. If A is recursively ennumerable then there exists an algorithm which halts on every string in A.True or false.Cite with reasons.
0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4