The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
75 views

how to solve  this ques [email protected] Gupta 2

asked in Theory of Computation by Junior (605 points) | 75 views
0
0
Both are NOT RE. So, Answer D.
0
+1
Thanks Prashant Sir and Deepak Bhaiyya..I forgot to think of the non recognizability

1 Answer

0 votes

Answer : D


Quick Revision :

Rice's Theorem Part 1 (For some undecidable languages) :

We know by Rice's theorem that "Any non-trivial property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is undecidable". 

For a property of recursively enumerable set to be non-trivial, there should exist at least two recursively enumerable languages, (hence two Turing machines), the property holding for one ($T_{yes}$ being its TM) and not holding for the other ($T_{no}$ being its TM).

Thus, as per Rice’s theorem the language describing any nontrivial property of Turing machine is not recursive. It can either be recursively enumerable or not recursively enumerable. 

Rice's Theorem Part 2 (For some unrecognizable languages) :

Any non-monotonic property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is unrecognizable.  

For a property of recursively enumerable set to be non-monotonic, there should exist at least two recursively enumerable languages (hence two Turing machines), the property holding for one ($T_{yes}$ being its TM) and not holding for the other ($T_{no}$ being its TM) and the property holding set (language of $T_{yes}$) must be a proper subset of the set not having the property (language of $T_{no}$).

https://gatecse.in/rices-theorem/


1. $REG = \left \{ M \,\,| \,\,L(M) \,\,is\,\, Regular \right \}$

It is Non-trivial property of Turing Machines because Not every RE language is Regular. You could have two TM $M_1$ and $M_2$ such that $L(M_1)$ is Regular whereas $L(M_2)$ is Non-regular. Hence, The given language $REG$, by Rice's theorem part 1, is Undecidable(i.e. Not REC)

Moreover, "$L(M)$ is Regular"   is a Non-monotonic property. Because you could give Two TM $M_{yes}$ and $M_{no}$ such that $L(M_{yes})$ is Regular, say, $L(M_{yes}) = \phi$ and $L(M_{no})$ is Non-regular, say, $L(M_{no}) = ww$ and We can see that $L_{yes} \subset L_{no}$. Hence, The given language $REG$, by Rice's theorem part 2, is Unrecognizable (NOT RE)


2. $Co-Reg$ $= \left \{ M \,\,| \,\,L(M) \,\,is\,\, Non-Regular \right \}$

It is Non-trivial property of Turing Machines because Not every RE language is Non-Regular. You could have two TM $M_1$ and $M_2$ such that $L(M_1)$ is Regular whereas $L(M_2)$ is Non-regular. Hence, The given language $Co-REG$, by Rice's theorem part 1, is Undecidable(i.e. Not REC)

Moreover, "$L(M)$ is Non-Regular"   is a Non-monotonic property. Because you could give Two TM $M_{yes}$ and $M_{no}$ such that $L(M_{yes})$ is Non-Regular, say, $L(M_{yes}) = ww$ and $L(M_{no})$ is Regular, say, $L(M_{no}) = \Sigma^*$ and We can see that $L_{yes} \subset L_{no}$. Hence, The given language $Co-REG$, by Rice's theorem part 2, is Unrecognizable (NOT RE)

answered by Boss (19.4k points)
edited by

Related questions

0 votes
1 answer
2
asked Oct 23 in Theory of Computation by Balaji Jegan Active (3.1k points) | 21 views
0 votes
1 answer
5
0 votes
1 answer
6
asked Oct 3 in Theory of Computation by Mudita (49 points) | 30 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,574 questions
48,563 answers
155,439 comments
63,582 users