Zkouška

• deterministický konečný automat (DFA) je pětice $A=(Q,\Sigma,\delta,q_0,F)$
• $Q$ … konečná množina stavů
• $\Sigma$ … konečná neprázdná množina vstupních symbolů (abeceda)
• $\delta:Q\times\Sigma\to Q$ … přechodová funkce
• $q_0\in Q$ … počáteční stav
• $F\subseteq Q$ … množina koncových (přijímajících) stavů
• úmluva
  • pokud přechodová funkce není totální, doplníme ji pomocí stavu fail (do něj povedou přechody pro chybějící kombinace stavů a písmen, z něj povedou přechody pouze opět do fail pro každé písmeno)
  • pokud $F=\emptyset$ a je vyžadováno $F\neq\emptyset$, přidáme stav final (je incidentní jen s přechody, které vedou z final do final pro každé písmeno abecedy)

• mějme neprázdnou množinu symbolů $\Sigma$
• slovo je konečná (i prázdná) posloupnost symbolů $s\in\Sigma$
• prázdné slovo se značí $\epsilon$ nebo $\lambda$
• $\Sigma^*$ … množina všech slov v abecedě $\Sigma$
• $\Sigma^+$ … množina všech neprázdných slov v abecedě $\Sigma$
• jazyk $L\subseteq\Sigma^*$ je množina slov v abecedě $\Sigma$

• nad slovy $\Sigma^*$ definujeme tyto operace:
  • zřetězení slov $u{.}v$ nebo $uv$
  • mocnina (počet opakování) $u^n$
  • délka slova $|u|$
  • počet výskytů $s\in\Sigma$ ve slově $u$ značíme $|u|_s$

• mějme přechodovou funkci $\delta:Q\times\Sigma\to Q$
• rozšířenou přechodovou funkci $\delta^*:Q\times\Sigma^*\to Q$ (tranzitivní uzávěr $\delta$) definujeme induktivně:
  • $\delta^*(q,\epsilon)=q$
  • $\delta^*(q,wx)=\delta(\delta^*(q,w),x)$ pro $x\in\Sigma,\,w\in\Sigma^*$
• idea: aplikujeme přechodovou funkci na celé slovo

• jazykem rozpoznávaným (přijímaným) deterministickým konečným automatem $A=(Q,\Sigma,\delta,q_0,F)$ nazveme jazyk $L(A)=\set{w\mid w\in\Sigma^*\land\delta^*(q_0,w)\in F}$
• slovo je přijímáno automatem $A\equiv w\in L(A)$
• jazyk $L$ je rozpoznatelný konečným atuomatem $\equiv$ existuje konečný automat $A$ takový, že $L=L(A)$
• třídu jazyků rozpoznatelných konečnými automaty označíme $\mathcal F$, nazveme regulární jazyky

• věta
  • nechť $L$ je regulární jazyk
  • $(\exists n\in\mathbb N)(\forall w\in L):|w|\geq n\implies w=xyz$
    • $y\neq\epsilon$
    • $|xy|\leq n$
    • $\forall k\geq 0:xy^kz\in L$
  • důkaz
    • mějme regulární jazyk $L$, pak existuje DFA $A$ s $n$ stavy, přičemž $L=L(A)$
    • vezměme libovolné slovo délky aspoň $n$
      • $a_1a_2\dots a_m=w\in L$
      • $m\geq n$
      • $a_i\in\Sigma$
    • definujme $p_i$ jako stav automatu, v němž budeme po $i$ písmenech toho slova
      • $\forall i:p_i=\delta^*(q_0,a_1a_2\dots a_i)$
      • zjevně $p_0=q_0$
    • máme $n+1$ $p_i$ a $n$ různých stavů automatu, takže mezi $p_i$ se nějaký stav opakuje, vezmeme první takový
      • $(\exists i,j)(0\leq i\lt j\leq n\land p_i=p_j)$
    • definujeme
      • $x=a_1\dots a_i$
      • $y=a_{i+1}\dots a_j$
      • $z=a_{j+1}\dots a_m$
    • tj. $w=xyz$, $y\neq\epsilon$, $|xy|\leq n$

• předpokládejme regularitu $L_{01}$
• vezměme $m$ z pumping lemmatu
• zvolme $w=0^m1^m$
• rozdělme $w=xyz$ dle pumping lemmatu
  • $|xy|\leq n$ je na začátku $w$, takže obsahuje jen nuly
  • $y\neq\epsilon$
• z pumping lemmatu $xz\in L_{01}$, což je spor, protože $xz$ obsahuje méně nul než jedniček

• definice: dosažitelný stav
  • mějme DFA $A=(Q,\Sigma,\delta,q_0,F)$
  • stav $q\in Q$ je dosažitelný, existuje-li $w\in\Sigma^*$ takové, že $\delta^*(q_0,w)=q$
• dosažitelné stavy hledáme iterativně
  • začneme s $M_0=\set{q_0}$
  • $M_{i+1}=M_i\cup\set{q\in Q:(\exists p\in M_i)(\exists x\in\Sigma)(\delta(p,x)=q)}$
  • opakujeme dokud $M_{i+1}\neq M_i$
