Matematické Fórum

Sk1X1 · 31. 05. 2020 12:18

Zdravím,
snažím se z následujícího regulárního výrazu udělat deterministický konečný automat.
$a^{*}b(c\vee a^{*})\vee b^{*}$

Nakreslil jsem si tedy nedeterministický.
//forum.matweb.cz/upload3/img/2020-05/19748_Untitled%2BDiagram%2B%25281%2529.png

A teď se snažím sestrojit ten deterministický. Zkoušel jsem různé postupy, co jsem tak různě nastudoval, ale žádný z nich se mi nezdá, že by vyšel.

Zkoušel jsem například sestrojit tabulku s espilon přechody.
//forum.matweb.cz/upload3/img/2020-05/20175_2020-05-31.png

Z ní bych pak dle postupu měl udělat další tabulku, kde začnu vstupním stavem a budu postupně získávat stavy, do kterých se dostanu. Jenže ze stavu 1 se nikam nedostanu a tak skončím hned v prvním bodě.
Můžete mě prosím někdo zkusit navést, kde jsem udělal chybu?

PS Dokážu vložit tabulku jinak než obrázkem?

Stýv · 31. 05. 2020 12:59

Já bych řekl, že ze vstupního stavu {1,2,3,7} přejdeš například přes b do stavu {3,4,5,6,7}.

Stýv · 31. 05. 2020 13:05

Pokud jde o tabulky, tak se dá použít latex:

nebo primitivnější [ code ][ /code ] (bez těch mezer):

Code:

  a b c E      
1 - - - 1,2,3,7
2 2 4 - 2      
3 - - - 3,7

Sk1X1 · 31. 05. 2020 13:26 — Editoval Sk1X1 (31. 05. 2020 13:27)

To znamená, že při sestrojení té druhé tabulky není vstupní stav {1}, ale stav z E sloupce {1,2,3,7}. Jde mi hlavně o obecný postup, který bych mohl použít i u dalších řešených příkladů. Tohle schválně vyzkouším. Díky moc.

Stýv · 31. 05. 2020 14:04

Nevím, jaký postup jste se učili, já vycházím z https://dl1.cuni.cz/pluginfile.php/4876 … tomaty.pdf (str. 57). Idea je, že stavy toho DKA jsou množiny všech stavů původního NKA, ve kterých bys zrovna mohl být.

Sk1X1 · 02. 06. 2020 14:36

Díky moc za rady, je mi to jasnější :-)

Matematické Fórum

#1 31. 05. 2020 12:18

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

#2 31. 05. 2020 12:59

Re: Převod regulárního výrazu na KA

#3 31. 05. 2020 13:05

Re: Převod regulárního výrazu na KA

Code:

#4 31. 05. 2020 13:26 — Editoval Sk1X1 (31. 05. 2020 13:27)

Re: Převod regulárního výrazu na KA

#5 31. 05. 2020 14:04

Re: Převod regulárního výrazu na KA

#6 02. 06. 2020 14:36

Re: Převod regulárního výrazu na KA

Zápatí