# Building automaton from regular expression

Let $L=a(a+b)^*b$, a regular expression. I will try to build the automaton by the $a^{-1}L$, $b^{-1}L$ rule

1. $a^{-1}L = \{a,b\}^* b=M$.
2. $b^{-1}L=\emptyset$.
3. $a^{-1}M=b\cup\{a,b\}^*b=N$.
4. $b^{-1}M=\{\varepsilon\} \cup \{b\}\cup \{a,b\}^*b = P$

But why are the result of 3 and 4 when doing $a^{-1}M$ and $b^{-1}M$ as given?

• – D.W. Apr 21 '17 at 15:48
• @D.W. nice pdf but somewhere with easier explanation and example? – Joel Separ Apr 21 '17 at 20:07
• @JoelSepar Try John Conway's Regular Algebra and Finite Machines. – Thumbnail Apr 22 '17 at 2:29

You failed to notice that your $M$ and $N$ states are indistinguishable. Let's take a walk around the problem first.

We can express this all in regular equations, in the notation of John Conway's Regular Algebra and Finite Machines:

\begin{align} L &= a M\\ M &= a M + b P\\ P &= 1 + a M + b P \end{align}

We can see that $L$

• starts with an $a$;
• remains in $M$ for as many $a$s as you like;
• goes to $P$, the only terminal state, at the first sign of a $b$;
• stays in the terminal $P$ for as many $b$s as you like;
• returning to $M$ at the first sign of an $a$.

These equations translate immediately into a DFA. We can also solve them:

$M = a M + b P$

... has solution

$M = a^*bP$

Substituting this into

$P = 1 + a M + b P$

... we get

\begin{align} P &= 1 + a a^*bP + b P\\ &= 1 + a^*bP \end{align}

... which has solution

\begin{align} P &= (a^*b)^*\\ &= 1 + (a + b)^*bP \end{align}

Now we can solve for $M$:

\begin{align} M &= a^*bP\\ &= a^*b(a^*b)^*\\ &= (a+b)^*b \end{align}

And for $L$:

\begin{align} L &= a M\\ &= a(a+b)^*b\\ \end{align}

How do we solve the equations above? The solution to the equation

$X = \mathcal {x} + \mathcal y X$

... ,where $\mathcal {x}$ and $\mathcal {y}$ are regular expressions independent of $X$, is

$X = {\mathcal y}^* \mathcal {x}$

OK. What did you miss?

\begin{align} a^{-1}M &= b + (a + b)^* b\\ &= (1 + (a + b)^*) b\\ &= (a + b)^* b\\ &= M \end{align}

Even if you miss this, you should find out by further beheading that $M$ and $N$ are indistinguishable.