05.1 Převod RV na KA
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
Vztah mezi RV a KA
# Metoda sousedů
Glushkov
Vezme RV a očísluje si každý jeho symbol, aby byl unikátní
Vytvoří množinu $Z$ - začínající symboly, všechny symboly, kterými může RV začínat
Vytvoří množinu $P$ - dvojice symbolů takových, že v tom RV mohou sousedit ($a_{i}$, může po něm bezprostředně následovat $b_{j}$)
Vytvoří množinu $F$ - koncových symbolů, symboly kterými hodnoty RV mohou končit
Vznikne konečný automat nedeterministický a homogenní
# Metoda derivací
- Janusz A. Brzozowski
- Vezmu RV $V$ a budu ho derivovat podle všech symbolů abecedy
- Budou vznikat nové RV, každý bude stavem automatu
- Zároveň je třeba kontrolovat, jestli ty stavy (RV) nejsou podobné, aby jich nebylo zbytečně moc
- Koncové stavy jsou všechny RV, které obsahují $\varepsilon$
Věta: Každý regulární výraz má pouze konečný počet nepodobných derivací Důsledek: Pro konstrukci DKA pro daný RV pomocí metody derivací stačí uvažovat pouze podobnosti ($\cong$) výrazů
- Vznikne konečný automat deterministický, který není minimální
# Metoda postupné konstrukce
- Ken Thompson
- Sleduje definici RV
- Sestrojí různé malé (částečné) automaty pro různé RV, které nakonec budou tvořit jeden velký automat
- Každý malý automat (operace) vytváří 1 počáteční a 1 koncový stav
# Pravidla
# Příklad
$V = ab^*a , + , ab$
- Vznikne konečný automat nedeterministický s $\varepsilon$-přechody