How should I go about showing that the following problem is decidable:

            Given DFAs M1 and M2, is L(M1) ⊆ L(M2)?

What is the general strategy to prove that a problem is decidable or undecidable?

Thanks in advance.


It is decidable.

First, deciding whether the language of a DFA is empty or not is decidable (by checking if there is a path from the initial state to an accepting state).

Next, a hint:

construct a DFA that accept all the words accepted by M1 that are not accepted by M2.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.