Build a DFA that accepts $L(M_1)-l(M_2)$

334 Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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?