recategorized by
1,798 views
3 votes
3 votes


@arjun sir please help

how is it recognizable?

recategorized by

3 Answers

Best answer
11 votes
11 votes

 

So, For this Question

  • Property P : Being a regular language
  • Property Language, $L_P = \left \{ <M> | L(M) \text{ is regular } \right \}$
  • Property SET($P$) is non empty, because  $\exists \; \text{RE} \in SET(\text{P})$ , some of them are $\left \{ \phi, \; \text{Reg Langs..} \right \}$
  • But property SET($P$) does not include all RE's, i.e. all RE's are not regular.(obvious)
  • $\therefore \phi \subset P \subset \text{RE} \Rightarrow$ P is non trivial
  • Rice theorem says $\Rightarrow$ $L_P$ is undecidable

Now is $L_P$ totally or semi-decidable ? the following corollary helps.

So, in this Qs ; $L_P$ is NOT RE

OK !  what does NOT RE means here ? It means, the task of checking regular languages one-by-one is not a computable function. Or on the other-way, there is no automated procedure to run on a TM to check regular languages .


NOTE : what is property + property SET ??

edited by
6 votes
6 votes

Actually we have the given problem which is more harder than the problem which I m mentioning below..

Let M denotes Turing machines that accepts exactly 3 strings..So this problem is not even RE as by the technique known as dovetailing also which is used for enumeration process effectively , we are not able to confirm which 3 will be the part of the language as all others need to be rejected..

Hence the given problem is even harder than the problem that language accepts a finite number(say 3) of strings..

Hence it is non RE set and hence not even partially decidable.

Hence C) is the correct answer..

0 votes
0 votes

This language is neither Turing decidable nor turing recognizable since we can establish both the non trivial property and non monotonic property hence you are right the answer should be (C) for further reference just follow this link http://gatecse.in/rices-theorem/ 
 

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
2 answers
3
agoh asked Dec 8, 2016
421 views
L= {(M)| M is a TM and there exists an input w, |w| < 100, on which M halts}. Is L decidable?Please explain.