retagged by
2,067 views
6 votes
6 votes
Consider the following languages-

L1={<M>| there exists x,y belonging to (sigma*) such that either x belongs to L(M) or y does not belong to L(M)}.

Answer- Recursive, This is the language of all turing machines

L2={<M1,M2>| L(M1) < L(M2)}

Answer- Not even recursively enumerable.

Arjun sir plzz explain these languages.
retagged by

1 Answer

Best answer
6 votes
6 votes
L1={<M>| there exists x,y belonging to (sigma*) such that either x belongs to L(M) or y does not belong to L(M)}.
 

Lets analyze the condition. We should have 2 strings in $\Sigma^*$ such that at least one of them must be in $L(M)$ or in its complement. For any string in $\Sigma^*$ it belongs to either $L(M)$ or its complement and hence this condition is always true. So, L1 is same as saying

{<M>| earth is round or earth is not round}

The most important part in such questions is the condition given inside the set notation - even a single letter there can change the language a lot.
selected by

Related questions