Select Git revision
Forked from
Martin Mareš / Úvod do kryptografie
Source project has a limited visibility.
-
Tonda Maloň authoredTonda Maloň authored
regular.tex 43.95 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{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{Algebraické souvislosti}
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 okruhy}
\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$).\foot{Je to tedy něco jako grupa,
ale k~$+$ nemusí existovat inverze.}
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{Okruh} 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 navíc jsou $+$ a~$\cdot$ 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 okruhu.\foot{Okruh je tedy něco
jako těleso, jen v~něm nemusí jít dělit.}
}
\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$ komutuje.
\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 okruh. Říkáme mu \df{okruh 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ů.
}
\exercises
\ex{Charakterizujte všechna řešení rovnice $X=AX\cup B$ v~případě, že $\varepsilon\in A$.
}
\endexercises
\endchapter