# Creating a minimal dfa from a regular expression

Having a bit of difficult with the following question: Create a minimal dfa for the language $L(r)$ where $r = a^*\bigl((ab+b)^*\bigr)$?

-
Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. – Julian Kuelshammer Oct 24 '12 at 13:05

Let's construct any dfa for your language and then prove it's minimal. The idea of the construction is the following: Rewrite $r$ as $a^* + a^*b(ab+b)^*$. We use four states:

• $0$: the starting state, is used to absorb the $a$s at the beginning of the word we check, if we read an $a$, we stay in $0$, but if we read a $b$, we can't stay, as we have reached the second part of $r$. As words in $L$ may consist only of $a$s, $0$ is accepting

• $1$: here, we are after we have absorbed a $b$ or an $ab$, if we read a $b$, we obviously stay here, but if we read an $a$, we can't stay, as the next letter must be a $b$. As words in $L$ may end here, $1$ is accepting.

• $2$: here we are after we have read an $a$ in $1$, if we read a $b$ no, we go back to $1$, as then we have successfully absorbed an $ab$ for the second part of $r$, if we read another $a$, our word cannot be in $L$, so we go to a trash state. As a word in $L$ which contains a $b$ must not end with $a$, $2$ is not accepting

• $3$: here we are when we have read something that shows that the input is not in $L$, and we never leave $3$ therefore and it is not accepting.

This gives the following dfa $A = (\Sigma, Q, q_0, F, \delta)$:

• alphabet $\Sigma = \{a,b\}$

• states $Q = \{0,1,2,3\}$, with starting state $q_0 = 0$ and accepting states $F = \{0,1\}$

• transition function $\delta\colon Q \times \Sigma \to Q$ given by $\begin{array}{c||c|c|c|c} & 0 & 1 & 2 & 3\\ \hline \hline a & 0 & 2 & 3 & 3 \\ \hline b & 1 & 1 & 1 & 3 \end{array}$

Now we prove that no two states are equivalent, as then our dfa is minimal: First we observe that surely the pairs $(0, 2)$, $(0,3)$, $(1,2)$ and $(1,3)$ are inequivalent, as one of the states is accepting and the other is not. No we look at the remaining two pairs

• $(0,1)$ is inequivalent, as reading an $a$ yields $(0,2)$, which we know to be inequivalent

• $(2,3)$ is inequivalent, as reading $b$ gives $(1,3)$, which we know to be inequivalent

Hence $A$ is minimal.

-