0
$\begingroup$

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*).

2 Answers 2

1

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.

  • 0
    @zeqof: Glad to help.2012-10-18
0

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.