Building automaton from regular expression

Question

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?

Answer 1

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.