✖

Převod regulárního výrazu na automat

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ý regulární výraz na nedeterministický konečný automat.

Příklad

Než si popíšeme samotný algoritmus, ukážeme si na příkladu, o co nám vlastně půjde. Mějme tento regulární výraz: $a(b|c)x^\ast$. Slovně bychom jazyk, který regulární výraz generuje, popsali jako slova, která začínají písmenem „a“, následuje buď písmeno „b“ nebo „c“ a pak následuje libovolný počet písmen „x“. Dokázali bychom sestrojit automat, který by přijímal tento jazyk? Ale jo, podívejte:

Tento automat zřejmě přijímá stejný jazyk. Nabízí se tak otázka, jestli pro každý regulární výraz existuje automat, který daný jazyk přijímá. No, ano.

Popis algoritmu na převod reguláru na automat

Předpokládáme, že máme na vstupu regulární výraz R. Z předchozí části o regulárních výrazech víme, že regulární výraz může mít celkem šest různých tvarů. Rozlišíme tak šest různých případů:

  1. R = a pro nějaký symbol $a\in\Sigma$. Tedy regulární výraz je pouze jeden symbol z abecedy $\Sigma$, nad kterou pracujeme. Automat, který by přijímat jeden symbol a by vypadal takto:

  2. R = ε, prázdný symbol. Automat, který by přijal prázdný symbol by vypadal takto:

  3. R = ∅, regulární jazyk, který generuje prázdný jazyk. Automat, který by takový jazyk rozpoznal, je tento:

  4. R = R1∪ R2, kde R1, R2 jsou regulární výrazy. My už víme, že sjednocení regulární jazyků je opět regulární jazyk a že jsme schopni sestavit automat, který takový jazyk přijímá. Jinými slovy předpokládáme, že máme automaty, které rozpoznávají jazyk generovaný výrazy R1 a R2 a pomocí nich sestavíme automat, který přijímá jazyk generovaný výrazem R1∪ R2. Příklad: pokud R1 = a a R2 = ε, tak dle postupu získáme tento automat:

  5. $R=R_1\circ R_2$, kde R1, R2 jsou regulární výrazy. Stejný případ jako v minulém bodě. Zřetězení regulárních jazyků je regulární jazyk a jsme tak schopni sestavit automat, který takový jazyk bude přijímat. Takže pokud R1 = a, R2 = b, tak by zřetězení vypadalo takto:

  6. $R=(R_1^\ast)$, kde R1 je regulární výraz. Opět víme, že uzávěr regulárního jazyka je regulární jazyk. Takže pokud $R=a^\ast$, tak by automat vypadal takto:

Postupnou aplikací těchto bodů převedeme celý regulární výraz na konečný automat.

Ucelený příklad

Zkusíme převést regulární výraz $(a|bc)^\ast$. Postupně získáme tyto automaty:

Tento výsledný automat přijímá jazyk, který generuje regulární výraz $(a|bc)^\ast$. Samozřejmě automat je šíleně složitý a jistě existuje mnohem jednodušší automat, který přijímá stejný jazyk. Můžeme použít algoritmus pro převod nka na dka a následně provést minimalizaci automatu.

Zdroje

Hledáme programátory!