# Decidable Problem

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?

• – Ran G. May 12 '15 at 0:53

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.