The Gateway to Computer Science Excellence
+2 votes

in Theory of Computation by | 179 views
Use Rice's Theorems here
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.$

1 Answer

+7 votes
Best answer

If someone knows even only the basic definitions of Automata Theory, will realize How Poorly this question has been constructed. But what else we can expect from Ace Test Series, It is one of the worst test series available in the market, if Not the worst one itself.

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. 

by Boss
selected by
Nice explanation.thanks a lot

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
59,988 answers
94,648 users