# Finding the regular expression equivalent for the given finite automaton

This is another homework problem I'm stuck with. For the given finite automata, I am asked to find out the equivalent regular expression.

On inspecting the given automata, I started deducing the expressions that it accepts and tried to find a pattern, and this is what I was able to figure out -

The automata makes the following transitions to a final state upon said input -

1. $q_1 to \ q_3$ on input of a single symbol $b$, $a^*b$, $ba^*$, or $a^*ba^*$.
2. Traversing through the cycle $q_1,q_3,q_2$ (and so on repeating) on input of $(a^*b^4a^*)^*$, a $((a^*b)^4)^*$.

Now the equivalent regular expression must be the sum of all these expressions,

R = $b + (a^*b) + (ba^*) + (a^*ba^*) + (a^*b^4a^*)^* + ((a^*b)^4)^*$.

Is there a better, concise expression for this or am I missing something? If not, How do I approach the simplification process of this expression?

• You can simplify $R$ to $(a^\ast b a^\ast)(b a^\ast b a^\ast b a^\ast)^\ast$. Intuitively, this means you can loop in $q_1$ with $a$s, move to $q_3$ with $b$ and loop there again with $a$. After that you have the option to move to $q_2$ and $q_1$ via $b$ again with $a$-loops in between as often as you want. I think this the most straight forward expression. However, you should checkout at least one algorithm, e.g. Floyd-Warshall, for these kind of exercises. – ttnick Mar 1 '18 at 9:56
• Thank you so much! Yes I just learnt Floyd-Warshall's algorithm, also realised its too expensive, and also learnt State elimination, to get the resultant regular expression much easier. – Vishhvak Srinivasan Mar 1 '18 at 10:39
• The essence of the state elimination algorithm is quite the same. I think the recursion step is somehow "rolled over" as in Floyd-Warshall. Maybe one more trick for state elimination, since it is not taught everywhere: Instead of $(Q, \Sigma, \Delta, q_0, F)$ look at $(Q \cup \{q_s, q_f\}, \Sigma, \Delta \cup \Delta^\prime, q_2, \{q_f\})$ with $(q_0, \varepsilon, q_0) \in \Delta^\prime$ and $(p, \varepsilon, q_f) \in \Delta^\prime$ for all $p \in F$ and eliminate all states execept for $q_s, q_f$. You will get an automaton with only one transition with the desired regular expression. – ttnick Mar 1 '18 at 11:07
• @PHPNick Yes. I think I read something similar to this in Mr.Ulmann's Book for Automata & Languages. Thank you so much for the input! – Vishhvak Srinivasan Mar 2 '18 at 4:27

Your DFA accepts the language of all words over $\{a,b\}$ in which the number of $b$s is of the form $3n+1$ (i.e., it is equivalent to 1 modulo 3). More generally, upon reading a word $w$, the DFA will be in state $q_1$ if it read a number of $b$s which is a multiple of 3; in state $q_3$ if it read a number of $b$s which is equivalent to 1 modulo 3; and in state $q_2$ if it read a number of $b$s which is equivalent to 2 modulo 3.
Using this description, it is easy to come up with a regular expression equivalent to your DFA. Rather than do that, let me give regular expressions for the language $L_{even}$ of words over $\{a,b\}$ containing an even number of $a$s, and for the language $L_{odd}$ of words over $\{a,b\}$ containing an odd number of $a$s:
• $L_{even}$: $b^*(ab^*ab^*)^*$.
• $L_{odd}$: $b^*ab^*(ab^*ab^*)^*$.