1

I am unsure as how to do this because the inputs accepted on both are $\{0, 1\}$ and the states are all different, so I am unsure which sets I am subtracting. enter image description here

Like I said, if the languages are equal and I subtracted, wouldn't I get no acceptable input?

matttm
  • 92
  • Yes, if the languages turned out to be equal, or if the second properly contained the first, you’d end up with a DFA that recognizes only the empty language. That’s fine. (It doesn’t happen here, though, since $1$ is in the first language but not the second.) – Brian M. Scott Feb 18 '16 at 18:56

1 Answers1

3

HINT: You can answer the question without paying any attention to the actual languages. The trick is to use the product construction to form a DFA whose state set is the Cartesian product of the state sets of $M_1$ and $M_2$. In this case the result will be a set of $4\cdot3=12$ states:

$$\begin{array}{ccc} \langle E,M\rangle&\langle E,N\rangle&\langle E,P\rangle\\ \langle G,M\rangle&\langle G,N\rangle&\langle G,P\rangle\\ \langle F,M\rangle&\langle F,N\rangle&\langle F,P\rangle\\ \langle H,M\rangle&\langle H,N\rangle&\langle H,P\rangle\\ \end{array}$$

The idea is that state $\langle F,N\rangle$, for instance, in this new DFA that we’re constructing corresponds to being simultaneously in state $F$ of $M_1$ and state $N$ of $M_2$. This happens if you run $M_1$ and $M_2$ simultaneously, and the first input is a $0$. If the first input is a $1$, on the other hand, $M_1$ goes to state $G$, while $M_2$ stays in state $M$, so our product DFA goes to $\langle G,M\rangle$.

See if you can fill in all of the transitions so that this new DFA faithfully mimics $M_1$ and $M_2$. Then work out which of the $12$ states should be acceptor states if this new DFA is to accept $L(M_1)\setminus L(M_2)$; you want $M_1$ to end up in an acceptor state and $M_2$ to end up ... where?

Brian M. Scott
  • 616,228