3 Apr 2004 09:13:30 -0500

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) |

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.