Select Git revision
regular.tex
-
Martin Mareš authored
\approx se tolik neplete s rovnítkem jako \equiv.
Martin Mareš authored\approx se tolik neplete s rovnítkem jako \equiv.
regular.tex 58.12 KiB
\ifx\chapter\undefined
\input adsmac.tex
\singlechapter{1}
\fi
\chapter[dfa]{Regulární jazyky}
\section{Definice a značení}
\list{o}
\:\em{Abeceda $\Sigma$} je nějaká konečná množina, jejím prvkům budeme říkat \em{znaky}
(někdy též \em{písmena}).
\:\em{$\Sigma^*$} je množina všech \em{slov} neboli \em{řetězců} nad abecedou~$\Sigma$,
což jsou konečné posloupnosti znaků ze~$\Sigma$.
\:\em{Slova} budeme značit malými písmenky řecké abecedy $\alpha$, $\beta$, \dots
\:\em{Znaky} abecedy označíme malými písmeny latinky $x$, $y$, \dots{}
Konkrétní znaky budeme psát \|psacím strojem|.
Znak budeme používat i~ve~smyslu jednoznakového řetězce.
\:\em{Délka slova} $\vert \alpha \vert$ udává, kolika znaky je slovo tvořeno.
\:\em{Prázdné slovo} značíme~$\varepsilon$, je to jediné slovo délky~0.
\:\em{Zřetězení} $\alpha\beta$ vznikne zapsáním slov $\alpha$ a~$\beta$ za sebe. Platí $\vert \alpha\beta \vert=\vert \alpha \vert+\vert \beta \vert$, $\alpha\varepsilon=\varepsilon\alpha=\alpha$.
\:\em{Mocnina} řetězce $\alpha^k$ pro $k\in\N$\foot{V~tomto textu považujeme 0 za přirozené číslo.}
vznikne zřetězením $k$~kopií řetězce~$\alpha$.
Tedy $\alpha^0=\varepsilon$, $\alpha^{k+1} = \alpha^k\alpha$.
\:$\alpha[k]$ je $k$-tý znak slova $\alpha$, indexujeme od~$0$ do~$\vert\alpha\vert-1$.
\:$\alpha[k:\ell]$ je \df{podslovo} začínající $k$-tým znakem a~končící těsně před $\ell$-tým.
Tedy $\alpha[k:\ell] = \alpha[k]\alpha[k+1]\ldots\alpha[\ell-1]$. Pokud $k\ge\ell$, je podslovo
prázdné. Pokud některou z~mezí vynecháme, míní se $k=0$ nebo $\ell=\vert\alpha\vert$.
\:$\alpha[{}:\ell]$ je \df{prefix} (předpona) tvořený prvními $\ell$ znaky řetězce.
\:$\alpha[k:{}]$ je \df{suffix} (přípona) od $k$-tého znaku do~konce řetězce.
\:$\vert \alpha \vert_x$ znamená počet výskytů znaku~$x$ v~řetězci~$\alpha$. Je to tedy počet všech~$i$ takových,
že $\alpha[i]=x$.
\:\em{Otočení} $\alpha\rev$ je slovo~$\alpha$ \uv{čtené pozpátku}. Tedy
pro $\alpha=x_1\ldots x_n$ máme $\alpha\rev=x_n\ldots x_1$.
\:\em{Jazyk} říkáme jakékoliv množině slov. Jazyky jsou tedy podmnožiny~$\Sigma^*$.
\endlist
\obs{
Jazyky jsou podobné \em{rozhodovacím problémům,} které definujeme\foot{Viz Průvodce, kapitola Těžké problémy.}
jako funkce ze~$\Sigma^*$ do $\{0,1\}$.
Rozhodovacímu problému $P$ můžeme přiřadit jazyk $L_P = \{\alpha\in\Sigma^* \mid P(\alpha)=1\}$.
Naopak jazyku $L\subseteq\Sigma^*$ přiřadíme problém~$P_L$ takový, že $P_L(\alpha) = 1 \Leftrightarrow \alpha\in L$.%
\foot{Bystrý čtenář v~tom poznává charakteristickou funkci podmnožiny.}
}
\section[dfa]{Konečné automaty}
\defn{\em{Deterministický konečný automat} (jinak řečený DFA\foot{deterministic finite-state automaton})
je uspořádaná pětice $(Q,\Sigma,\delta,q_0,F)$, kde:
\list{o}
\:$Q$ je konečná neprázdná množina \em{stavů,}
\:$\Sigma$ je konečná neprázdná množina znaků -- \em{abeceda,}
\:$\delta: Q\times \Sigma \rightarrow Q$ je \em{přechodová funkce,}%
\foot{Zde se omlouváme za nekonsistenci: malá řecká písmena jsme si vyhradili pro slova,
ale toto značení pro přechodovou funkci je natolik zažité, že ho je marno měnit.}
která pro každý stav automatu a znak ze vstupu určí, do jakého stavu má automat přejít,
\:$q_0\in Q$ je \em{počáteční stav,}
\:$F\subseteq Q$ je množina \em{přijímacích (neboli koncových) stavů.}
\endlist
}
Ve zbytku tohoto oddílu budeme říkat prostě \em{automat.}
\defn{\em{Výpočet} automatu pro vstup $\alpha\in\Sigma^*$ je posloupnost stavů
$s_0,s_1,\ldots,s_{\vert\alpha\vert}$ taková, že:
\list{o}
\:$s_0 = q_0$,
\:$s_{i+1} = \delta(s_i, \alpha[i])$.
\endlist
}
\note{
Automat si také můžeme představit jako orientovaný graf. Jeho vrcholy odpovídají stavům,
hrany přechodům mezi stavy. Každá hrana je označena jedním znakem abecedy, přičemž platí,
že z~každého vrcholu vede pro každý znak abecedy právě jedna hrana. Výpočet pro vstup~$\alpha$
je pak sled\foot{Připomínáme, že \em{sled} v~grafu je posloupnost na sebe navazujících vrcholů a~hran.
Od cesty se liší tím, že se v~něm mohou vrcholy i~hrany opakovat.} začínající v~počátečním
stavu, přičemž znaky na hranách dávají po řadě slovo~$\alpha$. Tento sled je jednoznačně určen
slovem~$\alpha$.
}
\defn{\em{Rozšířená přechodová funkce} $\dstar: Q \times \Sigma^* \rightarrow Q$
je definována takto:
\list{o}
\:$\dstar(q,\varepsilon) = q$ pro všechna $q\in Q$,
\:$\dstar(q,\alpha x) = \delta(\dstar(q,\alpha),x)$ pro všechna $q\in Q$, $\alpha\in\Sigma^*$, $x\in\Sigma$.
\endlist
}
\obs{
Pro výpočet automatu platí $s_i = \dstar(q_0, \alpha[{}:i])$.
}
\defn{Slovo~$\alpha$ je \em{přijímáno automatem}, pokud příslušný výpočet skončí
v~přijímacím stavu, tedy $\dstar(q_0, \alpha) \in F$.}
\defn{\em{Jazyk přijímaný (rozpoznávaný) automatem} je množina všech přijímaných slov,
tedy $\{ \alpha\in\Sigma^* \mid \dstar(q_0, \alpha) \in F \}$. Pro automat~$A$ tento jazyk
označíme $L(A)$.
}
\defn{Jazyk~$L$ je \em{regulární,} pokud je rozpoznávaný nějakým konečným automatem.
Tedy existuje-li konečný automat~$A$ takový, že $L = L(A)$.
}
\nota{V~obrázcích značíme počáteční stav šipkou z~okolního prostoru do stavu,
přijímací stavy mají tučný zelený okraj.}
\examplen{počítání jedniček}{
Uvažme jazyk $L_3 = \{ \alpha\in\{\0,\1\} \mid |\alpha|_{\1} \bmod 3 = 0 \}$,
tedy jazyk slov, jejichž počet jedniček je dělitelný třemi. Tento jazyk je regulární.
O~tom se snadno přesvědčíme sestrojením automatu: bude mít stavy $\{0,1,2\}$ odpovídající
možným zbytkům po dělení počtu zatím přečtených jedniček třemi. Stav~0 bude jak počáteční,
tak jediný přijímací. Viz obrázek \figref{dfa-1div3}.
}
\figure[dfa-1div3]{dfa-1div3.epdf}{}{Automat pro počet jedniček dělitelný~3}
\examplen{konečné jazyky}{
Ukážeme, že libovolný konečný jazyk~$L$ je regulární. Automat bude mít tvar
písmenkového stromu (trie) pro množinu~$L$. Stavy tedy budou prefixy všech slov z~$L$
a navíc jeden univerzální zamítací stav~$z$. Přechodová funkce $\delta(\alpha,x)$
pro prefix~$\alpha$ a znak~$x$ povede do prefixu $\alpha x$, pokud existuje, jinak
do~$z$. Ze~$z$ povedou všechny přechody zase do~$z$. Počátečním stavem bude prázdný
prefix~$\varepsilon$, přijímacími stavy všechna slova z~$L$. Viz obrázek \figref{dfa-trie}.
}
\figure[dfa-trie]{dfa-trie.epdf}{}{Automat rozpoznávající jazyk $\{\|alice|, \|alik|, \|bob|, \|bobek| \}$}
\examplen{vyhledávací automaty}{
Vyhledávací automat\foot{Viz Průvodce, kapitola Textové algoritmy.}
typu Knuth-Morris-Pratt jde upravit na konečný automat.
Množinu stavů zachováme, první stav automatu (prázdný prefix) se stane počátečním,
poslední stav (prefix rovný jehle) jediným přijímacím. Přechodovou funkci definujeme
pomocí funkce na jeden krok automatu, která se sama postará o~použití dopředných a
zpětných hran. Jazyk rozpoznávaný tímto automatem bude tvořen všemi slovy, která
končí jehlou. Podobně můžeme upravit automat typu Aho-Corasicková. Viz obrázek
\figref{dfa-kmp}.
}
\figure[dfa-kmp]{dfa-kmp.epdf}{}{Převod KMP pro slovo \|ananas| na konečný automat}
\examplen{neregulární jazyk}{
Jazyk $L_{01} = \{ \0^n\1^n \mid n\in\N \}$ není regulární.
Dokážeme to sporem. Předpokládejme, že existuje automat rozpoznávající tento jazyk.
Označme~$t$ počet jeho stavů. Automat spustíme na vstupech $\0^k$ pro $k=0,\ldots,t$
a nazveme $s_0,\ldots,s_t$ stavy, ve kterých jednotlivé výpočty skončí. Bude tedy
$s_i = \dstar(q_0, \0^i)$.
Posloupnost $s_0,\ldots,s_t$ má $t+1$ prvků, ale ty nabývají nejvýše $t$ hodnot.
Proto se některá nutně zopakuje: máme $s_i = s_j$ pro $0 \le i < j \le t$.
Výpočty pro slova $\0^i$ a $\0^j$ tedy oba shodně dojdou do nějakého stavu~$s$.
Pokud za tato dvě slova přidáme libovolný suffix~$\beta$, musí tedy pokračovat
shodně do $\dstar(s, \beta)$.
Takže slova $\0^i\1^i$ a $\0^j\1^i$ buďto automat obě přijme, nebo obě zamítne.
Jenže první do jazyka~$L_{01}$ patří, zatímco druhé nikoliv.
To je spor s~předpokladem, že automat rozpoznává jazyk~$L_{01}$.
}
\subsection{Iterační lemma}
Obrat s~opakováním stavů se hodí v~důkazu následujícího lemmatu:
\lemman{iterační; angl. pumping lemma}{
Mějme regulární jazyk~$L$.
Potom existuje číslo $n\in\N$ takové, že
každé slovo $\omega\in L$ délky alespoň~$n$
můžeme rozložit na $\omega = \alpha\beta\gamma$, přičemž:
\list{n.}
\:$\beta\neq\varepsilon$
\cmt{prostřední část není prázdná}
\:$\vert\alpha\beta\vert \le n$
\cmt{první a druhá část jsou krátké}
\:Slova $\alpha\beta^t\gamma$ pro $t\ge 0$ leží všechna v~$L$.
\cmt{druhou část lze libovolně opakovat}
\endlist
}
\proof
Jelikož jazyk $L$ je regulární, existuje nějaký automat~$A$ rozpoznávající~$L$.
Za $n$ zvolíme počet stavů tohoto automatu.
Uvažme nyní nějaké slovo $\omega\in L$ délky $m\ge n$.
Označíme $s_0,\ldots,s_m$ výpočet automatu pro toto slovo, tedy
$s_i = \dstar(q_0, \omega[{}:i])$.
Tato posloupnost má délku větší než~$n$, ale vyskytuje se v~ní nejvýše $n$~různých stavů.
Proto se nějaký stav musí opakovat: bude $s_i = s_j = s$ pro nějaké $i<j$ a stav~$s$.
Navíc k~opakování nutně dojde v~prvních $n+1$ prvcích, takže $j\le n$.
Nyní zvolíme $\alpha = \omega[{}:i]$, $\beta = \omega[i:j]$, $\gamma = \omega[j:{}]$.
Jelikož $\dstar(q_0, \alpha) = s$ a $\dstar(s, \beta) = s$,
musí být $\dstar(q_0, \alpha\beta^t) = s$ pro každé~$t$.
Proto jsou všechny stavy $\dstar(q_0, \alpha\beta^t\gamma)$ stejné
a jelikož ten pro $t=1$ je přijímací, musí být pro všechna~$t$ přijímací.
\qed
\example{
Neregularitu jazyka $L_{01}$ z~předchozího příkladu můžeme snadno dokázat pumpováním.
Kdyby byl regulární, uvažme slovo $\omega = \0^n\1^n$, kde $n$ je konstanta z~lemmatu.
Podle lemmatu existuje rozklad $\omega = \alpha\beta\gamma$. Jelikož $\alpha$ a~$\beta$
mají dohromady nanejvýš $n$ znaků, skládají se jenom z~nul. Přidání další kopie~$\beta$
(nebo její odstranění) by mělo vytvořit jiné slovo jazyka. Jenže přidání~$\beta$ zvýší počet nul, ale zachová
počet jedniček, takže slovo v~jazyku ležet nemůže. To je spor.
}
\examplen{prvočísla}{
Jazyk $L_P = \{ 0^p \mid \hbox{$p$ je prvočíslo}\}$ také nemůže být regulární.
Kdyby byl, uvažme konstantu~$n$ z~lemmatu a zvolme libovolné prvočíslo $p \ge n+2$.
Slovo $\0^p \in L_P$ tedy můžeme rozložit na části $\alpha = \0^i$, $\beta = \0^j$,
$\gamma = 0^k$, kde $i$, $j$ a~$k$ jsou čísla splňující $i+j+k = p$, $j>0$, $i+j \le n$
a $k\ge 2$.
Všechna slova $\0^i\0^{jt}\0^k$ pro $t\ge 0$ mají také ležet v~$L_P$, takže
$i + jt + k$ musí být pro všechna~$t$ prvočíslo.
Jenže zvolíme-li $t=i+k$, je $i + jt + k = (i+k)(1+j)$.
Jelikož $i+k$ i $1+j$ jsou větší než~1 (to první díky tomu, že $k\ge 2$),
nemůže se jednat o~prvočíslo. Došli jsme ke sporu.
}
\subsection{Součin automatů}
Už jsme zjistili, že otázka, zda počet jedniček ve slově je dělitelný třemi,
je regulární. Podobně je regulární otázka, zda je počet nul sudý. Co kdybychom
chtěli rozpoznávat slova, která splňují obě podmínky současně? K~tomu se hodí
představa, že oba automaty spustíme paralelně a~slovo přijmeme v~případě, že ho
oba přijaly. To můžeme formálně popsat následující konstrukcí.
\defn{Mějme dva automaty se společnou abecedou~$\Sigma$:
$A_1 = (Q_1, \Sigma, \delta_1, q_{01}, F_1)$ a
$A_2 = (Q_2, \Sigma, \delta_2, q_{02}, F_2)$.
Jejich \em{součin} $A_1\times A_2$ je automat
$A = (Q, \Sigma, \delta, q_0, F)$ definovaný takto:
\list{o}
\:$Q = Q_1\times Q_2$,
\cmt{ve stavu si pamatujeme si stav obou automatů}
\:$\delta((s_1, s_2), x) = (\delta_1(s_1, x), \delta_2(s_2, x))$,
\cmt{simulujeme jeden krok každého automatu}
\:$q_0 = (q_{01}, q_{02})$,
\cmt{oba automaty začínají ve svých počátečních stavech}
\:$F = F_1 \times F_2$.
\cmt{přijmeme, pokud oba přijaly}
\endlist
}
Snadno nahlédneme, že automat~$A$ přijme právě ta slova, která jsou přijata
jak automatem~$A_1$, tak~$A_2$. Proto $L(A) = L(A_1) \cap L(A_2)$.
\cor{
Průnik dvou regulárních jazyků je zase regulární jazyk.
}
\exercises
\excmt{
Pro tento a následující jazyky rozhodněte, zda jsou regulární -- kladnou
odpověď můžete zdůvodnit sestrojením automatu, zápornou třeba pomocí iteračního
lemmatu.
}
\ex{Jazyk $\{ x\alpha x \mid x\in\Sigma, \alpha\in\Sigma^* \}$
pro abecedu $\Sigma = \{\|a|, \|b|\}$.
Tedy jazyk slov délky aspoň~2, jejichž první a poslední znak je stejný.
}
\ex{Jazyk všech neklesajících posloupností číslic $\|0|\ldots\|3|$.
}
\ex[bindiv5]{Jazyk dvojkových zápisů přirozených čísel dělitelných~5.}
\ex{Jazyk slov nad abecedou $\{\|a|, \|b|, \|r|\}$, která začínají
na některý z~řetězců \|abba|, \|ara|, \|bar|.
}
\ex{Jazyk slov nad abecedou $\{\|a|, \|b|, \|r|\}$, která končí na
některý z~řetězců \|ara|, \|bar|, \|baba|.
}
\ex{Jazyk \em{čtverců} $\{ \alpha\alpha \mid \alpha\in\{\0, \1\}^* \}$.}
\ex{Jazyk $\{ \0^{n^2} \mid n\in\N \}$.}
\ex{Jazyk $\{ \0^{2^n} \mid n\in\N \}$.}
\ex[regcompl]{Dokažte, že doplněk regulárního jazyka je zase regulární.
Tedy pro každý regulární jazyk $L\subseteq\Sigma^*$ je $\Sigma^* \setminus L$ také regulární.
}
\ex{Dokažte, že sjednocení regulárních jazyků je regulární.
}
\ex{Dokažte, že jazyk $\{ \alpha\in\{\0,\1\}^* \mid |\alpha|_{\0} = |\alpha|_{\1} \}$
není regulární. Využijte toho, že $\{ \0^n\1^n \mid n\in\N \}$ není regulární,
a~že průnik dvou regulárních jazyků je regulární.
}
\ex{Definujme \em{uzávorkování} jako posloupnost závorek {\tt(} a~{\tt)},
které lze spárovat tak, aby se páry nekřížily a v~každém páru byla {\tt(}
před~{\tt)}. Ukažte, že jazyk všech uzávorkování není regulární.
}
\ex{Co kdybychom automatu dovolili mít nekonečně mnoho stavů? Jak by se změnilo,
které jazyky můžeme rozpoznávat?}
\ex{Vymyslete algoritmus, který pro daný automat~$A$ rozhodne, zda jazyk $L(A)$
je neprázdný.}
\exx{Vymyslete algoritmus, který pro daný automat~$A$ rozhodne, zda jazyk $L(A)$
je konečný.}
\ex{Ukažte, že převod KMP na DFA z~našeho příkladu lze provést v~čase $\Theta(S\cdot\vert\Sigma\vert)$,
kde~$S$ je počet stavů KMP.}
\ex{Dokažte, že iterační lemma není ekvivalence: najděte neregulární jazyk~$L$,
který \uv{jde pumpovat}.}
\endexercises
\section{Nedeterministické automaty}
Uvažme následující příklad. Chceme popsat jazyk všech slov nad abecedou $\{\0,\1\}$, která
končí na \0\1. Taková slova můžeme složit ze dvou částí $\alpha$ a~$\beta$, kde $\alpha$ je
libovolný řetězec nul a jedniček a $\beta=\0\1$. Obě tyto části umíme rozpoznat konečnými
automaty~$A$ a~$B$, takže by bylo pěkné umět tyto automaty složit dohromady a získat tak automat
pro požadovaný jazyk.
\figure[nfa-kombinace]{nfa-kombinace.epdf}{}{Slepení dvou automatů za stav}
Nabízí se ztotožnit přijímací stav automatu~$A$ s~počátečním stavem automatu~$B$
(jako na obrázku \figref{nfa-kombinace})
a dovolit tak výpočtu přejít z~$A$ do~$B$. Jenže vzniklý \uv{slepený} stav má dva
přechody pro znak~\0, což naše definice konečného automatu nedovoluje.
Co kdybychom definici zobecnili, aby to bylo možné, a~během výpočtu si pak
z~možných přechodů jeden vybrali? To vede k~myšlence nedeterminismu.
\defn{\em{Nedeterministický konečný automat} (NFA) je uspořádaná pětice $(Q,\Sigma,\delta,Q_0,F)$, kde:
\list{o}
\:$Q$ je konečná neprázdná množina \em{stavů,}
\:$\Sigma$ je konečná neprázdná množina znaků -- \em{abeceda,}
\:$\delta: Q\times \Sigma \rightarrow 2^Q$ je \em{přechodová funkce,}
která každé dvojici $(\<stav>,\<znak>)$ přiřadí množinu všech stavů,
do kterých je možné přejít,
\:$Q_0\subseteq Q$ je množina \em{počátečních stavů,}
\:$F\subseteq Q$ je množina \em{přijímacích stavů.}
\endlist
}
Z~jednoho stavu tedy může vést více přechodů označených stejným znakem abecedy,
ale také nemusí vést žádný. Původní DFA tedy odpovídají těm NFA, kde $|\delta(s,x)|$ je vždy~1.
Výpočet automatu opět odpovídá nějakému sledu v~grafu. Sled začíná některým z~počátečních
stavů a jeho hrany jsou označeny znaky vstupního slova. Oproti deterministickému automatu
ale tento sled není jednoznačně určen a nemusí ani existovat. Totéž můžeme popsat jako posloupnost
stavů.
\defn{\em{Výpočet} nedeterministického automatu pro vstup $\alpha\in\Sigma^*$ je jakákoliv
posloupnost stavů $s_0,s_1,\ldots,s_{\vert\alpha\vert}$, pro níž platí:
\list{o}
\:$s_0 \in Q_0$,
\:$s_{i+1} \in \delta(s_i, \alpha[i])$.
\endlist
}
\defn{Slovo~$\alpha$ je \em{přijímáno automatem}, pokud existuje alespoň jeden výpočet
se vstupem~$\alpha$, který končí v~jednom z~přijímacích stavů. Stejně jako u~DFA říkáme
množině všech přijímaných slov \em{jazyk rozpoznávaný automatem} a značíme ho~$L(A)$.
}
\figure[nfa-strom]{nfa-strom.epdf}{}{Les výpočtů NFA z~obrázku \figref{nfa-kombinace} na vstup {\tt 00101}}
Možné výpočty pro daný vstup můžeme popsat lesem (sledujte příklad na obrázku \figref{nfa-strom}).
Kořeny stromů odpovídají počátečním stavům. Jejich děti obsahují stavy, do kterých vede přechodová funkce
z~počátečního stavu pro první znak vstupu. Každé z~těchto dětí má své děti odpovídající přechodům
pro druhý znak vstupu atd. Některé větve lesa skončí předčasně, když přechodová funkce vrátí
prázdnou množinu. Větve, které pokračují až na poslední hladinu, odpovídají výpočtům automatu.
Výpočtů pro jedno slovo (a~tedy listů lesa) může být exponenciálně mnoho.
Ale pokud nějaké dva vrcholy na téže hladině obsahují stejný stav, musí pod
nimi být izomorfní podstromy. Proto tyto vrcholy nemusíme rozlišovat -- stačí
pro každý prefix vstupu určit množinu stavů, v~nichž se může automat nacházet.\foot{%
Kdybychom tyto vrcholy sloučili, z~lesa se stane acyklický orientovaný graf
s~$\O(n\cdot|Q|)$ vrcholy, kde $n$ je délka vstupu.}
To popíšeme pomocí rozšířené přechodové funkce. Ta pro danou množinu počátečních stavů~$S$
a vstup~$\alpha$ řekne, v~jakých stavech může výpočet skončit.
\defn{\em{Rozšířená přechodová funkce} $\dstar: 2^Q \times \Sigma^* \rightarrow 2^Q$
je definována takto:
\list{o}
\:$\dstar(S,\varepsilon) = S$ pro všechny $S\subseteq Q$,
\:$\dstar(S,\alpha x) = \bigcup_{s\in \dstar(S,\alpha)} \delta(s,x)$ pro všechny
$S\subseteq Q$, $\alpha\in\Sigma^*$, $x\in\Sigma$.
\endlist
}
\obs{Slovo~$\alpha$ je přijato automatem právě tehdy, když $\dstar(Q_0,\alpha) \cap F \ne \emptyset$.
}
Příklad ze začátku oddílu ukazuje, že někdy je pohodlnější sestrojit nedeterministický
automat. Nyní ukážeme, že nedeterminismu se pak můžeme zbavit:
\theorem{Ke každému NFA~$A$ existuje DFA~$A'$ takový, že $L(A') = L(A)$.}
\proof
Budeme simulovat rozšířenou přechodovou funkci automatu~$A$ automatem~$A'$. Stavy~$A'$
tedy budou odpovídat množinám stavů automatu~$A$ a do přechodů mezi nimi zakódujeme
indukční krok z~definice rozšířené přechodové funkce. Nyní precizně.
Mějme NFA $A=(Q, \Sigma, \delta, Q_0, F)$.
Sestrojíme DFA $A'=(Q', \Sigma, \delta', q_0^\prime, F')$, přičemž:
\list{o}
\:$Q' = 2^Q$,
\:$\delta'(S,x) = \bigcup_{s\in S} \delta(s,x)$ pro všechny $S\in Q'$ a $x\in\Sigma$,
\:$q_0^\prime = Q_0$,
\:$F' = \{ S\in Q' \mid S\cap F \ne \emptyset \}$.
\endlist
Nyní si všimneme, že výpočet automatu~$A'$ pro vstup~$\alpha$ skončí
ve stavu, který je roven $\dstar(Q_0,\alpha)$. Tento stav je přijímací
právě tehdy, když automat~$A$ přijme slovo~$\alpha$.
\qed
\cor{Jazyk je rozpoznatelný nedeterministickým automatem právě tehdy, je-li regulární.}
\example{
Větu vyzkoušíme na NFA ze začátku kapitoly (obrázek \figref{nfa-kombinace}). Stavy DFA budou
$$Q' = \{ \emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\} \},$$
přičemž stav $\{a\}$ je počáteční a stavy $\{c\}$, $\{a,c\}$, $\{b,c\}$ a $\{a,b,c\}$
přijímací. Přechodová funkce bude vypadat následovně:
$$\vbox{\halign{~~$#$\hfil&\quad$#$\hfil&\quad$#$\hfil~~\cr
S&\delta(S,\0)&\delta(S,\1)\cr
\noalign{\smallskip\hrule\smallskip}
\emptyset & \emptyset & \emptyset \cr
\{a\} & \{a,b\} & \{a\} \cr
\{b\} & \emptyset & \{c\} \cr
\{c\} & \emptyset & \emptyset \cr
\{a,b\} & \{a,b\} & \{a,c\} \cr
\{a,c\} & \{a,b\} & \{a\} \cr
\{b,c\} & \emptyset & \{c\} \cr
\{a,b,c\} & \{a,b\} & \{a,c\} \cr
}}$$
}
Přitom pouze stavy $\{a\}$, $\{a,b\}$ a $\{a,c\}$ budou dosažitelné z~počátečního stavu,
takže všechny ostatní stavy můžeme vynechat. Výsledný automat vidíte na obrázku \figref{nfa-to-dfa}.
Sestrojenému automatu můžeme rozumět tak, že aktuální stav obsahuje~$a$ vždy,
$b$ jen tehdy, končí-li vstup na~\0, a~$c$ jen tehdy, končí-li vstup na \0\1.
Stejný automat bychom dostali z~Knuthova-Morrisova-Prattova algoritmu
na vyhledávání v~textu.
\figure[nfa-to-dfa]{nfa-to-dfa.epdf}{}{Převod NFA z~obrázku \figref{nfa-kombinace} na DFA}
\subsection{Epsilon-přechody}
Zapojení dvou automatů \uv{sériově} ztotožněním stavů má jeden potenciální háček:
pokud z~přijímacího stavu prvního automatu vedly nějaké přechody, může výpočet
přejít z~druhého automatu zpátky do prvního. Lepší by bylo zavést z~konce prvního
automatu do začátku druhého nějaký speciální přechod, který nepoužije žádný znak
ze vstupu. Takovým přechodům se říká $\varepsilon$-přechody a můžeme o~ně definici NFA
rozšířit.
\defn{\em{Nedeterministický konečný automat s~$\varepsilon$-přechody ($\varepsilon$-NFA)}
je definován stejně jako klasický NFA, jen přechodovou funkci rozšíříme
na $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^Q$.
}
Výpočet automatu můžeme opět popsat jako sled v~grafu, na jehož hranách přečteme vstupní
slovo. Hrany popsané~$\varepsilon$ přitom vynecháváme. Pozor na to, že je-li v~grafu cyklus
z~$\varepsilon$-hran, může pro jeden vstup existovat nekonečně mnoho výpočtů. Alternativně
můžeme přeskakování $\varepsilon$-hran popsat následovně:
\defn{\em{$\varepsilon$-uzávěr stavu~$s\in Q$} značíme $U_\varepsilon(s)$ a je to množina
všech stavů, do kterých se dá ze stavu~$s$ dostat po $\varepsilon$-hranách. Uzávěr
rozšíříme na množiny stavů: $U_\varepsilon(S) = \bigcup_{s\in S} U_\varepsilon(s)$.
}
\obs{Stav je vždy dosažitelný sám ze sebe, takže vždy platí $s\in U_\varepsilon(s)$.
Pro množiny je proto $S\subseteq U_\varepsilon(S)$.\foot{Navíc si můžeme všimnout, že
$U_\varepsilon(\emptyset)=\emptyset$ a $U_\varepsilon(S)\subseteq U_\varepsilon(T)$,
kdykoliv $S\subseteq T$. Funkcím s~těmito vlastnostmi se obecně říká uzávěrové operátory.}
}
\defn{\em{Výpočet} $\varepsilon$-NFA pro vstup $\alpha\in\Sigma^*$ je jakákoliv
posloupnost stavů $s_0,s_1,\ldots,s_{\vert\alpha\vert}$, pro níž platí:
\list{o}
\:$s_0 \in U_\varepsilon(Q_0)$,
\:$s_{i+1} \in U_\varepsilon(\delta(s_i, \alpha[i]))$.
\endlist
}
Jinými slovy na samém začátku výpočtu a po průchodu každou obyčejnou hranou
jsme přidali průchod po libovolně mnoha $\varepsilon$-hranách.
Přijímání slova a jazyk rozpoznávaný automatem definujeme stejně jako pro NFA.
Důležité je, že $\varepsilon$-přechody je možné eliminovat a získat tak obyčejný NFA.
\theorem{Pro každý $\varepsilon$-NFA $A$ existuje NFA~$A'$ takový, že $L(A') = L(A)$.
}
\proof
Množinu stavů ponecháme. Množinu počátečních stavů nahradíme jejím $\varepsilon$-uzá\-vě\-rem.
Přechodovou funkci také zkombinujeme s~$\varepsilon$-uzávěrem, tedy
$\delta'(S,x) = U_\varepsilon(\delta(S,x))$. Přijímací stavy ponecháme.
Pro každý vstup mají oba automaty stejnou množinu výpočtů, takže se shodnou na přijetí
respektive odmítnutí slova. Tím pádem přijímají tentýž jazyk.
\qed
\cor{Jazyk je rozpoznatelný $\varepsilon$-NFA právě tehdy, je-li regulární.}
\lemma{Každý $\varepsilon$-NFA je možné (při zachování rozpoznávaného jazyka)
upravit tak, aby měl jediný počáteční a jediný přijímací stav.
Navíc do počátečního stavu ani z~přijímacího stavu nepovedou žádné přechody.
}
\proof
Přidáme nový počáteční stav, z~nějž povedou $\varepsilon$-přechody do původních
počátečních stavů. Také přidáme nový přijímací stav, do kterého zavedeme
$\varepsilon$-přechody z~původních přijímacích stavů.
\qed
\subsection{Algoritmické otázky}
Jak těžké je zjistit, zda slovo patří do regulárního jazyka? Jak to závisí
na délce slova~$n$ a počtu stavů automatu~$p$? A~jak na druhu automatu?
Velikost abecedy budeme považovat za konstantu, která se \uv{schová do~$\O$}.
\list{o}
\:DFA můžeme odsimulovat v~čase $\O(n)$.
\:U~NFA můžeme simulovat rozšířenou přechodovou
funkci v~čase $\O(p^2)$ na krok, celkem tedy $\O(p^2 n)$. Nebo můžeme NFA
převést podmnožinovou konstrukcí na DFA -- to potrvá $\O(2^p\cdot p^2)$,
ale pak už vstup zpracujeme v~čase $\O(n)$.
\:$\varepsilon$-NFA převedeme v~čase $\O(p^3)$ na klasický NFA.
\endlist
\exercises
\ex{U~DFA platilo, že prohodíme-li přijímací a nepřijímací
stavy (tedy nahradíme~$F$ za $Q\setminus F$), dostaneme automat přijímací
doplněk původního jazyka. Platí to i~pro NFA?}
\exx{Podmnožinová konstrukce produkuje automaty s~exponenciálně mnoha stavy
vzhledem k~počtu stavů původního automatu. I~když často budou některé z~nich
nedosažitelné, nemusí tomu tak být vždy. Sestrojte pro každé~$t$ jazyk, který
lze rozpoznat pomocí NFA s~$\O(t)$ stavy, ale každý DFA, který ho rozpoznává,
má aspoň $2^t$ stavů.}
\ex{Vylepšete simulaci NFA, aby pracovala v~čase $\O(2^p\cdot p + n)$.}
\endexercises
\section{Regulární výrazy}
Hlavní motivací pro zavádění NFA byla touha po vytváření komplikovaných
regulárních jazyků z~jednodušších. Ukážeme, že s~$\varepsilon$-NFA je možné
sestrojit praktickou \uv{stavebnici regulárních jazyků}. Dokonce pak zjistíme,
že z~ní jdou sestavit úplně všechny regulární jazyky.
\subsection{Operace s~jazyky}
\defn{Pro jazyky~$X$ a~$Y$ nad abecedou~$\Sigma$ definujeme:
\list{o}
\:\em{sjednocení} $X\cup Y$ a \em{průnik} $X\cap Y$ jako běžné množinové operace
\:\em{doplněk} $\overline{X} = \Sigma^* \setminus X$
\:\em{zřetězení (konkatenaci)} $X\cdot Y = \{ \alpha\beta \mid \alpha\in X \land \beta\in Y \}$,
často tečku vynecháváme a píšeme prostě $XY$.
\:\em{mocninu} $X^k$: $X^0 = \{\varepsilon\}$, $X^{k+1} = X^k\cdot X$.
(Zjevně $X^1=X$, $X^2=XX$, $X^3=XXX$, přičemž uzávorkování není třeba určit,
neboť zřetězení je asociativní.)
\:\em{iteraci} $X^* = \bigcup_{n\ge 0} X^n$
\:\em{pozitivní iteraci} $X^+ = \bigcup_{n\ge 1} X^n$.
(Platí tedy $X^* = \{\varepsilon\} \cup X^+$.)
\:\em{otočení} $X\rev = \{ \alpha\rev \mid \alpha\in X \}$.
\endlist
}
\theorem{
Pokud $X$ a~$Y$ jsou regulární, všechny operace produkují opět regulární jazyky.
}
\proof
Automat pro \em{průnik} regulárních jazyků už umíme získat součinovou konstrukcí.
\em{Doplněk} jsme vyřešili v~cvičení \exref{regcompl}, \em{otočení} vyřešíme ve cvičení \exref{regrev}.
Pro zbývající operace ukážeme, že z~automatů pro $X$ a~$Y$ umíme sestrojit
automat pro výsledný jazyk. Budou se nám k~tomu hodit $\varepsilon$-automaty
s~jednoznačným počátečním i koncovým (přijímacím) stavem. Automat pro~$X$ označme~$A_X$,
jeho počáteční stav~$a_X$ a koncový stav~$z_X$. Podobně pro~$Y$.
Pro \em{sjednocení} vytvoříme nový počáteční stav~$a$ a nový koncový~$z$.
Přidáme $\varepsilon$-přechody $a\rightarrow a_X$, $a\rightarrow a_Y$,
$z_X\rightarrow z$, $z_Y\rightarrow z$.
Pro \em{zřetězení} stačí přidat $\varepsilon$-přechod ze~$z_X$ do~$a_Y$. Počátečním
stavem bude~$a_X$, koncovým~$z_Y$.
\em{Mocninu} realizujeme jako $k$-násobné zřetězení (pro $k=0$ stačí užít fakt,
že každý konečný jazyk je regulární).
Pro \em{pozitivní iteraci} stačí přidat $\varepsilon$-přechod z~koncového stavu
do počátečního. Obecná \em{iterace} potřebuje přijímat navíc slovo~$\varepsilon$:
na to stačí přidat ještě $\varepsilon$-přechod z~počátečního stavu do koncového.
\qed
\subsection{Regulární výrazy}
Postup, jak jazyk získat z~jednodušších pomocí jazykových operací, můžeme popsat
regulárním výrazem. To je buďto konstanta vyjadřující nějaký elementární jazyk,
nebo operace aplikovaná na jednodušší regulární výrazy. Každému regulárnímu výrazu
pak můžeme přiřadit nějaký jazyk \em{generovaný výrazem}, který budeme
značit obvyklým $L(\ldots)$.
Výčet operací najdete na obrázku~\figref{regex}.
\texfigure[regex]{\vbox{\halign{$#$&\quad \it #\hfil&\quad#\hfil\cr
\emptyset & prázdný jazyk & $L(\emptyset) = \emptyset$ \cr
\varepsilon & prázdné slovo & $L(\varepsilon) = \{\varepsilon\}$ \cr
x & znak abecedy & $L(x) = \{x\}$ \cr
X\alt Y & sjednocení & $L(X\alt Y) = L(X) \cup L(Y)$ \cr
XY & zřetězení & $L(XY) = L(X) \cdot L(Y)$ \cr
X^* & iterace & $L(X^*) = L(X)^*$ \cr
X^+ & pozitivní iterace & zkratka za $XX^*$ \cr
X? & možnost & zkratka za $X\alt\varepsilon$ \cr
}}}{Regulární výrazy a jimi generované jazyky. Nejnižší prioritu má operátor
sjednocení, vyšší zřetězení a nejvyšší obě iterace.}
\example{Slova z~$\{\0,\1\}^*$ končící na \0\1 můžeme popsat regulárním
výrazem $(\0\alt\1)^*\0\1$.
}
\example{Slova z~$\{\0,\1\}^*$, ve kterých se pravidelně střídají \0 a~\1,
můžeme popsat výrazem $(\0\1)^* \mid (\1\0)^* \mid (\0\1)^*\0 \mid (\1\0)^*\1$,
případně jednodušeji $\1?(\0\1)^*\0?$.
}
Už víme, že jazyky generované regulárnimi výrazy jsou vždy regulární.
Překvapivě tak jde vygenerovat úplně každý regulární jazyk:
\theoremn{Kleeneho}{Jazyk je generovaný regulárním výrazem právě tehdy,
je-li regulární.
}
\proof
Zbývá dokázat implikaci zprava doleva. Mějme nějaký regulární jazyk~$L$ a DFA~$A$, který
tento jazyk rozpoznává. Automat budeme postupně zmenšovat, přičemž hrany mezi stavy
budou ohodnoceny nejen znaky abecedy, ale obecnými regulárními výrazy. Výpočet může
hranou projít, kdykoliv přečteme ze vstupu slovo vyhovující danému regulárnímu výrazu.
Nejprve přidáme nový počáteční stav~$a$ a přijímací stav~$z$ tak, aby do~$a$ ani ze~$z$
nevedly žádné hrany. To provedeme stejně jako u~$\varepsilon$-NFA, přičemž roli $\varepsilon$-přechodu
zde má hrana ohodnocená regulárním výrazem~$\varepsilon$.
Nyní na automat budeme aplikovat dva typy úprav:
\list{o}
\:{\I Sloučení hran} -- pokud mezi nějakými dvěma stavy vede více paralelních
hran, nahradíme je jedinou hranou ohodnocenou sjednocením regulárních výrazů z~původních hran.
\:{\I Eliminace stavu} -- vybereme si nějaký stav~$s$ různý od počátečního a přijímacího.
Tento stav odstraníme a zařídíme, aby všechny výpočty, které procházely tímto stavem,
použily nějakou \uv{zkratku}, která ho obejde. Pro každou dvojici stavů $x$ a~$y$
takovou, že z~$x$ vede do~$s$ hrana s~ohodnocením~$R_x$ a z~$s$ do~$y$ hrana s~ohodnocením~$y$,
přidáme zkratku z~$x$ do~$y$:
\list{o}
\:Pokud ve stavu~$s$ není smyčka (hrana z~$s$ do~$s$), bude zkratka
ohodnocena výrazem $R_x R_y$.
\:Pokud ve stavu~$s$ je smyčka s~ohodnocením~$R_s$, zkratku ohodnotíme
výrazem $R_xR_s^*R_y$.
\endlist
\endlist
Tyto kroky budeme střídat, než z~automatu zbude pouze počáteční a přijímací stav,
mezi nimiž povede jediná hrana. Jelikož oba druhy úprav zachovávají jazyk rozpoznávaný
automatem, ohodnocením zbývající hrany bude regulární výraz generující jazyk automatu.
Ještě dodejme, že stejný postup by fungoval i pro NFA nebo $\varepsilon$-NFA.
\qed
\example{
Postup si vyzkoušíme na jazyku dvojkových čísel dělitelných třemi.
Sestrojit regulární výraz pro tento jazyk není přímočaré, tak to zkusíme
pomocí Kleeneho věty. Na obrázku \figref{kleene} vidíme automat rozpoznávající
tento jazyk (inspiraci nacházíme v~cvičení \exref{bindiv5}) a jednotlivé
kroky z~důkazu věty. Dostáváme regulární výraz
$$(\0\alt \1\1\alt \1\0(\1\alt \0\0)^*\0\1)^*.$$
Zkuste najít vysvětlení jednotlivých částí výrazu, aniž byste se odkázali na automat.
}
\figure[kleene]{kleene.epdf}{width \hsize}{Převod automatu pro dělitelnost 3 na regulární výraz}
\note{UNIXové nástroje (například \|grep| a \|sed| používají nejrůznější varianty regulárních
výrazů, které se od těch našich liší pouze detaily notace. Jinde (například v~Perlu) ale najdeme
\uv{regulární} výrazy vybavené i schopností zpětných odkazů a rekurze. Ty dokáží popsat i mnohé
neregulární jazyky, ale algoritmy používané k~jejich vyhodnocování nemají polynomiální časovou
složitost.
}
\exercises
\ex[regrev]{Dokažte, že pro regulární jazyk~$X$ je jeho otočení~$X\rev$ také regulární.
}
\ex{Jak vypadá jazyk $X^{**}$?}
\ex{Napište regulární výraz, který generuje jazyk všech slov nad abecedou
$\{\0,\1\}$, jejichž počet jedniček je sudý nebo dělitelný třemi. Sestrojte
odpovídající $\varepsilon$-NFA, ten převeďte na NFA a~ten konečně na DFA.
}
\ex{Napište regulární výraz pro jazyk všech desítkových zápisů přirozených čísel
(nedovolujeme nestandardní zápisy typu \|0123| nebo~$\varepsilon$).
Podobně pro desetinná čísla (např. \|3.1415|) a desetinná s~periodou
(značíme \|0.0[01]|).
}
\ex{Napište regulární výraz pro jazyk všech slov nad abecedou $\{\0,\ldots,\9\}$,
která jsou neklesající (\|1377| v~tomto jazyce leží, \|735| nikoliv).
}
\ex{Vytvořte regulární výraz pro dvojkové zápisy čísel nedělitelných třemi.
Doporučujeme nejprve sestrojit DFA a pak použít konstrukci z~důkazu Kleeneho věty.
}
\ex{Uvažme jazyk všech slov nad abecedou $\{\|a|, \|b|, \|c|\}$, která
neobsahují podslovo \|abc|. Popište tento jazyk regulárním výrazem. Pokuste se
o~to přímo. Pak zkuste vytvořit DFA pro jazyk slov obsahujících \|abc|,
podle cvičení \exref{regcompl} vyrobit DFA pro jeho doplněk a na ten použít
konstrukci z~důkazu Kleeneho věty.
}
\ex{Navrhněte co nejefektivnější algoritmus, který zjistí, zda zadané slovo je
generované zadaným regulárním výrazem.
}
\exx{V~důkazu Kleeneho věty jsme použili automat, který má na hranách regulární
výrazy. Tento koncept můžeme zobecnit: \em{automat 2. řádu} má na každé hraně
nějaký jazyk, hranou je možné projít, pokud ze vstupu přečteme slovo z~jejího jazyka.
To zahrnuje nedeterminismus i automaty s~$\varepsilon$-přechody.
Definujte pro tyto automaty výpočet a rozšířenou přechodovou funkci.
Dokažte, že pokud jazyky hran jsou regulární, jazyk rozpoznávaný automatem
je také regulární.}
\exx{\em{Homomorfismus} je libovolné zobrazení $h: \Sigma^* \rightarrow \Delta^*$ takové, že
$h(\varepsilon) = \varepsilon$ a $h(\alpha\beta) = h(\alpha)h(\beta)$. Je tedy
jednoznačně určen obrazy jednoznakových řetězců, tj. funkcí $h_1: \Sigma \rightarrow \Delta^*$.
Homomorfismus můžeme rozšířit na jazyky: $h(L) = \{ h(\alpha) \mid \alpha\in L \}$.
Dokažte, že je-li $L$ regulární, pak $h(L)$ také.
}
\exx[subst]{\em{Substituce} je zobecnění homomorfismu, které znakům nepřiřazuje slova,
ale rovnou jazyky. Je tedy určený nějakou funkcí $s: \Sigma \rightarrow 2^{\Delta^*}$,
kterou můžeme rozšířit na slova: $s(\alpha\beta) = s(\alpha)\cdot s(\beta)$,
a~dokonce na jazyky: $s(L) = \bigcup_{\alpha\in L} s(\alpha)$. Tedy pokud $L$ je jazyk nad abecedou~$\Sigma$,
je $s(L)$ jazyk nad abecedou~$\Delta$.
Dokažte, že je-li $L$ regulární a všechny $s(x)$ regulární, tak $s(L)$ je také regulární.
}
\ex{Použití substituce:
Jazyky $\{\|a|, \|b|\}$, $\{\|ab|\}$ a $\{\|a|^*\}$ jsou regulární.
Pomocí substituce dokažte, že sjednocení, zřetězení a iterace libovolných
regulárních jazyků jsou opět regulární.
}
\ex{Odhadněte délku regulárního výrazu z~důkazu Kleeneho věty v~závislosti na počtu
stavů automatu.}
\exx{\em{Jiný důkaz Kleeneho věty:} Inspirujte se Floydovým-Warshallovým algoritmem
na výpočet matice vzdáleností v~grafu (kapitola 6.4 v~Průvodci). Stavy očíslujeme od~1
do~$n$. Pak pro $k$ od~0 do~$n$ definujeme regulární výrazy $R^k_{ij}$ popisující
všechny sledy ze stavu~$i$ do stavu~$j$, jejichž vnitřní stavy leží v~množině $\{1,\ldots,k\}$.
Ukažte, jak tyto výrazy počítat indukcí podle~$k$ a jak z~nich získat regulární výraz
pro jazyk automatu. Srovnejte délky výrazu s~předchozím cvičením.
}
\endexercises
\sectionstar{Redukce automatů}
Už jsme se vybavili řadou nástrojů, které nám umožňují snadno sestrojit automat
rozpoznávající zadaný jazyk. Tyto automaty ale bývají dost složité. V~tomto oddílu
prozkoumáme, jak automaty zjednodušovat.
\figure[dfa-reduce]{redukce.epdf}{width 0.8\hsize}{Automat a jeho redukce}
Prohlédněme si automat na obrázku \figref{dfa-reduce} vlevo,
pracující nad abecedou $\{\|a|, \|b|\}$.
Zřejmě rozpoznává jazyk generovaný regulárním výrazem $(\|a|\mid\|b|)\;\|a|^*\|b|\;(\|a|\mid\|b|)^*$.
Tentýž jazyk lze ovšem rozpoznávat i automatem vpravo, který má pouhé 3~stavy.
Zamysleme se nad tím, jakých stavů bychom se v~levém automatu dokázali zbavit:
\list{o}
\:Především můžeme odstranit stav~5, protože není z~počátečního stavu~0 dosažitelný
-- v~grafu do něj z~0 nevede žádná cesta.
\:Stavy 3 a~4 není potřeba rozlišovat: oba jsou přijímací a po zpracování
libovolného slova automat skončí zase v~přijímacím stavu. Můžeme je tedy
sloučit do společného stavu 34, který bude přijímací a jak~\|a|, tak~\|b| povedou
opět do stavu 34.
\:Stavy 1 a~2 také není potřeba rozlišovat: v~obou platí, že \|b| nás posune
do stavu 34, zatímco po \|a| zůstaneme v~1 nebo~2. Opět je můžeme sloučit
do společného stavu 12. (Naproti tomu 12 a 34 se chovají jinak, například se
liší tím, zda jsou přijímací.)
\endlist
Tím jsme z~levého automatu vytvořili pravý -- ten je daleko jednodušší, ale pořád přijímá
tentýž jazyk. Nyní se tento proces pokusíme popsat obecně.
\defn{Stav $s\in Q$ je \df{dosažitelný,} pokud existuje slovo $\alpha\in\Sigma^*$ takové,
že $\delta^*(q_0,\alpha) = s$.
}
Dosažitelné stavy jsou přesně ty, do nichž ze stavu~$q_0$ vede cesta. Tím pádem
je můžeme najít prohledáním automatu do šířky. Odstraníme-li všechny nedosažitelné
stavy, nezmění se množina možných výpočtů, a~tím pádem ani jazyk přijímaný automatem.
\defn{Stavy $s,t\in Q$ jsou \df{ekvivalentní} (značíme $s\approx t$), pokud pro
každé slovo $\alpha\in\Sigma^*$ platí $\delta^*(s,\alpha)\in F$, právě když
$\delta^*(t,\alpha)\in F$.
}
To znamená, že výpočty začínající ve stavech $s$ a~$t$ se po zpracování libovolného slova~$\alpha$
shodnou na tom, zda slovo přijaly.
Stavy, které nejsou ekvivalentní, jdou \df{oddělit} nějakým slovem~$\alpha$,
na jehož přijetí se výpočty neshodnou.
Snadno ověříme, že relace~$\approx$ je opravdu ekvivalence (je reflexivní,
symetrická a tranzitivní). Počítat ji podle definice není praktické, protože
bychom museli otestovat nekonečně mnoho slov. Ukážeme, že ji lze počítat
indukcí.
\defn{Stavy $s,t\in Q$ jsou \df{ekvivalentní do délky~$k$} (značíme $s\approx_k t$),
pokud nejdou oddělit žádným slovem délky nejvýše~$k$. Tedy
$(\delta^*(s,\alpha)\in F) \Leftrightarrow (\delta^*(t,\alpha)\in F)$,
kdykoliv $|\alpha|\le k$.
}
\obs{\list{o}
\:Je-li $s\approx_{k+1} t$, platí také $s\approx_k t$. Ekvivalence~$\approx_{k+1}$ je tedy
\em{zjemněním} ekvivalence~$\approx_k$, tedy $\mathord{\approx_{k+1}} \subseteq \mathord{\approx_k}$
a třídy jemnější ekvivalence jsou podmnožinami tříd hrubší ekvivalence.
\:$s\approx t$ platí právě tehdy, když je $s\approx_k t$ pro všechna~$k$.
\:Stavy $s$ a~$t$ jsou odděleny prázdným slovem právě tehdy, je-li jeden z~nich
přijímací a druhý nepřijímací.
\:Stavy $s$ a~$t$ jsou odděleny neprázdným slovem $\alpha=x\alpha'$ délky~$k$
právě tehdy, když jsou stavy $s'=\delta(s,x)$ a $t'=\delta(t,x)$ odděleny
slovem~$\alpha'$ délky $k-1$.
\endlist
}
Z~toho plyne:
$$\eqalign{
&(s\approx_0 t) \Longleftrightarrow (s\in F \Leftrightarrow t\in F) \cr
&(s\approx_{k+1} t) \Longleftrightarrow (s\approx_0 t) \land (\forall x\in\Sigma: \delta(s,x) \approx_k \delta(t,x)) \cr
}$$
To nám dává induktivní postup na sestrojení všech ekvivalencí~$\approx_k$.
Jelikož každá další ekvivalence je zjemněním té předchozí a tříd není nikdy
víc než stavů automatu, musí se zjemňování po konečně mnoha krocích zastavit
s~$\mathord{\approx_{k+1}} = \mathord{\approx_k}$.
Z~toho ovšem plyne $\mathord{\approx_\ell} = \mathord{\approx_k}$ pro všechna $\ell > k$,
a~tím pádem i $\mathord{\approx} = \mathord{\approx_k}$.
\example{Sestrojíme ekvivalence pro automat z~obrázku \figref{dfa-reduce} bez nedosažitelného stavu~5.
\tightlist{o}
\:$\approx_0$ má třídy:
$$\halign{\hbox to 5em{\hfil$#$}&\hbox to 7em{${}#$\hfil}&#\hfil\cr
A&=\{0,1,2\} & nepřijímací \cr
B&=\{3,4\} & přijímací \cr
}$$
\:$\approx_1$ má třídy:
$$\halign{\hbox to 5em{\hfil$#$}&\hbox to 7em{${}#$\hfil}&#\hfil\cr
C&=\{0\} & nepřijímací, znaky \|a| i~\|b| vedou do stavů z~třídy~$A$ \cr
D&=\{1,2\} & nepřijímací, \|a| vede do~$A$, \|b| do~$B$ \cr
E&=\{3,4\} & přijímací, \|a| i~\|b| vedou do~$B$ \cr
}$$
\:$\approx_2$ má třídy:
$$\halign{\hbox to 5em{\hfil$#$}&\hbox to 7em{${}#$\hfil}&#\hfil\cr
F&=\{0\} & nepřijímací, znaky \|a| i~\|b| vedou do stavů z~třídy~$D$ \cr
G&=\{1,2\} & nepřijímací, \|a| vede do~$D$, \|b| do~$E$ \cr
H&=\{3,4\} & přijímací, \|a| i~\|b| vedou do~$E$ \cr
}$$
\:Ekvivalence~$\approx_2$ vyšla stejná jako~$\approx_1$, takže máme hotovou plnou ekvivalenci~$\approx$.
\endlist
}
Nyní ukážeme, jak ekvivalentní stavy sloučit:
\defn{Nechť $A=(Q,\Sigma,\delta,q_0,F)$ DFA, $\approx$ ekvivalence jeho stavů
a pro každý stav $s\in Q$ je $[s]$ jeho ekvivalenční třída.
Pak definujeme \df{faktorový automat} $A/\mathord{\approx} = (Q',\Sigma,\delta',q'_0,F')$, kde:
\tightlist{o}
\:$Q' = \{[s] \mid s\in Q\}$,
\:$\delta'([s],x) = [t]$, kdykoliv $\delta(s,x)=t$,
\:$q'_0 = [q_0]$,
\:$F' = \{[s] \mid s\in F\}$.
\endlist
}
\note{
Stavy faktorového automatu jsou tedy ekvivalenční třídy stavů původního
automatu. Přechod z~ekvivalenční třídy $S$ do $T$ přes znak~$x$ odpovídá
přechodu mezi $s\in S$ do $t\in T$ přes~$x$ v~původním automatu.
Z~vlastností relace~$\approx$ přitom plyne, že nezáleží na volbě reprezentantů $s$ a~$t$:
pro každé $s,s'\in S$ a $x\in\Sigma$ je $sx \approx s'x$.
Podobně třída je přijímací, pokud stavy v~ní ležící byly v~původním automatu přijímací;
opět se na tom všichni reprezentanti třídy shodnou.
}
\lemma{
Faktorizací automatu se nezmění přijímaný jazyk.
}
\proof
Indukcí podle délky řetězce dokážeme, že pro každý řetězec~$\alpha$ platí
$\delta'(q'_0,\alpha) = \delta'([q_0],\alpha) = [\delta(q_0,\alpha)]$.
Tento stav leží v~$F'$ právě tehdy, když $\delta(q_0,\alpha)$ leží v~$F$.
\qed
\example{Z~levého automatu na obrázku \figref{dfa-reduce} dostaneme faktorizací pravý automat.}
\defn{
Automat je \df{redukovaný,} pokud jsou všechny jeho stavy dosažitelné a žádné
dva stavy nejsou ekvivalentní.
}
Z~předchozích úvah přímo plyne:
\theorem{
Nechť z~automatu~$A$ vznikne automat~$A'$ odstraněním nedosažitelných stavů a následnou faktorizací.
Pak automat~$A'$ je redukovaný a přijímá stejný jazyk jako~$A$.
}
V~příštím oddílu navíc dokážeme, že všechny redukované automaty přijímající
tentýž jazyk jsou v~nějakém smyslu izomorfní.
\subsection{Algoritmus na ekvivalenci stavů}
Nyní konstrukci ekvivalence stavů formulujeme jako algoritmus.
Postupně budeme vytvářet ekvivalence~$\approx_k$. Budeme je reprezentovat pomocí
ekvivalenčních tříd očíslovaných přirozenými čísly. Pro každy stav~$s$ si budeme
pamatovat číslo $t[s]$ třídy, kam patří.
\algo{EkvivalenceStavů}
\algin Automat $(Q,\Sigma,\delta,q_0,F)$
\:Vytvoříme počáteční ekvivalenci~$\approx_0$:
\::Pro všechny stavy $s\in Q$:
\:::Je-li $s\in F$, pak $t[s]\=2$, jinak $t[s]\=1$.
\::$p \= 2$ \cmt{počet tříd}
\:Pro $k=1,2,\ldots,|Q|$: \cmt{postupně vytváříme další ekvivalence~$\approx_k$}
\::Pro všechny stavy $s\in Q$:
\:::$a_s \= \hbox{pole nul indexované abecedou rozšířenou o~$\varepsilon$}$
\:::$a_s[\varepsilon] \= t[s]$
\:::Pro všechny znaky $x\in\Sigma$:
\::::$a_s[x] \= t[\delta(s,x)]$
\::Setřídíme všechna $a_s$ lexikograficky.
\::Očíslujeme nové ekvivalenční třídy:
\:::$i \= 0$
\:::Pro všechna $a_s$ v~setříděném pořadí:
\::::Pokud $a_s$ je první nebo různé od svého předchůdce:
\:::::$i \= i + 1$
\::::$t[s] \= i$
\:::Je-li $i = p$, skončíme.
\:::$p \= i$
\algout Ekvivalence~$\approx$ popsaná polem~$t$ čísel tříd.
\endalgo
Při konstrukci ekvivalence~$\approx_k$ algoritmus každému stavu~$s$ přiřadí jeho \em{kód:}
$(|\Sigma|+1)$-tici čísel indexovanou znaky abecedy rozšířené o~$\varepsilon$.
Na $x$-té pozici leží číslo ekvivalenční třídy v~$\approx_{k-1}$, do níž padne $\delta(s,x)$.
Na pozici~$\varepsilon$ leží číslo původní ekvivalenční třídy.
Dva stavy jsou pak ekvivalentní v~$\approx_k$ právě tehdy, když dostaly stejný kód.
Stačí tedy kódy setřídit a pro každou skupinu stejných kódů založit ekvivalenční třídu.
Jaká je složitost tohoto algoritmu v~závislosti na počtu stavů $S = |Q|$ a velikosti abecedy $A = |\Sigma|$?
Hlavní smyčka přes~$k$ proběhne nejvýš $S$-krát, pak už nemůže ekvivalenčních tříd přibývat.
Pro každou ekvivalenci sestrojíme $S$ kódů délky~$A+1$, což trvá $\Theta(SA)$.
V~tomto čase je stihneme i přihrádkově setřídit a očíslovat nové ekvivalenční třídy.
Algoritmus tedy doběhne v~čase $\Theta(S^2A)$.
\exercises
\ex{Dokažte, že vyhledávací automaty typu Knuth-Morris-Pratt (viz oddíl \secref{dfa}) jsou redukované.
}
\ex{Platí totéž o~vyhledávacích automatech typu Aho-Corasicková?
}
\ex{Navrhněte, jak pomocí ekvivalence stavů zjistit, zda dva automaty přijímají stejný jazyk.}
\ex{Funguje myšlenka ekvivalence stavů a faktorizace automatu i pro nedeterministické automaty?}
\endexercises
\sectionstar{Algebraické souvislosti}
{\bf Pozor! Tato kapitola je ve vývoji.}
V~tomto oddílu prozkoumáme některé souvislosti mezi teorií automatů
a algebrou. Předpokládáme čtenáře zběhlého v~základech algebry, takže
důkazy jsou zde poněkud hutnější.
\subsection{Monoidy a polookruhy}
\defn{
\df{Monoid} je algebraická struktura $(X,\cdot,1)$, kde $X$ je množina prvků,
$\cdot$ nějaká asociativní binární operace a~$1$ její jednotkový prvek (platí
$1\cdot x = x\cdot 1 = x$ pro všechna $x\in X$).
Pokud $\cdot$ navíc komutuje, mluvíme o~komutativním monoidu.
}
\examples{\tightlist{o}
\:Celá čísla s~násobením a jednotkovým prvkem~1 tvoří komutativní monoid.
\:Funkce z~$\{1,\ldots,n\}$ do $\{1,\ldots,n\}$ spolu se skládáním funkcí a identitou
tvoří monoid, který pro $n>1$ není komutativní.
\endlist
}
\defn{
Nad libovolnou abecedou~$\Sigma$ můžeme definovat monoid $(\Sigma^*, \cdot, \varepsilon)$.
Jeho prvky řetězce, binární operace je zřetězení (rozmyslete si asociativitu)
a jako jednotkový prvek slouží prázdný řetězec~$\varepsilon$. Tomuto monoidu se říká
\df{volný monoid} nad abecedou~$\Sigma$ nebo také \df{monoid řetězců}.
}
\defn{
\df{Polookruh} je algebraická struktura $(X,+,\cdot,0,1)$, kde $+$ a~$\cdot$ jsou
binární operace, $(X,\cdot,1)$ tvoří monoid, $(X,+,0)$ tvoří komutativní monoid
a operace $+$ a~$\cdot$ jsou svázány distributivitou z~obou stran:
$$
x\cdot (y+z) = x\cdot y + x\cdot z, \quad
(x+y)\cdot z = x\cdot z + y\cdot z.
$$
Pokud navíc $\cdot$ komutuje, mluvíme o~komutativním polookruhu.
}
\note{
Častěji potkáváme \em{grupu} (monoid, v~němž existuje inverze k~násobení),
\em{okruh} (polookruh, v~němž existuje inverze ke sčítání) a
\em{těleso} (okruh, v~němž existuje inverze k~násobení kromě~0).
}
\examples{\tightlist{o}
\:Celá čísla $(\Z,+,\cdot,0,1)$ s~běžnými operacemi tvoří komutativní okruh.
\:Matice $\R^{n\times n}$ spolu s~maticovým sčítáním a násobením,
nulovou maticí a jednotkovou maticí tvoří okruh, který pro $n>1$ nekomutuje.
\:Booleova algebra $(\{0,1\},\lor,\land,0,1)$ tvoří komutativní polookruh.
\endlist}
\defn{
Uvažme množinu $2^{\Sigma^*}$ všech jazyků nad abecedou~$\Sigma$.
Když k~ní přidáme operaci $\cup$ sjednocení jazyků s~jednotkovým prvkem~$\emptyset$
a operaci $\cdot$ zřetězení jazyků s~jednotkovým prvkem~$\{\varepsilon\}$,
vznikne polookruh. Říkáme mu \df{polookruh jazyků} nad~$\Sigma$.
}
\note{
Snadno ověříme, že $\cup$ komutuje, $\cdot$ nekomutuje a tyto dvě operace
jsou svázány distributivitou $(A\cup B)\cdot C = A\cdot C \cup B\cdot C$
a analogicky z~opačné strany.
}
\subsection{Lineární rovnice pro jazyky}
Pojďme prozkoumat, jak se chovají rovnice typu $X=AX\cup B$, kde $X$ je neznámý
jazyk a $A$ a~$B$ známé jazyky. To je analogie lineárních rovnic, jen v~okruhu jazyků
místo tělesa reálných čísel. Aby analogie lépe vynikla, budeme na chvíli psát $+$ místo~$\cup$.
\lemma{Pro každé dva jazyky $A$ a~$B$ existuje jazyk~$X$ takový, že $X=AX+B$.
Pokud jazyk~$A$ neobsahuje prázdné slovo, je~$X$ jednoznačně určen.
Navíc $X$ lze z~$A$ a~$B$ získat operacemi regulárních výrazů.
}
\proof
Začněme existencí. Ukážeme, že $X=A^*B$ rovnici splňuje. Dosazením získáme
$AX+ B = A(A^*B) + B = A^+B + B = (A^+ + \{\varepsilon\})B = A^*B = X$.
Nyní jednoznačnost. Nechť $\varepsilon\not\in A$ a $X_1$, $X_2$ jsou dvě řešení
rovnice. Platí tedy $X_1 = AX_1 + B$ a $X_2 = AX_2 + B$.
Ukážeme, že každé $\alpha\in X_1$ leží také v~$X_2$ (prohozením $X_1$
a~$X_2$ pak získáme, že $X_1=X_2$).
Pro spor předpokládejme, že existuje nějaké \uv{špatné} $\alpha\in X_1\setminus X_2$.
Zvolme nejkratší takové~$\alpha$. Jelikož $\alpha\in AX_1+ B$. Jelikož $B$ je součástí
jak~$X_1$, tak~$X_2$, nemůže být $\alpha\in B$. Platí tedy $\alpha\in AX_1$. Z~toho plyne,
že $\alpha$ se dá zapsat jako $\alpha'\xi$, kde $\alpha'\in A$ a $\xi\in X_1$. Jelikož
$A$ neobsahuje prázdné slovo, naše~$\alpha'$ je neprázdné, takže $\xi$ musí být kratší
než~$\alpha$. Ovšem $\alpha$ bylo nejkratší špatné slovo, tedy $\xi$ je dobré. Proto
musí $\xi$ ležet nejen v~$X_1$, ale i v~$X_2$. Takže $\alpha'\xi \in AX_2 \subseteq X_2$,
což je ve sporu s~tím, že $\alpha$ bylo špatné.
\qed
Dále uvažme soustavu lineárních rovnic tvaru
$$\eqalign{
X_1 &= A_{11}X_1 + A_{12}X_2 + \ldots + A_{1m}X_m + B_1 \cr
X_2 &= A_{21}X_1 + A_{22}X_2 + \ldots + A_{2m}X_m + B_2 \cr
&\vdots \cr
X_n &= A_{n1}X_1 + A_{n2}X_2 + \ldots + A_{nm}X_m + B_n \cr
}\eqno{(*)}$$
Tuto soustavu můžeme řešit postupem podobným Gaussově eliminaci.
\lemma{
Pokud žádný z~jazyků $A_{ij}$ neobsahuje prázdné slovo, má soustava rovnic
$(*)$ právě jedno řešení $X_1$, \dots, $X_n$. Toto řešení lze z~jazyků
$A_{ij}$ a~$B_i$ vyjádřit operacemi regulárních výrazů.
}
\proof
Postupujeme indukcí podle~$n$. Případ $n=1$ odpovídá předchozímu lemmatu.
Nyní ukážeme, jak řešení soustavy $n>1$ rovnic převést na řešení soustavy $n-1$ rovnic.
Použijeme předchozí lemma na první rovnici.
Získáme jednoznačné $X_1 = A_{11}^*(A_{12}X_2 + \ldots + A_{1m}X_m + B_1)$.
Pomocí toho můžeme eliminovat~$X_1$ ze všech ostatních rovnic:
$$
X_i = A_{i1}X_1 + A_{i2}X_2 + \ldots + A_{im}X_m + B_i
$$
přepíšeme na
$$
X_i = A_{i1}A_{11}^*(A_{12}X_2 + \ldots + A_{1m}X_m + B_1) + A_{i2}X_2 + \ldots + A_{im}X_m + B_i,
$$
což můžeme upravit:
$$
X_i = (A_{i1} A_{11}^* A_{12} + A_{i2}) X_2 + \ldots +
(A_{i1} A_{11}^* A_{1m} + A_{im}) X_m + B_i,
$$
čili
$$
X_i = A'_{i2} X_2 + \ldots + A'_{im} X_m + B_i.
$$
To je soustava $n-1$ rovnic o~$n-1$ neznámých, jejíž koeficienty $A'_{ij}$
jsou zase jazyky neobsahující prázdné slovo. Podle indukčního předpokladu
má jednoznačné řešení, k~němuž umíme jednoznačně doplnit~$X_1$ a získat tak
řešení původní soustavy.
\qed
\cor{
Pokud jsou všechny koeficienty soustavy regulární jazyky, řešení $X_1$, \dots, $X_n$
je také tvořeno regulárními jazyky.
}
\cor{
Řešení soustav rovnic nám dává alternativní důkaz Kleeneho věty (její netriviální implikace).
Mějme deterministický automat s~počátečním stavem~$q_0$ a dalšími stavy $q_1$, \dots, $q_n$.
Sestavíme soustavu rovnic pro jazyky $X_0$ až~$X_n$, přičemž $X_i = \{ \alpha\in\Sigma^* \mid
\delta^*(q_i,\alpha) \in F \}$ je jazyk všech slov přijímaných výpočty začínajícími v~$q_i$.
Speciálně $X_0$ je tedy jazyk přijímaný automatem.
Kdy je $\alpha\in X_i$? Buďto $\alpha=\varepsilon$ a $q_i$ je přijímací stav. Nebo
je $\alpha=x\alpha'$, přechod z~$q_i$ přes znak~$x$ nás posune do nějakého~$q_j$
a $\alpha'\in X_j$. To dává rovnici
$$
X_i = A_{i0}X_0 + \ldots + A_{in}X_n + B_i,
$$
kde $A_{ij} = \{ x\in\Sigma \mid \delta(q_i,x) = q_j \}$
a $B_i=\{\varepsilon\}$, pokud $q_i$ je přijímací stav, a~jinak $B_i=\emptyset$.
Vytvořili jsme soustavu $n+1$ rovnic o~$n+1$ neznámých, jejíž koeficienty
$A_{ij}$ neobsahují prázdné slovo. Podle předchozího lemmatu má tedy jednoznačné
řešení. Z~něj si vybereme jazyk~$X_0$ a zapíšeme ho jako regulární výraz.
To vyjde, neboť koeficienty soustavy jsou konečné, a~tedy regulární jazyky
a řešení soustavy z~nich umíme vyjádřit pomocí operací regulárních výrazů.
}
\subsection{Izomorfismus automatů}
Mnoha různými odvětvími matematiky se jako červená nit vine pojem \em{izomorfismu.}
Odhlédneme-li od detailů, vždy se tím myslí bijekce mezi nějakými dvěma množinami,
která zachovává nějaké vlastnosti.
\example{Izomorfismus neorientovaných grafů $G=(V,E)$ a $G'=(V',E')$ je bijekce
$f: V\rightarrow V'$, která zachovává vlastnost \uv{být spojen hranou}.
Tedy $\{u,v\}\in E$ právě tehdy, když $\{f(u),f(v)\} \in E'$.
Existuje-li taková bijekce, řekneme, že grafy $G$ a~$G'$ jsou izomorfní,
a představujeme si, že se liší jenom pojmenováním vrcholů. Snadno nahlédneme, že vlastnost
\uv{být izomorfní} je ekvivalence na grafech.
}
Podobně můžeme definovat izomorfismus konečných automatů.
\defn{\df{Izomorfismus automatů} $A = (Q,\Sigma,\delta,q_0,F)$ a $A' = (Q',\Sigma,\delta',q'_0,F')$
je bijekce $f: Q\rightarrow Q'$, pro kterou platí:
\list{o}
\:$f(q_0) = q'_0$,
\:$s\in F \Leftrightarrow f(s)\in F'$,
\:$\delta(s,x) = t \Leftrightarrow \delta'(f(s),x) = f(t)$.
\endlist
Pokud taková bijekce existuje, řekneme, že automaty $A$ a~$A'$ jsou izomorfní, což značíme $A\cong A'$.
}
\obs{
Relace~$\cong$ je ekvivalence na automatech.
}
\note{
Izomorfismus tedy zachovává vlastnosti \uv{být počáteční stav}, \uv{být koncový stav}
a přechody mezi stavy. Izomorfní automaty se tedy liší jen pojmenováním stavů. S~touto
představou je následující tvrzení jen cvičením z~dosazování do definic:
}
\lemma{
Izomorfní automaty rozpoznávají tentýž jazyk.
}
\proof
Nechť mezi automaty $A=(Q,\Sigma,\delta,q_0,F)$ a $A'=(Q',\Sigma,\delta',q'_0,F')$ vede izomorfismus~$f$.
Uvažme slovo $\alpha\in\Sigma^*$ délky~$n$ a výpočet automatu~$A$ nad tímto slovem. To je nějaká posloupnost stavů
$q_0=s_0,s_1,\ldots,s_n$. Funkce~$f$ tento výpočet zobrazí na posloupnost stavů
$s'_0=f(s_0),s'_1=f(s_1),\ldots,s'_n=f(s_n)$.
Ověříme, že tato posloupnost je výpočtem automatu~$A'$ nad tímtéž slovem.
Použijeme vlastnosti z~definice izomorfismu. Nejprve ověříme $s'_0 = f(s_0) = f(q_0) = q'_0$.
Podle definice výpočtu je $s_{i+1} = \delta(s_i, \alpha[i])$, takže
$s'_{i+1} = f(s_{i+1}) = f(\delta(s_i, \alpha[i])) = \delta'(f(s_i), \alpha[i]) = \delta'(s'_i, \alpha[i])$.
Nakonec víme, že $s_n\in F$ právě tehdy, když $s'_n = f(s_n) \in F'$, takže automaty
se shodnou na tom, zda slovo~$\alpha$ přijmou. Jelikož $\alpha$ jsme mohli zvolit libovolně,
znamená to, že automaty přijímají tentýž jazyk.
\qed
\subsection{Redukce automatu}
TODO:
\list{o}
\:Odstranění nedosažitelných stavů (možná později?)
\:Připomenutí ekvivalencí a jejich tříd, zjemnění ekvivalence
\:Ekvivalence stavů
\:Algoritmus na konstrukci ekvivalence (indukce podle délky oddělujícího slova)
\:Cvičení: využití algoritmu pro test, zda dva automaty přijímají tentýž jazyk
\:Faktorizace stavů $\Rightarrow$ redukovaný automat, jeho ekvivalence stavů je triviální
\:Plán: dva redukované automaty pro tentýž jazyk jsou izomorfní
\endlist
\subsection{Kongruence slov a Myhillova-Nerodova věta}
TODO:
\list{o}
\:Co je to kongruence na monoidu
\:Automatová kongruence (potřebujeme všechny stavy dosažitelné)
\:Syntaktická kongruence (asi jen jednostranná)
\:Automatová kongruence je zjemněním syntaktické
\:Myhillova-Nerodova věta: jazyk je regulární $\Leftrightarrow$ levá/pravá syntaktická
kongruence má konečně mnoho tříd.
\:Nějaké příklady jazyků a jejich kongruencí
\:Dva stavy jsou ekvivalentní, pokud jejich kongruenční třídy patří do téže třídy syntaktické kongruence.
\:Pokud dva automaty mají tutéž automatovou kongruenci, jsou izomorfní.
\:Důsledek: Redukované automaty pro tentýž jazyk jsou izomorfní.
\endlist
\exercises
\ex{Charakterizujte všechna řešení rovnice $X=AX\cup B$ v~případě, že $\varepsilon\in A$.
\ex{Homomorfismus se od izomorfismu liší tím, že nevyžadujeme, aby zobrazení bylo bijektivní.
Můžeme si tedy představit, že je to izomorfismus jednoho objektu s~nějakou podmnožinou druhého
objektu. Rozmyslete si, co znamená homomorfismus automatů, a~ukažte, že z~něj také plyne,
že automaty rozpoznávají stejný jazyk.
}
\ex{Formulujte definici izomorfismu pro nedeterministické automaty.}
}
\endexercises
\endchapter