848 views
3 votes
3 votes

1 Answer

Best answer
9 votes
9 votes

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.

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

edited by

Related questions

4 votes
4 votes
2 answers
1
Kai asked Jan 29, 2017
719 views
When a Multi-tape TM of time complexity T(N) is reduced to a single tape turing machine, the complexity can go upto?
3 votes
3 votes
2 answers
3
3 votes
3 votes
2 answers
4