thompson's construction: superfluous epsilon transitions ?

spur4444@yahoo.com (Spur)
3 Apr 2004 09:13:30 -0500

          From comp.compilers

Related articles
thompson's construction: superfluous epsilon transitions ? spur4444@yahoo.com (2004-04-03)
Re: thompson's construction: superfluous epsilon transitions ? torbenm@diku.dk (2004-04-15)
Re: thompson's construction: superfluous epsilon transitions ? torbenm@diku.dk (2004-04-21)
| List of all articles for this month |
From: spur4444@yahoo.com (Spur)
Newsgroups: comp.compilers
Date: 3 Apr 2004 09:13:30 -0500
Organization: http://groups.google.com
Keywords: parse, theory, question
Posted-Date: 03 Apr 2004 09:13:30 EST

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


Post a followup to this message

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