Draw a finite state machine which will accept the regular expression $(a^2)^* + (b^3)^*$

Question

Draw a finite state machine which will accept the regular expression:

$(a^2)^* + (b^3)^*$

In particular, I am confused by the $+$ sign, what does it exactly mean? Most literature I could find about $+$ is $a^+$, which means 1 or more $a$; but here it is clearly not the same meaning.

Answer 1

Start at state $q_{0}$. On input of $a$, transition to state $q_{1}$. On input of $b$, go to $q_{2}$.

While on $q_{1}$, if there is an input of $a$, go to $q_{0}$.

While on $q_{2}$, if an input of $b$, go to $q_{3}$. On $q_{3}$, on input of $b$, go to $q_{4}$. While on $q_{4}$, go to $q_{2}$ on input of $b$.

The accepting states are $q_{0}$ and $q_{4}$. Of course, you could have $q_{0}$ and $q_{4}$ go to a separate accepting state on input $\epsilon$, the empty string.

Answer 2

I'm guessing it's similar to the notation used in this post on CS, where the author uses it to mean OR.

Applying to your example, your FSM must accept an even number of as, or a number of bs divisible by three.

So, to draw the graph, first draw the graph for $(a^2)^*$. Then, draw the graph for $(b^3)^*$. Then, put a start state, say $s$, and transitions consuming the empty string from $s$ to the two graphs.

Answer 3

Here is the drawing:

The idea is that the machine has two counters, one for as and one for bs, indicated by the orange boxes. Since it accepts either a number of as that is a multiple of 2, or a number of bs that is a multiple of 3, it only needs to choose which of these counters to use. Upon seeing the first symbol in the input, either a or b, it chooses which of the counters to use, and thereafter circulates around the counter. One state of each counter is an accepting state. If the wrong symbol appears while the machine is counting, it goes into ‘dead’ state $x$, from which it cannot escape; transitions to state $x$ are drawn in red.