M0 = TM

L2 = {<A> | A = DFA, L(A) = L(Mo)}

Why L2 is decidable?

Can you please tell us the basic idea of it's TM?

Since M0 is a constant, we know its' language and we know that in order for L2 not to be empty L(M0) has to be a regular language.

So, now we are left with the question if a given DFA A has the same language as L(M0), since both languages are regular we saw an algorithm to compare if they are equal or not (check that each one is a subset of the other)

First of all, if L(M0) is not regular, then clearly L2 is empty and decidable.

Else, L2 contains all the DFA's A, whose language is equivalent to some regular language, this is also decidable (since checking whether two DFA's languages are equal is decidable).

In any case, L2 is decidable.

Edit: Peter beat me to the answer

I can't understand /:

I still can't find the TM that decides L2.

I tried this:

On input (<A>):

if L(Mo) regular: return L(A) == L(M) #(checking whether two DFA's languages are equal)

else : reject # (L2 is empty)

but deciding if L(M0) regular or not may loop…

If i knew what was L2 - It was easy, but i don't..

can you please write for me the TM that decides L2 ?

Your algorithm is correct.

Please notice that given a language L, the question whether it's regular is decidable (and doesn't "loop") since one of the following decides it:

1. on input x: accept

2. on input x: reject

Yes, you DON'T need to know WHO decides it. It's sufficient that you know that there exists some such algorithm. Notice that, in contrast, for the HALTING problem, for instance, you can't list a set of algorithm that one of which decides it, for cardinality reasons (too few TMs: only Alef zero) , as seen in class.

Notice that the algorithms I mentioned above decide what we need, since one formal definition of our problem can be:

{x in Sigma* : L is regular}

(this means that we have two "not related" things in the definition of the class: some x, and some requirement on L)