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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.