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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.