✖

Převod automatu na regulární výraz

Kapitoly: Regulární výrazy, Převod reguláru na automat, Zobecněný NKA, Převod automat na regulár

Ukážeme si, jak převést libovolný konečný automat na regulární výraz.

Popis algoritmu

Na vstupu máme nějaký NKA A. Jako první z něj uděláme ZNKA. V druhé fázi vždy v jednom kroku odstraníme jeden stav, správně pozměníme přechodové funkce a opakujeme, dokud nezbydou jen dva stavy — počáteční a koncový. Mezi nimi povede hrana, která bude jako popisek regulární výraz, který bude výsledkem celého algoritmu. Celý postup tak spočívá především v odstranění stavu a následné opravě automatu tak, abychom získali ekvivalentní automat.

Odstranění jednoho stavu

Jak odstranit jeden stav si můžeme znázornit na jednoduchém příkladu. Předpokládejme, že část našeho automatu vypadá takto:

kde Ri jsou nějaké regulární výrazy. Jak by vypadal automat, kdybychom odstranili stav qr? Můžeme si to představit tak, že jsme ve stavu qi a ptáme se, jaká všechna slova jsme schopni na tomto úseku vygenerovat? Pokud půjdeme ze stavu qi přímo do stavu qj, budou to všechna slova, která odpovídají regulárnímu výrazu R4.

Pokud ale půjdeme do stavu qr, tak můžeme vygenerovat slova tvaru R1. Ve stavu qr ale můžeme cyklit pro regulární výraz R2, takže vlastně můžeme vygenerovat slova tvaru $R_1\circ(R_2^\ast)$. No a protože se ještě můžeme dostat ze stavu qr do stavu qj, tak tam ještě přidáme regulární výraz R3. Celkově tak touto cestou můžeme získat slova tvaru $R_1\circ(R_2^\ast)\circ R_3$.

Nyní víme, že z této části automatu mohou vzniknout slova tvaru R4 nebo tvaru $R_1\circ(R_2^\ast)\circ R_3$. To samozřejmě můžeme napsat ve tvaru regulárního výrazu jako $(R_4)|(R_1\circ(R_2^\ast)\circ R_3)$.

Nyní už můžeme jednoduše odstranit stav qr a nechat jen dva stavy qi a qj a namísto R4 napíšeme právě vypočtený regulární výraz:

Tento postup provedeme s každou hranou z každého stavu qi do nějakého stavu qj a to včetně smyček, tj. včetně případu, kdy qi = qj.

Po odstranění jednoho stavu získáme ekvivalentní automat — automat, který rozpoznává stejný jazyk.

Celý algoritmus

Na vstupu máme NKA $A=\left<Q, \Sigma, \delta, q_0, F\right>$.

  1. Převedeme NKA A na ZNKA $Z=\left<Q^\prime, \Sigma, \delta^\prime, q_0^\prime, q_f^\prime\right>$. Dále budeme písmenem k označovat počet stavů v Z.
  2. Pokud k = 2, algoritmus končí a na hraně mezi počátečním a koncovým stavem je výsledný regulární výraz.
  3. Pokud k>2, vybereme libovolný stav qr, který je různý od počátečního a koncového stavu, tj. $q_r\ne q_0^\prime$ a $q_r\ne q_f^\prime$. Dále vytvoříme nový ZNKA $Z^\prime=\left<Q^{\prime\prime}, \Sigma, \delta^{\prime\prime},q_0^{\prime},q_f^{\prime}\right>$, pro který bude platit: $$ Q^{\prime\prime}=Q^\prime\setminus\left\{q_r\right\} $$ a pro všechny $q_i\in Q^{\prime\prime}\setminus\left\{q_f^\prime\right\}$ a pro všechny $q_j\in Q^{\prime\prime}\setminus \left\{q_0^\prime\right\}$ nechť $$ \delta^{\prime\prime}(q_i, q_j)=(R_4)|(R_1(R_2^\ast)R_3), $$ kde $R_1=\delta^\prime(q_i,q_r)$, $R_2=\delta^\prime(q_r,q_r)$, $R_3=\delta^\prime(q_r, q_j)$, $R_4=\delta^\prime(q_i, q_j)$. Dále pokračuj krokem 2.

Příklad

Mějme na vstupu tento konečný automat:

Jako první jej převedeme na ZNKA (zbytečné ∅-přechody nebudeme znázorňovat):

Nyní aplikujeme druhou část algoritmu a odstraníme nějaký uzel. Začneme s uzlem q2. Odstraníme uzel q2 a přidáme přechod ze stavu q1 do stavu qf. Tento přechod označíme jako $b(a|b)^\ast$, protože z uzlu q1 se dostaneme do stavu q2 pro slova tvaru b, pak můžeme cyklit pro a|b, tím získáme $(a|b)^\ast$ a nakonec se pomocí epsilon pravidla přesuneme do qf. Přitom platí, že $b(a|b)^\ast\epsilon=b(a|b)^\ast$. Dostaneme automat:

Zbývá nám odstranit poslední stav, q1. Přidáme hranu ze stavu qs do stavu qf. Jak ji označíme? Do stavu q1 se dostaneme přes epsilon pravidlo, to můžeme rovnou vypustit. Pak můžeme cyklit pro a, takže získáme regulární výraz $a^\ast$. No a nakonec se přes hranu dostaneme do qf, takže výraz ještě zřetězíme s $b(a|b)^\ast$. Hranu tak popíšeme regulárním výrazem $a^\ast b(a|b)^\ast$.

Automat už má jen dva stavy, takže algoritmus končí. Na hraně je výsledný regulární výraz.

Zdroje