• korektnost
  • každé $M_i$ obsahuje pouze dosažitelné stavy
• úplnost
  • pro dosažitelný stav $q$ mějme nejkratší takové $w$, že $\delta^*(q_0,w)=q$
    • $|w|=n$
    • $w=x_1\dots x_n$
  • zjevně $\delta^*(q_0,x_1\dots x_i)\in M_i$
  • tedy $q=\delta^*(q_0,w)\in M_n$

• mějme konečnou abecedu $\Sigma$ a relaci ekvivalence $\sim$ na $\Sigma^*$
• $\sim$ je pravá kongruence $\equiv(\forall u,v,w\in\Sigma^*):u\sim v\implies uw\sim vw$
• $\sim$ je konečného indexu $\equiv$ rozklad $\Sigma^*/\sim$ má konečný počet tříd
• třídu kongruence $\sim$ obsahující slovo $u$ značíme $[u]_\sim$ nebo $[u]$
• příklady
  • relace „končí stejným písmenem“ je pravá kongruence
  • relace „mají stejný počet znaků“ není konečného indexu

• věta
  • nechť $L$ je jazyk nad konečnou abecedou $\Sigma$
  • potom následující trzení jsou ekvivalentní:
    • $L$ je rozpoznatelný konečným automatem
    • existuje pravá kongruence $\sim$ konečného indexu nad $\Sigma^*$ tak, že $L$ je sjednocením jistých tříd rozkladu $\Sigma^*/\sim$
• důkaz $\implies$
  • definujeme $u\sim v\equiv\delta^*(q_0,u)=\delta^*(q_0,v)$
  • je to ekvivalence, je to pravá kongruence
  • má konečný index (protože automat má konečně mnoho stavů)
  • $L=\set{w\in\Sigma^*:\delta^*(q_0,w)\in F}$
  • $=\bigcup_{q\in F}\set{w\in\Sigma^*:\delta^*(q_0,w)=q}$
  • $=\bigcup_{q\in F}[w\in\Sigma^*:\delta^*(q_0,w)=q]$
  • tedy $L$ je sjednocením tříd, které odpovídají přijímajícím stavům automatu
• důkaz $\impliedby$
  • abeceda automatu bude $\Sigma$
  • za stavy $Q$ položíme třídy rozkladů $\Sigma^*/\sim$
  • počáteční stav $q_0:=[\epsilon]$
  • koncové stavy budou třídy, jejichž sjednocením je $L$
  • přechodová funkce $\delta([u],x):=[ux]$
    • je korektní z definice pravé kongruence
  • zjevně $L(A)=L$
• použití k důkazu neregularity
  • ukážeme pro pumpovatelný jazyk slov ve tvaru $a^+b^ic^i$ nebo $b^ic^j$
  • pro regulární $L$ musí existovat pravá kongruence konečného indexu $m$
  • mějme množinu řetězců $S=\set{ab,abb,abbb,\dots,ab^{m+1}}$
  • $|S|=m+1$, tedy nutně existují dvě slova $i\neq j$, která padnou do stejné třídy
    • $ab^i\sim ab^j$
    • tedy $ab^ic^i\sim ab^jc^i$
    • ale $ab^ic^i\in L$ a $ab^jc^i\notin L$, což je spor, takže jazyk není regulární

• nechť $A_1,A_2$ jsou DFA
• řekneme, že zobrazení $h:Q_1\to Q_2$ je automatovým homomorfismem, jestliže:
  • $h(q_{0_1})=q_{0_2}$
  • $h(\delta_1(q,x))=\delta_2(h(q),x)$
  • $q\in F_1\iff h(q)\in F_2$
• homomorfismus prostý a na (tzn. bijekci) nazýváme isomorfismus

• definice: dva konečné automaty $A,B$ nad stejnou abecedou $\Sigma$ jsou ekvivalentní, jestliže rozpoznávají stejný jazyk, tj. $L(A)=L(B)$
• věta: existuje-li homomorfismus konečných automatů $A_1$ do $A_2$, pak jsou $A_1$ a $A_2$ ekvivalentní
• důkaz
  • zjevně $\forall w\in\Sigma^*:h(\delta^*_1(q,w))=\delta^*_2(h(q),w)$
  • dále projdeme sérií ekvivalentních výroků
    • $w\in L(A_1)$
    • $\delta_1^*(q_{0_1},w)\in F_1$
    • $h(\delta_1^*(q_{0_1},w))\in F_2$
    • $\delta_2^*(h(q_{0_1}),w)\in F_2$
    • $\delta_2^*(q_{0_2},w)\in F_2$
    • $w\in L(A_2)$

• říkáme, že stavy $p,q\in Q$ konečného automatu $A$ jsou ekvivalentní, pokud $\forall w\in\Sigma^*:\delta^*(p,w)\in F\iff\delta^*(q,w)\in F$
• nejsou-li dva stavy ekvivalentní, říkáme, že jsou rozlišitelné

• základ: pokud $p\in F$ a $q\notin F$, pak je dvojice $\set{p,q}$ rozlišitelná
• indukce
  • nechť $p,q\in Q,\, a\in\Sigma$ a o dvojici stavů $\set{\delta(p,a),\delta(q,a)}$ víme, že jsou rozlišitelné, pak i $\set{p,q}$ jsou rozlišitelné
  • opakujeme, dokud existuje nějaká nová trojice $p,q,a$
