GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
72 views
If M is a turing machine and Language accepted by that turning machine is L(M) such that L is regular language. Whether this Statement is decidable or undecidable?
asked in Theory of Computation by (119 points)   | 72 views
Undecidable. But It is recognizable (R.E)
it is neither decidable nor Recursively enurable
Right. If it were something like "L is a Regular Language and accepts regular sets", this would be a R.E, right? Because it can have a 'yes' ?

1 Answer

+2 votes
Best answer

$T_{yes}=\phi$

$T_{no}=0^{n}1^{n}$

using Rice theorem $2$,

Any non-monotonic property of the LANGUAGE recognizable by a Turing machine is unrecognizable 

non-monotonic property Holds as -:

$T_{yes}\subset T_{no}$

Hence is is not turing recognizable , so no chance of its decidablity.

answered by Veteran (10.6k points)  
selected by
(1) L(M)L(M) has at least 10 strings

We can have TyesTyes for Σ∗Σ∗ and TnoTno for ϕϕ. Hence, L={M∣L(M) has at least 10 strings}L={M∣L(M) has at least 10 strings} is not Turing decidable (not recursive). (Any other TyesTyes and TnoTno would also do. TyesTyes can be any TM which accepts at least 10 strings and TnoTno any TM which doesn’t accept at least 10 strings )

 

 

how this is not turing decidable

iunderstood the monotonic property ( part 2)

but not clear with PaRT 1

@sourav

@A_i_$_h

A language is decidable iff it is Recursive(i.e indirectly CSL,CFL,RL)

There is no point of arguing that a language which is not even RE will decidable or not !?

 

y its  is not RE ?
@sourav A language is decidable iff it is recursive -- not all r.e. languages are decidable.
@arjun sir, Thanks! I missed it.Updated!


Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2058 Points

  5. A_i_$_h

    1990 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,037 questions
33,646 answers
79,693 comments
31,069 users