# 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 ?