• korektnost
  • uvažujme špatné páry stavů, které jsou rozlišitelné, ale algoritmus je nerozlišil
  • vezměme z nich pár $\set{p,q}$ rozlišitelný nejkratším slovem $w=a_1\dots a_n$
  • stavy $r=\delta(p,a_1)$ a $s=\delta(q,a_1)$ jsou rozlišitelné kratším slovem $a_2\dots a_n$, takže pár není mezi špatnými
  • tedy v příštím kroku algoritmus rozliší i $p,q$
• složitost
  • čas výpočtu je polynomiální vzhledem k počtu stavů
  • v jednom kole uvažujeme všechny páry, tj. $O(n^2)$
  • kol je maximálně $O(n^2)$, protože v každém rozlišíme aspoň jeden pár
  • dohromady $O(n^4)$, ale lze zrychlit na $O(n^2)$ pamatováním závislostí mezi stavy

• testujeme ekvivalenci regulárních jazyků $L,M$
• najdeme DFA $A_L,A_M$ takové, že
  • $L(A_L)=L$
  • $L(A_M)=M$
  • $Q_L\cap Q_M=\emptyset$
• vytvoříme DFA sjednocením stavů a přechodů $(Q_L\cup Q_M,\Sigma,\delta_L\cup \delta_M,q_{0_L},F_L\cup F_M)$
  • není důležité, zda jako počáteční stav zvolíme $q_{0_L}$ nebo $q_{0_M}$
• použijeme algoritmus hledání rozlišitelných stavů
• jazyky jsou ekvivalentní $\iff$ počáteční stavy $q_{0_L},q_{0_M}$ jsou ekvivalentní

• deterministický konečný automat je redukovaný, pokud
  • nemá nedosažitelné stavy
  • žádné dva stavy nejsou ekvivalentní
  • $\delta$ je totální
• konečný automat $A$ je reduktem automatu $B$, pokud
  • $A$ je redukovaný
  • $A$ a $B$ jsou ekvivalentní
• lemma: každé dva ekvivalentní redukované automaty jsou izomorfní
• lemma: pro každý DFA, který přijímá aspoň jedno slovo, existuje redukovaný DFA, který je s ním ekvivalentní
• důsledek: všechny redukty jednoho DFA jsou izomorfní

• eliminujeme nedosažitelné stavy
• najdeme rozklad zbylých stavů na třídy ekvivalence
• stavy nového automatu budou jednotlivé třídy
• zkonstruujeme přechodovou funkci mezi třídami
• počáteční stav nového automatu bude odpovídat třídě s počátečním stavem původního automatu
• množinou přijímajících stavů budou třídy odpovídající přijímajícím stavům původního automatu
• poznámka: pro nedeterministické konečné automaty tento algoritmus nefunguje

• nedeterministický konečný automat s $\epsilon$ přechody je pětice $A=(Q,\Sigma,\delta,q_0,F)$
• $Q$ … konečná množina stavů
• $\Sigma$ … konečná množina vstupních symbolů (abeceda)
• $\delta:Q\times(\Sigma\cup\set{\epsilon})\to \mathcal P(Q)$ … přechodová funkce vracející podmnožinu $Q$
• $q_0\in Q$ … počáteční stav
  • alternativa: množina počátečních stavů $S_0\subseteq Q$
• $F\subseteq Q$ … množina koncových (přijímajících) stavů

• pro $q\in Q$ definujeme $\epsilon$-uzávěr $\epsilon\text{closure}(q)$ rekurzivně
  • stav $q$ je v $\epsilon\text{closure}(q)$
  • $p\in\epsilon\text{closure}(q)\land r\in\delta(p,\epsilon)\implies r\in \epsilon\text{closure}(q)$
• pro množinu stavů $S\subseteq Q$ definujeme $\epsilon\text{closure}(S)=\bigcup_{q\in S}\epsilon\text{closure}(q)$
• idea: všechny stavy, do nichž se z daného stavu dostaneme prázdným slovem

• mějme $\epsilon$NFA $(Q,\Sigma,\delta,q_0,F)$
• rozšířenou přechodovou funkci $\delta^*$ definujeme takto
  • $\delta^*(q,\epsilon)=\epsilon\text{closure}(q)$
  • $\delta^*(q,wx)=\epsilon\text{closure}\left(\bigcup_{p\in \delta^*(q,w)}\delta(p,x)\right)$
    • pro $x\in\Sigma,\,w\in\Sigma^*$

• mějme NFA $A=(Q,\Sigma,\delta,q_0,F)$
• pak $L(A)=\set{w\in \Sigma^*:\delta^*(q_0,w)\cap F\neq 0}$ je jazyk přijímaným automatem $A$
• tedy $L(A)$ je množina slov $w\in\Sigma^*$ takových, že $\delta^*(q_0,w)$ obsahuje aspoň jeden přijímající stav

• konfigurace DFA/$\epsilon$NFA
  • mějme konečný automat $(Q,\Sigma,\delta,q_0,F)$
  • pak dvojice $(q,v)$ označuje konfiguraci konečného automatu, který se nachází ve stavu $q$ s nepřečteným vstupem $v$
    • přičemž $q\in Q,\,v\in \Sigma^*$
• výpočetní graf (strom) $\epsilon$NFA
  • mějme NFA $A=(Q,\Sigma,\delta,q_0,F)$ a vstupní slovo $w\in\Sigma^*$
  • uzly výpočetního grafu jsou konfigurace $A$ nad slovem $w$
  • orientované hrany značí možný přechod mezi konfiguracemi
  • tedy z $(p,au)$ vede hrana do $(q,u)$, právě když $q\in\delta(p,a)$

• věta: jazyk $L$ je rozpoznatelný $\epsilon$NFA, právě když je $L$ regulární
• pro libovolný $\epsilon$NFA $N$ zkonstruujeme DFA $D$ přijímající stejný jazyk jako $N$
• nové stavy jsou $\epsilon$-uzavřené podmnožiny $Q_N$
  • $Q_D\subseteq\mathcal P(Q_N)$
  • $\forall S\subseteq Q_N:\epsilon\text{closure}(S)\in Q_D$
  • v $Q_D$ může být i $\emptyset$
• počáteční stav je $\epsilon$-uzávěr $q_0$
  • $q_{D_0}=\epsilon\text{closure}(q_{N_0})$
• přijímající stavy jsou všechny množiny obsahující nějaký přijímající stav
  • $F_D=\set{S\in Q_D: S\cap F_N\neq\emptyset}$
• přechodová funkce sjednotí a $\epsilon$-uzavře přechody z jednotlivých stavů
  • pro $S\in Q_D,\,x\in\Sigma$ definujeme $\delta_D(S,x)=\epsilon\text{closure}\left(\bigcup_{p\in S}\delta_N(p,x)\right)$

• věta: pro DFA $D$ vytvoření podmnožinovou konstrukcí z NFA $N$ platí $L(N)=L(D)$
• důkaz: indukcí dokážeme $\delta^*_D(q_{D_0},w)=\delta^*_N(q_{N_0},w)$

• definice: množinové operace nad jazyky (sjednocení, průnik, rozdíl, doplněk) fungují tak, jak bychom čekali
• věta
  • mějme regulární jazyky $L,M$
  • pak jsou následující jazyky také regulární
    • sjednocení $L\cup M$
    • průnik $L\cap M$
    • rozdíl $L-M$
    • doplněk $\overline L=\Sigma^*-L$
• důkaz
  • pokud $\delta$ není totální, přidáme fail
  • uvažujeme DFA přijímající daný jazyk
  • doplněk: obrátíme „koncovost“ stavů
  • průnik, sjednocení, rozdíl
    • zkonstruujeme součinový automat $(Q_1\times Q_2,\Sigma,\delta,(q_{0_1},q_{0_2}),F)$
      • kde $\delta((p,q),x)=(\delta_1(p,x),\delta_2(q,x))$
    • průnik … $F=F_1\times F_2$
    • sjednocení … $F=(F_1\times Q_2)\cup(Q_1\times F_2)$
    • rozdíl … $F=F_1\times (Q_2-F_2)$

• zřetězení jazyků $L{.}M=\set{uv\mid u\in L\land v\in M}$
• mocniny jazyka $L^k=\underbrace{L{.}L\dots L}_{k}$
• pozitivní iterace $L^+$
• obecná iterace $L^*$
• otočení jazyka $L^R=\set{u^R\mid u\in L}$
• levý kvocient $L$ podle $M$
  • $M\setminus L=\set{v\mid uv\in L\land u \in M}$
• levá derivace $L$ podle $w$
  • $\partial_wL=\set{w}\setminus L$
• pravý kvocient $L$ podle $M$
  • $L/M=\set{u\mid uv\in L\land v\in M}$
  • $\partial^R_wL=L/\set{w}$

• věta: jsou-li $L,M$ regulární jazyky, jsou regulární i $L{.}M,L^*,L^+,L^R,M\setminus L,L/M$
• důkaz
  • uvažujeme automaty pro $L,M$
  • vytvoříme NFA
  • jednotlivé části oddělujeme epsilon přechody, aby nemohly interagovat
  • $L^R$ … obrátíme šipky ve stavovém diagramu
  • $M\setminus L$
    • algoritmicky najdeme stavy, kam se dá dostat slovem z $M$
    • do těch stavů dáme epsilon přechody z počátečního stavu
  • $L/M=(M^R\setminus L^R)^R$
  • ostatní jsou intuitivní

• $\text{RegE}(\Sigma)$ … množina všech regulárních výrazů nad konečnou neprázdnou abecedou
• $L(\alpha)$ … hodnota regulárního výrazu $\alpha$
• regulární výraz a jeho hodnota jsou definovány induktivně
  • základ
    • $\epsilon$ … prázdný řetězec, $L(\epsilon)=\set{\epsilon}$
    • $\emptyset$ … prázdný výraz, $L(\emptyset)=\emptyset$
    • $a$ … znak $a\in\Sigma$, $L(a)=\set{a}$
  • indukce
    • $\alpha+\beta$ … jako OR, $L(\alpha+\beta)=L(\alpha)\cup L(\beta)$
    • $\alpha\beta$ … $L(\alpha\beta)=L(\alpha)L(\beta)$
    • $\alpha^*$ … $L(\alpha^*)=L(\alpha)^*$
    • $(\alpha)$ … závorky nemění hodnotu, $L((\alpha))=L(\alpha)$
