PRUMYSL.CZ KONSTRUKTER.CZ 3D-TISK.CZ MATEMATIKA.CZ NOVAMEDIA.CZ

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

Zobrazit kapitoly článku
  1. Regulární výrazy
  2. Převod reguláru na automat
  3. Zobecněný NKA
  4. 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=\emptyset\), regulární jazyk, který generuje prázdný jazyk. Automat, který by takový jazyk rozpoznal, je tento:

  4. \(R=R_1\cup R_2\), 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 \(R_1\cup R_2\). 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 #

 

Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace