1
$\begingroup$

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

DFA

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?

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.