# DFA containing substring to not containing substring by flipping acceptability of all states?

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?

• 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). Jan 30, 2021 at 8:18
• DFAs don't contain substrings. Oct 28, 2021 at 5:45

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)$$
• 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.