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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know that the automaton for the regular expression (a + b)* will just have one state, where the initial state = the accepting state and there is one edge going into that state labelled a,b.

Sorry, I haven't attached a diagram but my rep isn't high enough to allow that. (<10)

I just want to know, what difference is there between the automaton described above and the one for (a* + b*).

share|cite|improve this question
up vote 1 down vote accepted

For $a^*+b^*$ you’ll want four states, three of which are acceptors. The initial state $s_0$ is an acceptor, to handle the empty word. There’s an $a$ transition from $s_0$ to an acceptor state $s_a$ and a $b$ transition from $s_0$ to an acceptor state $s_b$. The state $s_a$ loops with an $a$ transition to handle $a^+$, and $s_b$ loops with a $b$ transition to handle $b^+$. Finally, there are a $b$ transition from $s_a$ and an $a$ transition from $s_b$ to a ‘garbage state’ $s_\infty$, which is not an acceptor state and which loops to itself on both $a$ and $b$ inputs; anything that contains both an $a$ and a $b$ dumps the machine into the garbage state and keeps it there.

share|cite|improve this answer
Thanks for clarifying. – zeqof Oct 18 '12 at 3:39
@zeqof: Glad to help. – Brian M. Scott Oct 18 '12 at 3:43

The automaton for $(a+b)^*$ will accept any string of as and bs at all, just as you described. But the automaton for $a^*+b^*$ will only accept strings that contain as or bs, but not both. For example, it won't accept the string ab. Once it sees either an a or a b, it is "locked in", and seeing the other letter will put it into a "dead" state from which it can never accept.

share|cite|improve this answer

Your Answer


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.