Search code examples
nfa

r* expression NFA

I have found this image, which represents r* expression NFA. My question is: there shouldn't be an arrow linking the second node to the third node? This way if I have a "rr" string, when the first symbol is read I get into the second node, but from there can't go anywhere because there aren't outgoing arrows. http://imageshack.us/f/641/screenshot20111021at114.png/

Solution

  • The linked image implies a couple of assumptions.

    • Arrows labeled "E" are implied to mean "epsilon transition", a changing state that doesn't modify the current symbol. following such an arrow doesn't "consume any input"
    • The rectangular region labeled "R" is implied to mean "An automaton accepting R". if you reach the starting state on that region (the second circle from the left in the image), the boxed region will accept R for an arbitrary sublanguage. R is used as a variable, just as it is in the base regular expression R*. We don't see any arrows between the starting and ending states because we don't define what R means; it's variable, we could use anything.