Decidability

Question

Let M1 be a Turing machine and M2 be a finite automaton. Is the problem, whether M1 and M2 accept the same language decidable?

An elaborative answer with proof is most welcome.

Comments

no it can never be decidable

It is a undecidable problem

---

Only if both are finite , then only it will be decidable

Answer 1

The problem can be stated differently as:

$$REGULAR_{TM} = \{ < M > | \,\text{M is a TM and L(M) is a regular languauge}\}$$
This can be proven to be undecidable by a reduction from $A_{TM}$. You can look up the proof online - it's fairly easy.

Another way to prove it would be to use Rice's theorem - the property of being regular is non-trivial and as a consequence of that, the given language is undecidable.

Comments

I think if both L1 and L2 are finite, then only it will be decidable

---

Yes, testing equivalence of DFAs is a decidable problem, which can be proved using closure properties.

---

Finite, regular and even DCFL equivalence is decidable .

---

Sir u mean if L1 and L2 if both DCFL?

If L1 is DCFL, then (L1)' also be DCFL. That is true

But how it satisfies $L_{1}=L_{2}$??

Plz explain more .

---

@srestha-This might help.

https://cs.stackexchange.com/questions/60052/decidability-of-halting-problem-for-dpdas-with-epsilon-transitions

---

Can I prove it like this

Suppose the given problem was decidable(using an algorithm A) then if $L(M_2)=\sum^*$ so

$L(M_1)=\sum^*$ would have been decidable stating that we have membership algorithm for RE languages and consequently then every RE language would have been REC!! Multiple contradictions!!

Answer 2

$REGULAR_{TM} = \{ < M > | \,\text{M is a TM and L(M) is a regular language}\}$

This is a non-trivial property of language accepted by TM because not every RE language is Regular. There can be 2 TM $M_1$ and $M_2$ where $M_1$ recognizes a regular language but $M_2$ does not. Hence the given language is Undecidable.

Also, "L(M) is Regular"  is a Non-monotonic property. Because you could give Two TM $M_{yes}$ and $M_{no}$ such that $L(M_{yes})$ is Regular, say, $L(M_{yes}) = ϕ$ and $L(M_{no})$ is Non-regular, say, $L(M_{no})=ww$ and We can see that $L_{yes} \subset L_{no}$. Hence, the given language, by Rice's theorem part 2, is Unrecognizable (NOT RE)