+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?
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' ?

$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.

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!

+1 vote