For example, $D_1 = \{ w | w$ does not contain baba as substring$\}$


For $D_1$, I would make $F_1 = \{q_4\}$.

As I tried to design $D_2$ as the complement of $D_1$ which does not have baba as a sub-string, I've found that I can make $D_2$ by inverting all the acceptability of all states, making $F_2 = \{q_0, q_1, q_2, q_3\}$, since instead of accepting, the input string is rejected upon reaching the an acceptance state of its complement $D_1$.

From this, I believe that we can get the complement of any DFA simply by accepting when $D_1$ rejects, and reject when $D_1$ accepts, meaning $F_2$ is the complement of $F_1$.

Is my generalized proof correct?

  • $\begingroup$ Have you tried proving this claim for a general DFA? Did you get stuck anywhere? (remember that in a DFA, each word has a single run). $\endgroup$ – Shaull Jan 30 at 8:18

Shortly, yes. Formally, for every DFA $\mathcal{A} = \langle \Sigma, Q, q_0, \delta, F\rangle$, define the DFA $\overline{\mathcal{A}} = \langle \Sigma, Q, q_0, \delta, F' \rangle$, where $F' = Q\setminus F$. That is, $\overline{\mathcal{A}}$ is obtained by flipping the acceptance of the states in $\mathcal{A}$. We calim the following.

Claim: $\overline{L(\mathcal{A})} = L\left(\overline{\mathcal{A}}\right)$.

Proof: for every word $w\in \Sigma^*$, we have $$ w\in L(\mathcal{A}) \leftrightarrow\\ \text{the run $r_0, r_1, \ldots, r_{|w|}$ of $\mathcal{A}$ on $w$ is such that $r_{|w|}\in F$}\leftrightarrow \\ \text{the run $r_0, r_1, \ldots, r_{|w|}$ of $\overline{\mathcal{A}}$ on $w$ is such that $r_{|w|}\in F$}\leftrightarrow \\ \text{the run $r_0, r_1, \ldots, r_{|w|}$ of $\overline{\mathcal{A}}$ on $w$ is such that $r_{|w|} \notin Q\setminus F$} \leftrightarrow \\ \text{the run $r_0, r_1, \ldots, r_{|w|}$ of $\overline{\mathcal{A}}$ on $w$ is such that $r_{|w|} \notin F'$} \leftrightarrow \\ w\notin L\left( \overline{\mathcal{A}}\right)$$

Crucial points in the construction that you should ponder about:

  • Both automata have the same structure, in particular, they have the same run over the same word $w$: can you tell where we relied on this fact?

  • The automaton $\mathcal{A}$ is deterministic (in particular, there is a single run of $\mathcal{A}$ on $w$ that determines whether $w$ is accepted or rejected): if $\mathcal{A}$ is nondeterministic, then the construction does not work. Indeed, on input word $w$, there could be two runs of $\mathcal{A}$ on $w$: $r$ which is accepting, and $p$ which is rejecting. After flipping the acceptance of states, we get that $r$ is rejecting and $p$ is accepting, and so $w$ is still accepted.


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.