|thompson's construction: superfluous epsilon transitions ? email@example.com (2004-04-03)|
|Re: thompson's construction: superfluous epsilon transitions ? firstname.lastname@example.org (2004-04-15)|
|Re: thompson's construction: superfluous epsilon transitions ? email@example.com (2004-04-21)|
|Date:||3 Apr 2004 09:13:30 -0500|
|Keywords:||parse, theory, question|
|Posted-Date:||03 Apr 2004 09:13:30 EST|
I have seen Thompson construction diagrams of two kinds -
minimalistic, and with additional Eps edges, probably for clarity.
For example, the following are two ways to represent the concatenation
of a and b:
Similarly, there are two ways to represent a|b, one with just 2 states
and two edges (a and b) between them, and another with 6 states,
padded with Eps edges all along.
Thus, I want to ask whether the Kleene transition (a*) can be made
Why can't it be just:
That is, from the start state edges to the final state on a or Eps,
and back on Eps ?
It looks like this will accept a* too, doesn't it ? So why isn't it
presented as an alternative to the "normal" 4 state representation ?
The only problem I see here is the "Eps loop", i.e. Eps leads from S0
to F, and Eps leads from F to S0. Is this illegal in NFAs ? I guess it
can be a problem because to any accepting path and infinite string of
S0->F->S0->F... may be added since the transitions are Eps. But can't
we define the accepting string as the minimal and solve this problem ?
Thanks in advance
Return to the
Search the comp.compilers archives again.