• nejvyšší prioritu má iterace $^*$, pak zřetězení, pak sjednocení $+$
• třída $\text{RegE}(\Sigma)$ je nejmenší třída uzavřená na uvedené operace

• věta
  • každý jazyk reprezentovaný konečným automatem lze zapsat jako regulární výraz
  • každý jazyk popsaný regulárním výrazem lze zapsat jako $\epsilon$NFA
• důkaz
  • výraz → $\epsilon$NFA
    • indukcí dle struktury výrazu (viz prezentace)
    • jednotlivé stavební bloky musíme dostatečně oddělovat epsilon přechody
  • DFA → výraz
    • střídavě používáme dva kroky
      1. sloučení hran – když mezi dvěma stavy vede více hran stejným směrem, nahradíme je jednou hranou ohodnocenou sjednocením regulárních výrazů z původních hran (sjednocujeme pomocí $+$)
      2. eliminace stavu – libovolný stav, který není počáteční ani přijímající, odstraníme a zařídíme, že všechny trasy výpočtu, které jím původně procházely, zůstanou zachovány (přidáme odpovídající hrany)
         • pokud ve stavu byla smyčka, zohledníme to na hranách, přičemž výraz ze smyčky bude mít iteraci $^*$
    • nakonec sjednotíme výrazy na hranách z počátečního do přijímajících stavů

• mějme konečnou abecedu $\Sigma$
• pro každé $x\in\Sigma$ budiž $\sigma(x)$ jazyk v nějaké abecedě $Y_x$
• položme
  • $\sigma(\epsilon)=\set{\epsilon}$
  • $\sigma(u{.}v)=\sigma(u){.}\sigma(v)$
• zobrazení $\sigma:\Sigma^*\to\mathcal P(Y^*)$, kde $Y=\bigcup_{x\in\Sigma} Y_x$, se nazývá substituce
• pro jazyk $L$ definujeme $\sigma(L)=\bigcup_{w\in L}\sigma(w)$
• nevypouštějící substituce je taková, kde žádné $\sigma(x)$ neobsahuje $\epsilon$
• příklad substituce $\sigma$
  • definice
    • $\Sigma=\set{0,1}$
    • $Y_0=\set{a,b}$
    • $\sigma(0)=\set{a^ib^i\mid i,j\geq 0}$
    • $Y_1=\set{c,d}$
    • $\sigma(1)=\set{cd}$
    • tedy $Y=\set{a,b,c,d}$
    • $\sigma$ zobrazí slovo v abecedě $\Sigma$ na jazyk v abecedě $Y$
  • použití
    • $\sigma(010)=\set{a^ib^jcda^kb^l\mid i,j,k,l\geq 0}$

• homomorfismus $h$ je speciální případ substituce, kde obraz je vždy jen jednoslovný jazyk, tj. $\forall x\in\Sigma:h(x)=w_x$
  • zapisujeme bez množinových závorek, tradičnější by bylo zapsat $\forall x\in\Sigma:\sigma(x)=\set{w_x}$
  • tedy $h:\Sigma^*\to Y^*$
• nevypouštějící homomorfismus je takový, kde $\forall x:w_x\neq\epsilon$
• inverzní homomorfismus
  • nechť $h$ je homomorfismus abecedy $\Sigma$ do slov nad abecedou $Y$
  • $h^{-1}(L)=\set{w\in\Sigma^*:h(w)\in L}$

• věta: je-li jazyk $L$ a je-li pro všechna $x$ z $\Sigma$ jazyk $\sigma(x),h(x)$ regulární, pak je regulární i $\sigma(L),h(L)$
• důkaz
  • strukturální indukcí
  • použijeme definici substituce a uzavřenost regulárních jazyků na sjednocení a zřetězení
  • iteraci rozložíme na nekonečné sjednocení

