[ri4pp:2007] - Re: by "Petar Bojic" <rapecafa@verat.net>

Svaki regularan izraz opisan Tompsonovim grafom ima jedinstven pocetni i
jedinstven krajnji cvor, pri cemu izmedju moze biti proizvoljna budzevina
od cvorova i prelaza, a ne samo jedan prelaz kao u primeru reg izraza a
ili b. Konkatenacija samo kaze da se Tompsonov graf za konkatenaciju
regularnog izraza A i regularnog izraza B dobija tako sto se epsilon
prelazom spoji krajnji cvor reg. iz. A i pocetni cvor reg. iz. B. Tu nema
nikakvih dodatnih stanja i epsilon prelaz se ne moze izbeci. Doduse, mogao
bi se izbeci epsilon prelaz objedinjavanjem krajnjeg stanja reg izraza A i
pocetnog reg izraza B u jedno stanje (kao sto je navedeno u primeru za ab)
ali to nije  moguce uvek uraditi.

Petar Bojic

> Moze li neko da mi kaze da li kod Tomsonovog algoritma za konkatenaciju ab
> postoji jedno dodatno
> stanje izmedju (u koje se prelazi pod dejstvom epsilon) , tako pise u
> predavanjima,
> znaci
> 1--(a)--->2-----(epsilon)--->3---(b)--->4  ???
>
> ili
>
> (ovako su radjeni svi zadaci u zbirci)
> 1---(a)--->2-----(b)----->3  ??
>
> Logicnije mi je ovo iz zbirke, u redu za uniju, zvezdasto i pozitivno
> zatvranje - slazhem se da treba epsilon,
> ali za konkatenaciju mislim da je suvishno (samo gomilamo bezveze stanja
> automata) ?
>
> Hvala,pozdrav
>