# Converting a regular expression to its complement via automata

I'm supposed to convert a regular expression $$r = (\alpha\beta + \beta\alpha)^\ast$$ into its complement via automata. I started out by first constructing the individual DFAs that recognize $$\alpha\beta$$ and $$\beta\alpha$$:

I then combined and closed these with empty transitions, in order to generate the NFA that would recognize the language $$(\alpha\beta + \beta\alpha)^\ast$$:

After this, I wrote the state transition table in order to make the $$\newcommand{\Pset}[1]{\mathit{2}^{#1}}\Pset Q$$-algorithm (a.k.a. the power set algorithm) easier to deal with. It turned out as follows:

Next I wrote out the $$\Pset Q$$-algorithm in order to turn the NFA into a DFA:

\begin{align*}\newcommand{\pa}[1]{\left( #1 \right)}\newcommand{\set}[1]{\left\{#1\right\}} \delta\pa{ \set{t_0} }^\epsilon &= \set{ t_0, a_0, b_0 }\\ \delta\pa{ \set{ t_0, a_0, b_0 }, \alpha }^\epsilon &= \set{a_1}^\epsilon = \set{a_1}\\ \delta\pa{ \set{ t_0, a_0, b_0 }, \beta }^\epsilon &= \set{b_1}^\epsilon = \set{b_1}\\ \delta\pa{ \set{a_1}, \alpha }^\epsilon &= \varnothing^\epsilon = \varnothing \\ \delta\pa{ \set{a_1}, \beta }^\epsilon &= \set{a_2}^\epsilon = \set{a_2, t_0} \\ \delta\pa{ \set{b_1}, \alpha }^\epsilon &= \set{b_2}^\epsilon = \set{b_2, t_0} \\ \delta\pa{ \set{b_1}, \beta }^\epsilon &= \varnothing^\epsilon = \varnothing \\ \delta\pa{ \set{a_2, t_0}, \alpha }^\epsilon &= \varnothing^\epsilon = \varnothing \\ \delta\pa{ \set{a_2, t_0}, \beta }^\epsilon &= \varnothing^\epsilon = \varnothing \end{align*}

The resulting DFA would look something like this:

The complement of this DFA would then be the automaton that has its accepting and non-accepting states swapped as follows:

At this stage I realized I'm missing something: the repetition resulting from $$(\cdot)^\ast$$. This DFA only recognizes the complement of $$(\alpha\beta+\beta\alpha)$$, not the complement of $$(\alpha\beta+\beta\alpha)^\ast$$. My first question then is, how do I take that into account. Second, I'm aware of how to transform linear and branching automata into regular expressions by ''eating up'' pairs of states from left to right, and concatenating or taking unions of symbols, as long as the automaton ends up in an accepting state in each of its branches. But how do I transform automata that

1. do not end up in an accepting state and maybe even begin with an accepting state or
2. are the compelement of some automaton

into a regular expressions? In my head in case 2 I should be swapping the alphabet in the transitions as well as the states, if I move along the directed graph while eliminating states... I guess if a run into an accepting state while reading a graph, I could introduce an empty string there. So for example an initial accepting state plus something else might be expressed with $$\epsilon + \cdots$$, but I'm not sure.

• I realized I missed $a_0$ and $b_0$ from both $\epsilon$-closures $\newcommand{\set}[1]{\{#1\}}\set{a_2}^\epsilon = \set{a_2, t_0, a_0, b_0}$ and $\set{b_2}^\epsilon = \set{b_2, t_0, a_0, b_0}$, but that shouldn't change things too much. Mar 23, 2020 at 17:24
• No wait, forgetting those states from $\{a_2\}^\epsilon$ and $\{b_2\}^\epsilon$ does matter... I also didn't remember to include the transitions from $\{a_1\}$ and $\{b_1\}$ to themselves via $\alpha$ and $\beta$ respectively. I wonder if there's something else I've missed... Mar 23, 2020 at 17:58
• This is why computing the complement of a DFA is best left to a computer. With even a relatively small number of states, humans tend to overlook transitions and get the diagrams wrong in other ways.
– amd
Mar 23, 2020 at 19:02
• @amd Computing the complement of a DFA is very easy, since it suffices to change the final states. Mar 23, 2020 at 22:32
• @J.-E.Pin Building the DFA by hand in the first place is error-prone.
– amd
Mar 23, 2020 at 22:56

Since typing $$\alpha$$ and $$\beta$$ is time consuming, let me take the alphabet $$A = \{a, b\}$$ instead.
Your language $$L = (ab + ba)^*$$ is the star of the prefix code $$P = \{ab, ba\}$$ and there is a standard algorithm to compute the minimal automaton of $$P^*$$ when $$P$$ is a finite prefix code. Here you get the automaton $${\cal A} = (Q, A, \cdot, 1, F)$$ with $$Q = \{0, 1, 2, 3\}$$, $$F = \{1\}$$ and the following transition function $$\begin{array}{c|c|c|c|c|} &1&2&3&0\\ \hline a&2&0&1&0\\ \hline b&3&1&0&0\\ \hline \end{array}$$ The minimal automaton of the complement $$L^c$$ of $$L$$ is obtained by changing $$F$$ to $$Q - F$$. A possible regular expression for $$L^c$$ is $$(ab + ba)^*(a + b + aaA^* +bbA^*)$$.