• věta: je-li $h$ homomorfismus abecedy $\Sigma$ do abecedy $Y$ a $L$ je regulární jazyk abecedy $Y$, pak $h^{-1}(L)$ je také regulární jazyk
• důkaz
  • pro $L$ máme DFA $A=(Q,Y,\delta,q_0,F)$
  • $h:\Sigma\to Y^*$
  • definujeme $\epsilon$NFA $B=(Q',\Sigma,\delta',[q_0,\epsilon],F\times\set{\epsilon})$
    • $Q'=\set{[q,u]\mid q\in Q,\,u\in Y^*,\,(\exists a\in \Sigma)(\exists v\in Y^*):h(a)=vu}$
      • $u$ je buffer
    • $\delta'([q,\epsilon],a)=[q,h(a)]$ … naplňuje buffer
    • $\delta'([q,bv],\epsilon)=[p,v]$, kde $\delta(q,b)=p$ … čte buffer
  • tak jsme získali konečný automat přijímající $h^{-1}(L)$
  • proč buffer?
    • základní myšlenka
      • máme automat $A$ přijímající jazyk dlouhých slov (to není termín, pouze zjednodušení)
      • chceme automat $B$ přijímající jazyk krátkých slov
      • automat $B$ načte jedno písmeno krátkého slova, tomu v jazyce dlouhých slov odpovídá posloupnost písmen, kterou umíme zpracovat naším automatem
      • takže přečteme písmeno, vygenerujeme posloupnost písmen $h(x)$, uložíme ji do bufferu a automatu $A$ postupně předhazujeme písmena po jednom
    • techničtěji
      • $h$ ze znaku ($\in\Sigma$) vytvoří slovo ($\in Y^*$)
      • přechodová funkce $\delta:Q\times Y\to Q$ ale písmenka přijímá po jednom
      • takže ze znaku $x\in\Sigma$ vytvoříme slovo $h(x)\in Y^*$ a pak ho po písmenkách zpracováváme funkcí $\delta$, dokud buffer nevyprázdníme, pak přejdeme k dalšímu znaku

• lemma: lze algoritmicky rozhodnout, zda jazyk přijímaný DFA, NFA, $\epsilon$NFA je prázdný
  • jazyk je prázdný $\iff$ žádný z koncových stavů není dosažitelný
  • dosažitelnost lze testovat $O(|Q|^2)$
• lemma: pro daný řetězec $w$ (délky $n$) a regulární jazyk $L$ lze algoritmicky rozhodnout, zda $w\in L$
  • DFA: $O(n)$
  • NFA o $s$ stavech: $O(ns^2)$, každý vstupní symbol aplikujeme na všechny stavy předchozího kroku, těch je nejvýš $s$
  • $\epsilon$NFA: v průběhu aplikujeme $\epsilon$-uzávěr

• formální (generativní) gramatika je čtveřice $G=(V,T,P,S)$
• $V$ … konečná množina neterminálů (variables)
• $T$ … neprázdná konečná množina terminálních symbolů (terminálů)
• $S\in V$ … počáteční symbol
• $P$ … konečná množina pravidel (produkcí) reprezentující rekurzivní definici jazyka
  • každé pravidlo má tvar $\beta A\gamma\to\omega$
    • $A\in V$
    • $\beta,\gamma,\omega\in (V\cup T)^*$
  • tj. levá strana obsahuje aspoň jeden neterminální symbol

• gramatiky typu 0 (rekurzivně spočetné jazyky $\mathcal L_0$)
  • pravidla v obecné formě $\alpha\to\omega$
  • $\alpha,\omega\in(V\cup T)^*$
  • $\alpha$ obsahuje neterminál
• gramatiky typu 1 (kontextové gramatiky, jazyky $\mathcal L_1$)
  • pouze pravidla ve tvaru $\gamma A\beta\to\gamma\omega\beta$
  • $A\in V$
  • $\gamma,\beta\in(V\cup T)^*$
  • $\omega\in (V\cup T)^+$
  • jedinou výjimkou je pravidlo $S\to\epsilon$, pak se ale $S$ nevyskytuje na pravé straně žádného pravidla
• gramatiky typu 2 (bezkontextové gramatiky, jazyky $\mathcal L_2$)
  • pouze pravidla ve tvaru $A\to\omega$
  • $A\in V$
  • $\omega\in(V\cup T)^*$
• gramatiky typu 3 (regulární gramatiky / pravé lineární gramatiky, regulární jazyky $\mathcal L_3$)
  • pouze pravidla ve tvaru $A\to\omega B$ nebo $A\to\omega$
  • $A,B\in V$
  • $\omega\in T^*$
  • idea
    • každý neterminál odpovídá stavu konečného automatu
    • pravidla odpovídají přechodové funkci

• mějme gramatiku $G=(V,T,P,S)$
• říkáme, že $\alpha$ se přímo přepíše na $\omega$ (píšeme $\alpha\Rightarrow_G\omega$ nebo $\alpha\Rightarrow\omega$), jestliže $\exists \beta,\gamma,\eta,\nu\in(V\cup T)^*:\alpha=\eta\beta\nu\land\omega=\eta\gamma\nu\land(\beta\to\gamma)\in P$
• říkáme, že $\alpha$ se přepíše na $\omega$ (píšeme $\alpha\Rightarrow^*\omega$), jestliže $\exists\beta_1,\dots,\beta_n\in(V\cup T)^*:\alpha=\beta_1\Rightarrow\beta_2\Rightarrow\dots\Rightarrow\beta_n=\omega$
  • tj. také $\alpha\Rightarrow^*\alpha$
• posloupnost $\beta_1,\dots,\beta_n$ nazýváme derivací (odvozením)
• pokud $\forall i\neq j:\beta_i\neq\beta_j$, hovoříme o minimálním odvození
• libovolný řetězec $\omega\in (V\cup T)^*$ odvoditelný z počátečního symbolu $S$ nazýváme sentenciální forma

