1,094 views

1 Answer

Best answer
3 votes
3 votes

It is a property of language of Turing machines (recursively enumerable languages),

Using Rice's theorem, there exists Turing Machine $T_{yes}$ for $L=\{a, aab\}$ and Turing machine $T_{no}$ for $L=(a+b)^*$ and also $L(T_{yes}) \subset L(T_{no})$, making the property non-trivial as well as non-monotonic.

Hence, the above language is not recursively enumerable as per Rice's theorem part 2.

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

selected by

Related questions

0 votes
0 votes
0 answers
1
Sparsh-NJ asked Aug 6, 2023
219 views
If G is a CFG then L(G) = (Sigma)* is Decidable or Undecidable?The reference where I solved this question says this is an Undecidable problem! But I think it's Decidable ...
0 votes
0 votes
0 answers
2
jatin khachane 1 asked Jan 8, 2019
701 views
L1 = { <M | M halts on $\epsilon$ }L2 = { <M | $\epsilon$ $\in$ L(M) }Which one is RE or not RE
1 votes
1 votes
0 answers
3
srestha asked Dec 6, 2018
369 views
Where can we apply PCP to check, if the grammar is undecidable?Some examples of such grammars Ambiguous grammarAny other example and how they solved with PCP?