Skip to content
Snippets Groups Projects
Select Git revision
  • d95ba5957064ea7a2e1b678a3f1b1ae641e7d423
  • master default
2 results

regular.tex

Blame
  • 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