• jazyk $L(G)$ generovaný gramatikou $G=(V,T,P,S)$ je množina terminálních řetězců, pro které existuje derivace ze startovního symbolu $L(G)=\set{w\in T^*: S\Rightarrow_G^* w}$
• jazyk neterminálu $A\in V$ definujeme $L(A)=\set{w\in T^*: A\Rightarrow_G^* w}$

• věta: pro každý jazyk rozpoznávaný konečným automatem existuje gramatika typu 3, která ho generuje
• důkaz
  • $L=L(A)$ pro deterministický konečný automat $A=(Q,\Sigma,\delta,q_0,F)$
  • definujme gramatiku $G=(Q,\Sigma,P,q_0)$, kde pravidla $P$ mají tvar
    • $p\to aq$, když $\delta(p,a)=q$
    • $p\to\epsilon$, když $p\in F$
  • platí $L(A)=L(G)$?
    • otestujeme pro prázdné a neprázdné slovo

• lemma: ke každé gramatice typu 3 existuje gramatika typu 3, která generuje stejný jazyk a obsahuje pouze pravidla ve tvaru $A\to aB,\,A\to\epsilon$, kde $A,B\in V,\,a\in T$
  • zavedeme nové neterminály
  • odstraníme pravidla $A\to B$
  • místo pravidel tvaru $A\to a_1\dots a_n B$ nebo $A\to a_1\dots a_n$ přidáme řetězce pravidel v povoleném tvaru
• věta: pro každý jazyk $L$ generovaný gramatikou typu 3 existuje $\epsilon$NFA rozpoznávající $L$
  • vezmeme $G=(V,T,P,S)$ obsahující jen pravidla tvaru $A\to aB$, respektive $A\to\epsilon$
  • z té snadno vyrobíme automat

• gramatiky typu 3 nazýváme také pravé lineární (neterminál je vždy vpravo)
• gramatika je levá lineární, jestliže má pouze pravidla tvaru $A\to Bw$ nebo $A\to w$, přičemž $A,B\in V,\,w\in T^*$
• lemma: jazyky generované levou lineární gramatikou jsou právě regulární jazyky
  • lze dokázat pomocí reverze

• gramatika je lineární, jestliže má pouze pravidla tvaru $A\to uBw$ nebo $A\to w$, kde $A,B\in V,\,u,w\in T^*$ (na pravé straně vždy maximálně jeden neterminál)
• lineární jazyky jsou právě jazyky generované lineárními gramatikami
• příklad: jazyk $L=\set{0^i1^i\mid i\geq 1}$
• pozorování: lineární pravidla lze rozložit na levě a pravě lineární pravidla

• mějme gramatiku $G=(V,T,P,S)$
• derivační strom pro $G$ je strom, kde
  • kořen je označen startovním symbolem $S$
  • každý vnitřní uzel je ohodnocen neterminálem $V$
  • každý uzel je ohodnocen prvkem ze sjednocení $V\cup T\cup\set{\epsilon}$
  • je-li uzel ohodnocen $\epsilon$, je jediným dítětem svého rodiče
  • je-li $A$ ohodnocení vrcholu a jeho děti jsou zleva po řadě ohodnoceny $X_1,\dots,X_k$, pak $(A\to X_1\dots X_k)\in P$ je pravidlo gramatiky
• říkáme, že derivační strom dává (yields) sentenciální formu $\alpha$ (slovo $w$), jestliže $\alpha$ (respektive $w$) vznikne zřetězením listů ve směru zleva doprava

• levá (leftmost) derivace $\Rightarrow_{lm},\,\Rightarrow_{lm}^*$ v každém kroku přepisuje nejlevější neterminál
• pravá (rightmost) derivace $\Rightarrow_{rm},\,\Rightarrow_{rm}^*$ v každém kroku přepisuje nejpravější neterminál

• věta: pro danou gramatiku a  jsou následující tvrzení ekvivalentní
  1. $A\Rightarrow_{lm}^* w$
  2. $A\Rightarrow^* w$
  3. existuje derivační strom s kořenem $A$ dávající slovo $w$
• důkaz
  • $(1)\implies(2)$ … triviálně
  • $(2)\implies(3)$ … z derivace vytvoříme strom
  • $(3)\implies(1)$ … pro libovolný derivační strom najdeme levou derivaci průchodem stromu

gramatiky $G_1,G_2$ jsou ekvivalentní, jestliže $L(G_1)=L(G_2)$, tj. generují stejný jazyk

• symbol $X$ je užitečný v gramatice $G=(V,T,P,S)$, pokud existuje derivace tvaru $S\Rightarrow^*\alpha X\beta\Rightarrow^* w$, kde $w\in T^*,\, X\in (V\cup T),\,\alpha,\beta\in(V\cup T)^*$
• pokud $X$ není užitečný, říkáme, že je zbytečný
• $X$ je generující, pokud $X\Rightarrow^* w$ pro nějaké slovo $w\in T^*$
• $X$ je dosažitelný, pokud $S\Rightarrow^*\alpha X\beta$ pro nějaká $\alpha,\beta\in (V\cup T)^*$

• neterminál $A$ je nulovatelný, pokud $A\Rightarrow^*\epsilon$
• jednotkové pravidlo je $(A\to B)\in P$, kde $A,B$ jsou oba neterminály
• dvojici $A,B\in V$ takovou, že $A\Rightarrow^*B$ pouze jednotkovými pravidly, nazýváme jednotkový pár (jednotková dvojice)

