So I've been trying to crack this for a long time and almost feel like I am going in loops about this question.

Given the following NFA:

enter image description here

Using the GNFA algorithm get the regular expression.

I understand that you would have the following for the first step(adding empty states): enter image description here

The next step would be removing the state [q1] I would get: enter image description here

Finally removing [q2] would get: enter image description here

However the answers others have got is: $(a \cup bb^*a)^*bb^*$ Which does not make sense as I got, $a^*b(b \cup aa^*b)^*$? A GNFA(generalised nondeterministic finite automaton) is described as follows:

A GNFA is similar to an NFA but must obey certain rules:

  • It has only one accept state
  • The initial state has no transitions coming into it
  • The accept state has no transitions coming out from it
  • A transition can denote any regular expression, rather than just a symbol from the alphabet Note that a symbol is a kind of regular expression.

Furthermore, We may convert an NFA into a GNFA as follows:

  • Add a new start state with an ε-transition to the old start state
  • Add a new accept state with ε-transitions from the old accept states
  • If arrows have multiple labels, or if there are multiple arrows between two states, replace them with the union (or) of those labels
  • $\begingroup$ @Jeff , It is called a generalised nondeterministic finite automaton (GNFA) $\endgroup$ – Anish B May 10 '13 at 14:57
  • $\begingroup$ Hint: What language does your DFA actually accept? You should be able to figure out an English description of the accepted language just by looking at the DFA. Now, which of the two regular expressions $(a+bb^*a)bb^*$ and $a^*b(b+aa^*b)^*$ correctly describe that language? $\endgroup$ – JeffE May 10 '13 at 14:59
  • $\begingroup$ @JeffE Also, I do agree that one makes more sense than the other however, when using the GNFA algorithm it isn't typically the same as reading it in an English description hence my confusion. $\endgroup$ – Anish B May 10 '13 at 15:03
  • 1
    $\begingroup$ I never said "one makes more sense than the other". I'm suggesting that you solve the problem from first principles, using your brain instead of the GNFA algorithm, and then check which of the two regular expressions are correct. (Note: I did not write "which of the two regular expressions is correct.") $\endgroup$ – JeffE May 10 '13 at 15:08
  • 1
    $\begingroup$ See also our reference question for more techniques, all of which can yield different (yet still correct) results. $\endgroup$ – Raphael May 12 '13 at 10:24

You want to know why "the others" obtained a different expression?

When contructing a regular expression there is no unique correct answer. There are usually several expressions "that make sense". In this case you use state elimination method (I learned this under the name of Brzozowski and McCluskey). Here the order of removal determines the expression found. So: what do you get when removing $q2$ first?

You can also do "clever tricks" during the construction. In your example you have $b\cup aa^*b$ which is equivalent to $a^*b$.

| cite | improve this answer | |
  • $\begingroup$ +1 for b U aa*b = a*b and the name Brzozowski and McCluskey $\endgroup$ – Maha Apr 24 '14 at 8:52

Your Answer

