Dark Mode

[closed]

284 views

2 votes

closed as a duplicate of:
What is the difference ??

*L*_{1}is recursive language*L*_{2}is recursive enumerable language- Both (a) and (b)
- Both are not recursive enumerable

please give explanation too

0

0

@Uddipto. For L1, just assume that there exists TM for L1.

Now, if we assume that TM to be M_{0}, then given any input string, it will always halt, right? i.e it will either accpet or reject the string but it will never go into infinite loop.

Now, the strings that are accepted by M_{0} is exactly the description of M i.e. M_{0} could segregate the strings that represented M by accepting them.

@Pankaj.

Rice theorem is about property languages. I will tell in simple way.

let L_{p} = {<M> | L(M) = all regular languages }

Here, L_{p} is the property language.

Now, what above description says is give me all the turing machine encodings for TM's such that TM accepts regular language.

Now, the property of language of TM is that it should be regular.

Now, simple thing to do is just make a set and include in that set all languages which should be accepted by TM's.

For example I specified,

set S = { $\epsilon$, a*, b* ,...}

Each element of S is regular language(which is the property here)

Now, L_{p} will contain TM encodings for each element of S.

Now, Rice theorem says that if S = {} or S={set of all RE} then this is trivial property else its non-trivial property.

If this is non-trivial, then L_{p} is undecidable.

Now compare this with your example. Will you be able to apply Rice theorem? No

0