thompson's construction: superfluous epsilon transitions ?

Hello all,


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:


(S0)---a-->(S1)---b-->(F)


(S0)---a-->(S1)---Eps-->(S2)---b-->(F)


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
simpler ?
Why can't it be just:


    <~~~~Eps~~~~~~|
(S0)---a,Eps-->(F)


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


Eli

Return to the comp.compilers page.
Search the comp.compilers archives again.