Regular Expressions

The answer is $(ab^*a | cd^*c)^*$ .

$S_0$ is the starting state and the accepting state. From the starting state we can either choose "c" or "a" to transition to $S_1$ or $S_2$ , respectively. This clues us into the fact that the answer will probably have an "OR" operation.

Case 1: we go to $S_1$ and generate a "c". From $S_1$ to get back to the accepting state ( $S_0$ ), we can go straight to $S_0$ with a "c" transition, generating the string "cc" or we can loop back in on $S_1$ with "d" however many times and then do the "c" transition to the accepting state, generating a string with a "c", then any number of "d"s, then one "c".

Case 2: we go to $S_2$ and generate an "a". From $S_2$ to get back to the accepting state ( $S_0$ ), we can go straight to $S_0$ with an "a" transition, generating the string "aa" or we can loop back in on $S_2$ with "b" however many times and then do the "a" transition to the accepting state, generating a string with an "a" then any number of "b"s and then an "a".

After we complete either case 1 or case 2, we can start the whole thing over and add on another part of the string using case 1 or 2, and this is why there is a star surrounding the OR term.

For example, we could complete case 1 with 2 iterations of "d" to make "cddc" and then back at $q_0$ , we could do a case 2 with three iterations of the "b" transition to produce the string "cddcabbba".