Creating a minimal dfa from a regular expression

Question

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)$?

Answer 1

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.