@Deepakk Poonia (Dee) is it A?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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)

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 556
- Exam Queries 551
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,894 questions

52,261 answers

182,168 comments

67,679 users