559 views

Use Rice's Theorems here
edited
How?plz explain.

I get that it's not decidable but how is it semidecidable
Had this Question been set properly, answer would be $D.$

If someone knows even only the basic definitions of Automata Theory, will realize How Poorly this question has been constructed.

Now coming to the Question, Why is it Poorly constructed?

$L$ is the set of all Regular languages over some alphabet, say $\{ 0,1\}.$ So, $L$ itself is NOT a language But a collection of languages. A Language is a set of Strings over some Alphabet. What is a string in $L$ ? What is the alphabet of $L$ ?

So, Now you know what is Wrong with this Question. Whoever set this Question has very poor knowledge of Automata Theory.

Now let me change this Question and make it a valid one.

Consider $<M>$ be the encoding of a Turing Machine as a string over alphabet $Σ = \{0, 1\}$

$L = \{ <M> | L(M) \,\, is \,\, Regular\}$

Now this language $L$ is Non-RE language.

We can prove it using Rice's Theorem.

Property $P(L) = L \,\, is\,\, Regular$ is Non-trivial and Non-monotonic Property of RE languages. And by Rice's Theorem we know that Any Non-trivial and Non-monotonic Property of RE languages is Undecidable and Unrecognizable.

Hence, $L$ is Not-RE.

### 1 comment

Nice explanation.thanks a lot

1
575 views