Determine the language that corresponds to the following automata.

Question

I want to determine that language that corresponds to the following automata

Note: $q_{6}$ have arrow to $a$ to himself.
I started with the minimal words:

1. $aaabb$
2. $aaba$
3. $aaaba$
4. $bababa$

the only thing I figured from here is that the number of $a$ need to be $>2$
any suggestions?
thanks.

Answer 1

The basic technique is to repeatedly remove one of the states from the automaton, adapting the labels of the surrounding states accordingly. Here, it is not difficult to see that the transitions q0-q1-q2 correspond with the regular expression b*ab*a. Similarly q2-q4-q5 (resulting in aa*b) and q2-q5-q6 (resulting in bb*a). The difficulty lies in the states q5, q6and q7 which are "intertwined". Another approach is Brzozowski's algebraic method, which translates the transitions into a series of equations to be reduced. The techniques are discussed in this article by Christoph Neumann, for instance, but are quite messy to actually perform by hand.

The package JFLAP has a built-in ability to convert automata to regular expressions. Entering your automaton, with the extra loop on q6, then results in the following expression: b*((ab*abb*a+ab*aaa*ba)(ba)*+(ab*aaa*bb+(ab*abb*a+ab*aaa*ba)(ba)*bb)(b+a(ba)*bb)*(λ+a(ba)*)).