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
- do not end up in an accepting state and maybe even begin with an accepting state or
- 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.
