filipg/amu_automata_2011 — Issue #181: Do AutomataSpecification dodać metodę wyliczającą epsilon-domknięcie danego stanu
Author: filipg
Created: 2011-11-03 07:55:52+00:00
State: open

Epsilon-domknięcie stanu to zbiór stanów osiągalnych z danego stanu po samych epsilon-przejściach. Oto pseudokod najprostszego (niekoniecznie najefektywniejszego) algorytmu wyliczającego epsilon-domknięcie stanu q:

epsilon-domknięcie(q) := {q}

do
dodano-coś := false

dla każdego stanu p zawartego w epsilon-domknięcie(q)
dla każdego epsilon-przejścia wychodzącego z p
r := stan docelowy epsilon-przejścia
if r nie należy do epsilon-domknięcie(q)
dodaj r do epsilon-domknięcie(q)
dodano-coś := true
while dodano-coś

(Zauważmy, że stan zawsze należy do swojego epsilon-domknięcia.)