2
$\begingroup$

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$:

DFA recognizing (ab) and (ba).

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$:

An NFA that recognized the Kleene closure (ab + ba)*.

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:

The state transition table for the NFA that recognizes the regular expression (ab+ba)*.

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 DFA corresponding to the NFA that recognizes (ab+ba)*.

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

The complement of the DFA that recognizes (ab+ba)*

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.

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – sesodesa
    Mar 23, 2020 at 17:24
  • $\begingroup$ 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... $\endgroup$
    – sesodesa
    Mar 23, 2020 at 17:58
  • $\begingroup$ 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. $\endgroup$
    – amd
    Mar 23, 2020 at 19:02
  • $\begingroup$ @amd Computing the complement of a DFA is very easy, since it suffices to change the final states. $\endgroup$
    – J.-E. Pin
    Mar 23, 2020 at 22:32
  • $\begingroup$ @J.-E.Pin Building the DFA by hand in the first place is error-prone. $\endgroup$
    – amd
    Mar 23, 2020 at 22:56

1 Answer 1

1
$\begingroup$

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^*)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .