7
$\begingroup$

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
Improve this question
$\endgroup$
8
  • $\begingroup$ @Jeff , It is called a generalised nondeterministic finite automaton (GNFA) $\endgroup$
    – Anish B
    Commented May 10, 2013 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
    Commented May 10, 2013 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
    Commented May 10, 2013 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
    Commented May 10, 2013 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
    Commented May 12, 2013 at 10:24

1 Answer 1

Reset to default
8
$\begingroup$

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

When constructing a regular expression, there is no unique correct answer. There are usually several expressions "that make sense." In this case, you use the 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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 for b U aa*b = a*b and the name Brzozowski and McCluskey $\endgroup$
    – Mahesha999
    Commented Apr 24, 2014 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.