Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. If this is homework, please add the homework tag; people will still help, so don't worry. –  Julian Kuelshammer Oct 24 '12 at 13:05

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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