• lemma
  • mějme bezkontextovou gramatiku $G$ takovou, že $L(G)-\set{\epsilon}\neq\emptyset$
  • pak existuje CFG $G_1$ taková, že $L(G_1)=L(G)-\set{\epsilon}$, a $G_1$ neobsahuje $\epsilon$-pravidla, jednotková pravidla ani zbytečné symboly
  • gramatika $G_1$ se nazývá redukovaná
• idea důkazu (podrobněji viz převod do Chomského normálního tvaru, který je silnější)
  • eliminujeme $\epsilon$-pravidla
  • eliminujeme jednotková pravidla (tím nepřidáme $\epsilon$-pravidla)
  • eliminujeme zbytečné symboly (tím nepřidáme žádná pravidla)
    • nejdříve eliminujeme negenerující, pak nedosažitelné

o bezkontextové gramatice $G=(V,T,P,S)$ bez zbytečných symbolů, kde jsou všechna pravidla ve tvaru $A\to BC$ nebo $A\to a$, kde $A,B,C\in V,\, a\in T$, říkáme, že je v Chomského normálním tvaru (ChNF)

• věta: mějme bezkontextovou gramatiku $G$ takovou, že $L(G)-\set{\epsilon}\neq\emptyset$, pak existuje CFG $G_1$ v Chomského normálním tvaru taková, že $L(G_1)=L(G)-\set{\epsilon}$
• algoritmus
  • eliminujeme $\epsilon$-pravidla
    • označíme nulovatelné symboly
    • přidáme verzi pravidel bez nulovatelných symbolů
    • odstraníme $\epsilon$-pravidla
  • eliminujeme jednotková pravidla (tím nepřidáme $\epsilon$-pravidla)
    • najdeme jednotkové páry
    • přidáme odpovídající pravidla
    • odstraníme jednotková pravidla
  • eliminujeme zbytečné symboly (tím nepřidáme žádná pravidla)
    • nejdříve eliminujeme negenerující, pak nedosažitelné
  • pravé strany délky aspoň 2 předěláme na samé neterminály
  • pravé strany s aspoň třemi neterminály rozdělíme na více pravidel

• věta
  • nechť $L$ je bezkontextový jazyk
  • $(\exists n)(\forall w\in L):|w|\geq n\implies w=u_1u_2u_3u_4u_5$
    • $u_2u_4\neq\epsilon$
    • $|u_2u_3u_4|\leq n$
    • $\forall k\geq 0:u_1u_2^ku_3u_4^ku_5\in L$
  • poznámka: v prezentaci je ostrá nerovnost $|w|\gt n$, v jiných zdrojích neostrá
• idea důkazu
  • vezmeme derivační strom pro $w$
  • nejdeme nejdelší cestu, na ní dva stejné neterminály
  • tyto neterminály určí dva postromy, které definují rozklad slova
  • větší podstrom můžeme posunout ($k\gt 1$) nebo nahradit menším podstromem ($k=0$)
• důkaz
  • vezmeme gramatiku v Chomského normální formě (pro $L=\set{\epsilon}$ a $\emptyset$ zvol $n=1$)
  • nechť $|V|=v$
  • položíme $n=2^v$
  • pro $w\in L$ takové, že $|w|\geq n$, má v derivačním stromu $w$ cestu délky $\gt v$
    • pro slovo délky rovné $2^v$ bude mít nejmělčí možný strom $v+2$ úrovní (většina vnitřních vrcholů se binárně větví, poslední úroveň slouží pro přechod k terminálům), tedy nejdelší cesty budou obsahovat $v+2$ vrcholů (z toho $v+1$ neterminálů)
  • vezmeme cestu maximální délky, terminál, kam vede, označíme $t$
  • aspoň dva z posledních $v+1$ neterminálů na cestě do $t$ jsou stejné
  • vezmeme dvojici $A_1,A_2$ nejblíže k $t$ (určují podstromy $T_1,T_2$)
  • cesta z $A_1$ do $t$ je nejdelší v podstromu $T_1$ a má délku maximálně $v+1$
    • z toho plyne $|u_2u_3u_4|\leq n$, jelikož slovo $u_2u_3u_4$ je dané podstromem $T_1$
  • z $A_1$ vedou dvě cesty, jedna do $T_2$, druhá do zbytku $u_2u_4$
    • Chomského normální tvar je nevypouštějící, tedy $u_2u_4\neq\epsilon$
  • zjevně $S\Rightarrow^* u_1A_1u_5\Rightarrow^*u_1u_2A_2u_4u_5\Rightarrow^*u_1u_2u_3u_4u_5$
  • posuneme-li $A_2$ do $A_1$ ($i=0$), dostaneme $u_1u_3u_5$
  • posuneme-li $A_1$ do $A_2$ ($i=2$), dostaneme $u_1u_2u_2u_3u_4u_4u_5$
    • tohle můžeme opakovat několikrát → $i=2,3,4,\dots$
• lze použít např. k důkazu nebezkontextovosti $\set{0^i1^i2^i\mid i\geq 1}$