Need help with this regular expression

Question

Give a regular expression that describes the language accepted by the illustrated FSA. State $0$ is the initial state.

Answer 1

HINT: There are mechanical algorithms for solving this kind of problem, but this FSA is simple enough that we can find such a regular expression without using them.

• Any word matching $a(ba)^*$ will be at $1$, where it will be accepted if the next letter is $a$. Thus, the language includes all words matching $a(ba)^*a(a+b)^*$.

• Any word matching $a(ba)^*b$ will be at $2$, where it will be accepted if the next letter is $b$. Find a regular expression that matches all accepted words of this type; it will be similar to the one in the previous bullet point.

• Now analyze the accepted words that start with $b$; the reasoning is very similar.

• Finally, combine your results to get a regular expression that covers all cases.

The regular expression that you get probably won’t be very compact and will most likely be capable of considerable simplification, but you can worry about that later: for now you just want to get one that’s correct.