Redirected
reopened by
1,234 views
0 votes
0 votes

Let M range over Turing machine descriptions. Consider the set REG= {M | L(M) is a regular set} and let the complement of REG be Co-REG. Which of the following is true?

(A) REG is r.e. but Co-REG is not
(B) REG is not r.e. but Co-REG is
(C) Both are r.e.
(D) None of them are r.e.

reopened by

9 Answers

Best answer
11 votes
11 votes

REG contains the set of all strings which are encodings of TM whose language is regular. So, REG is deciding a property of TM- we are lucky and can make use of Rice's theorem. 

Here we want to prove whether RE or not. (Rice's theorem part 1 won't help)

So, lets see if the property is non-monotonic so that we can apply Rice's theorem part 2. 

For non-monotonicity, language of TM satisfying the property must be a subset of language of TM not satisfying the property. So, if we take L(TMyes) = ∅ and T(TMno) = any non regular language, this proves the property is non-monotonic. So, as per Rice's theorem part 2, REG is not RE. 

Using the same technique we can prove Co-Reg is also not RE. Just take L(TMyes) = any non regular language and L(TMno) = Σ*. 

http://gatecse.in/wiki/Rice%27s_Theorem_with_Examples

selected by
5 votes
5 votes

1).  REG = {<M> | L(M) is a regular set } 

Rice second theorem can help here => 

Take Tyes = {0,1,10,01} and TNo = (0,1)*

Now, as Tyes is a proper subset of TNo , hence, making this language even not RE.

2). Complement of REG 

Apply rice second theorem again =>

Take Tyes = Any non regular language like CFL or CSL and TNo = (0,1)*

Now, again as Tyes is a proper subset of TNo , hence, making this language even not RE.

4 votes
4 votes

L(M) is a regular set is a non-monotonic property of r.e. languages and deciding any such property is not even semi-decidable making REG non r.e.

For Co-Reg, L(M) is a non regular set, which is also a non-monotonic property of r.e. languages and hence Co-Reg is also non r.e.

So, D option.

http://www.gatecse.in/rices-theorem/ 

PS: To show monotonicity of a property, we need a r.e. language which has the property and another r.e. language which does not have the property and the first one a proper subset of second. For REG these languages respectively can be the empty language and any non-regular language (just one possibility) while for C-REG these respectively can be any non-regular language and $\Sigma^*$.

edited by
2 votes
2 votes

$\text{REGULAR}_{\text{TM}} = \left \{ <M>|\text{L(M) is regular} \right \}$

$\text{REGULAR}_{\text{TM}}$ is NOT RE  

Complement of $\text{REGULAR}_{\text{TM}}$ is also NOT RE.

Proofs of both of them are very rigorous :

1. Using reduction from complement of halting problem.

2. Using reduction from diagonalization language.

References : 1.    using complement of halting problem.

2. using diagonalization language

Related questions

0 votes
0 votes
2 answers
1