zkouska.md

Zkouška

Úvod

• Definice: Deterministický konečný automat
  • 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)
• Definice: Slovo, $\epsilon$, $\lambda$, $\Sigma^*$, $\Sigma^+$, jazyk
  • 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$
• Definice: Operace zřetězení, mocnina, délka slova
  • 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$
• Definice: Rozšířená přechodová funkce
  • 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
• Definice: Jazyky rozpoznatelné konečnými automaty, regulární jazyky
  • 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: Iterační (pumping) lemma pro 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$
• Věta: Neregularita $L_{01}=\set{0^n1^n\mid n\geq 0}$
  • 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
• Algoritmus: Hledání dosažitelných stavů
  • 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$

Redukovaný DFA

• Definice: Kongruence
  • 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: Myhill-Nerodova věta
  • 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í
• Definice: Automatový homomorfismus
  • 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
• Věta: Ekvivalence automatů
  • 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)$
• Definice: Ekvivalence stavů
  • ří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é
• Algoritmus: Hledání rozlišitelných stavů v DFA
  • 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
• Algoritmus: Testování ekvivalence regulárních jazyků
  • 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í
• Definice: Redukovaný DFA, redukt
  • 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í
• Algoritmus: Nalezení reduktu DFA
  • 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é ϵNFA

• Definice: Nedeterministický konečný automat s $\epsilon$ přechody ($\epsilon$NFA)
  • 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ů
• Definice: $\epsilon$-uzávěr
  • 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
• Definice: $\delta^*$ pro $\epsilon$NFA
  • 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^*$
• Definice: Jazyk přijímaný $\epsilon$NFA
  • 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
• Definice: Konfigurace končného automatu, výpočetní graf $\epsilon$NFA
  • 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)$
• Algoritmus: Podmnožinová konstrukce (s $\epsilon$-přechody)
  • 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: Převod NFA na DFA
  • 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)$
• Věta: Uzavřenost na množinové operace
  • 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)$
• Definice: Řetězcové operace nad jazyky
  • 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: Uzavřenost regulárních jazyků na řetězcové operace
  • 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í

Regulární výrazy

• Definice: Regulární výrazy, hodnota regulárního výrazu
  • $\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: Varianta Kleeneho věty
  • 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ů
• Definice: Substituce jazyků
  • 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}$
• Definice: Homomorfismus jazyků, inverzní homomorfismus
  • 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: Uzavřenost na homomorfismus
  • 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: Uzavřenost na inverzní homomorfismus
  • 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
• Věta: Rozhodovací problémy pro regulární jazyky
  • 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

Gramatiky

• Definice: Formální (generativní) gramatika
  • 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
• Definice: Klasifikace gramatik podle tvaru přepisovacích pravidel
  • 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
• Definice: Derivace $\Rightarrow^*$
  • 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
• Definice: Jazyk generovaný gramatikou $G$
  • 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: $L\in RE\implies L\in\mathcal L_3$
  • 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
• Věta: $\epsilon$-NFA pro gramatiku typu 3 rozpoznávající stejný jazyk
  • 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
• Definice: Levé (a pravé) lineární gramatiky
  • 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
• Definice: Lineární gramatika, jazyk
  • 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
• Definice: Derivační strom
  • 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
• Definice: Levá a pravá derivace
  • 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: Ekvivalence tvrzení o derivacích
  • 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
• Definice: Ekvivalence gramatik
  • gramatiky $G_1,G_2$ jsou ekvivalentní, jestliže $L(G_1)=L(G_2)$, tj. generují stejný jazyk

Chomského normální forma, CFG

• Definice: Zbytečný, užitečný, generující, dosažitelný symbol
  • 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)^$
• Definice: Nulovatelný neterminál; jednotkové pravidlo, jednotkový pár
  • 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)
• Věta: Gramatika v normálním tvaru, redukovaná
  • 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é
• Definice: Chomského normální tvar
  • 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: Chomského normální tvar bezkontextové gramatiky
• Algoritmus: Převod CFG do Chomského normálního tvaru
  • 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: Lemma o vkládání (pumping) pro bezkontextové jazyky
  • 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}$
• Algoritmus: CYK algoritmus, v čase $O(n^3)$
  • věta: slovo $w$ patří do jazyka gramatiky $G$, právě když je v CYK algoritmu $S\in X_{1,n}$ (přičemž $|w|=n$)
  • algoritmus
    • mějme gramatiku v Chomského normálním tvaru $G=(V,T,P,S)$ pro jazyk $L$ a slovo $w=a_1a_2\dots a_n\in T^*$
    • vytvořme trojúhelníkovou tabulku
      • horizontální osa je $w$
      • $X_{ij}$ jsou množiny neterminálů $A$ takových, že $A\Rightarrow^* a_ia_{i+1}\dots a_j$
      • základ: $X_{ii}=\set{A\in V:(A\to a_i)\in P}$
      • indukce: $X_{ij}=\bigcup_{i\leq k\lt j}\set{A\in V:(\exists B\in X_{ik})(\exists C\in X_{k+1,j})((A\to BC)\in P)}$
• Definice: Jednoznačnost a víceznačnost CFG
  • bezkontextová gramatika $G=(V,T,P,S)$ je víceznačná, pokud existuje aspoň jeden řetězec $w\in T^*$, pro který můžeme najít dva různé derivační stromy, oba s kořenem $S$, dávající slovo $w$
  • v opačném případě nazýváme gramatiku jednoznačnou
  • bezkontextový jazyk $L$ je jednoznačný, jestliže existuje jednoznačná CFG $G$ tak, že $L=L(G)$
  • bezkontextový jazyk $L$ je (podstatně) nejednoznačný, jestliže každá CFG $G$ taková, že $L=L(G)$, je nejednoznačná, takovému jazyku říkáme i víceznačný
  • poznámky
    • neexistuje algoritmus, který nám řekne, zda je gramatika víceznačná
    • typické příčiny víceznačnosti
      • není respektovaná priorita operátorů
      • posloupnost identických operátorů lze shlukovat zleva i zprava
    • odstranění víceznačnosti vynucením priority
      • zavedeme více různých proměnných, každou pro jednu úroveň „priority“
      • faktor – nelze rozdělit žádným operátorem
      • term – nelze rozdělit operátorem $+$, lze rozdělit $\cdot$
      • výraz – lze rozdělit $+$ i $\cdot$

Zásobníkové automaty

• Definice: Zásobníkový automat (PDA)
  • zásobníkový automat (PDA) je sedmice $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$
  • $Q$ … konečná množina stavů
  • $\Sigma$ … neprázdná konečná množina vstupních symbolů
  • $\Gamma$ … neprázdná konečná zásobníková abeceda
  • $\delta$ … přechodová funkce
    • $\delta:Q\times(\Sigma\cup\set{\epsilon})\times\Gamma\to \mathcal P_{FIN}(Q\times\Gamma^*)$
      • kde $\mathcal P_{FIN}(A)$ je množina všech konečných podmnožin množiny $A$
    • tedy $\delta(p,a,X)\ni(q,\gamma)$
      • $q$ je nový stav
      • $\gamma$ je řetězec zásobníkových symbolů, který nahradí $X$ na vrcholu zásobníku
  • $q_0\in Q$ … počáteční stav
  • $Z_0\in\Gamma$ … počáteční zásobníkový symbol
  • $F$ … množina přijímajících (koncových) stavů (může být nedefinovaná)
  • jak PDA funguje
    • je nedeterministický
    • v jednom časovém kroku
      • na vstupu přečte žádný nebo jeden symbol
      • přejde do nového stavu
      • nahradí symbol na vrchu zásobníku libovolným řetězcem (nejlevější znak bude na vrchu)
  • přechodový diagram
    • jako pro konečný automat
    • hrany popisujeme ve tvaru: vstupní znak, zásobníkový znak → push řetězec
• Definice: Konfigurace zásobníkového automatu
  • konfiguraci zásobníkového automatu reprezentujeme trojicí $(q,w,\gamma)$
  • $q$ … stav
  • $w$ … zbývající vstup
  • $\gamma$ … obsah zásobníku (vrch zásobníku je vlevo)
  • konfiguraci značíme zkratkou ID (instantaneous description)
• Definice: $\vdash$, $\vdash^*$ posloupnosti konfigurací
  • mějme
    • PDA $(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$
    • $p,q\in Q$
    • $a\in (\Sigma\cup\set{\epsilon})$
    • $X\in\Gamma$
    • $\alpha\in\gamma^*$
    • $\delta(p,a,X)\ni (q,\alpha)$
  • pak říkáme, že konfigurace $(p,aw,X\beta)$ bezprostředně vede na konfiguraci $(q,w,\alpha\beta)$
    • značíme $(p,aw,X\beta)\vdash(q,w,\alpha\beta)$
  • podobně „konfigurace $I$ vede na konfiguraci $J$“ (pokud existuje posloupnost konfigurací mezi nimi, které na sebe bezprostředně vedou), značíme pomocí $\vdash^*$
    • definuje se rekurzivně
      • základ: $I\vdash^*I$
      • rekurze: $I\vdash J\land J\vdash^*K\implies I\vdash^*K$
• Definice: Jazyk přijímaný koncovým stavem, prázdným zásobníkem
  • mějme zásobníkový automat $P_{da}=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$
  • jazyk přijímaný koncovým stavem je $L(P_{da})=\set{w\in\Sigma^:(\exists q\in F)(\exists\alpha\in\Gamma^)((q_0,w,Z_0)\vdash^*{P{da}}(q,\epsilon,\alpha))}$
  • jazyk přijímaný prázdným zásobníkem je $N(P_{da})=\set{w\in\Sigma^:(\exists q\in Q)((q_0,w,Z_0)\vdash^{P{da}}(q,\epsilon,\epsilon))}$
    • množina $F$ je nerelevantní, takže ji lze vynechat – pak je PDA šestice
• Věta: L(CFG), L(PDA), N(PDA)
  • lemma: vstup, který není čtený, a dno zásobníku neovlivní výpočet
  • lemma: od přijímajícího stavu k prázdnému zásobníku
    • na dno zásobníku přidáme špunt
    • z přijímajících stavů vedeme hranu do vypouštěcího stavu, kde zásobník vyprázdníme
  • lemma: od prázdného zásobníku ke koncovému stavu
    • na dno zásobníku přidáme špunt
    • z každého stavu uděláme přechod takový, že pokud je vidět špunt, přemístíme se do koncového stavu
  • věta: následující tvrzení jsou ekvivalentní
    • jazyk $L$ je bezkontextový, tj. generovaný bezkontextovou gramatikou
    • jazyk $L$ je přijímaný nějakým zásobníkovým automatem koncovým stavem
    • jazyk $L$ je přijímaný nějakým zásobníkovým automatem prázdným zásobníkem
  • důkaz: ekvivalenci N(PDA) a L(PDA) už máme, ještě ukážeme ekvivalenci L(CFG) a N(PDA)
  • lemma: N(PDA) z L(CFG) – viz algoritmus „konstrukce PDA z CFG“
  • lemma: pro PDA existuje CFG
    • máme PDA $(Q,\Sigma,\Gamma,\delta,q_0,Z_0)$
    • neterminály gramatiky budou složené symboly $[qXp]$ … PDA vyšel z $q$, vzal $X$ a (nakonec) přešel do $p$
    • zavedeme nový počáteční symbol $S$
    • definujeme pravidla
      • $\forall p\in Q: S\to [q_0Z_0p]$
        • „začneme v $q_0$, (hned) odebereme $Z_0$ (ale možná tam zase něco vrátíme) a nakonec se dostaneme do (koncového) stavu $p$“ (tedy přijmeme prázdným zásobníkem)
      • uvažujeme všechny dvojice $(p,Y_1Y_2\dots Y_k)\in \delta (q,s,X)$
        • kde $s\in\Sigma\cup\set{\epsilon}$
        • $\forall p_1,\dots,p_{k}\in Q$ vytvoříme pravidlo $[qXp_k]\to s[pY_1p_1][p_1Y_2p_2]\dots[p_{k-1}Y_kp_k]$
        • levá strana – jsme ve stavu $q$, z vrchu zásobníku vezmeme $X$, pak se (možná) něco stane, nakonec budeme v nějakém stavu $p_k$
        • pravá strana – přešli jsme ze stavu $q$ do konkrétního stavu $p$, přitom jsme přečetli písmeno $s$ ze vstupu a na zásobníku přibyly symobly $Y_1\dots Y_k$, které je potřeba zpracovat (při zpracování prvního symbolu budeme vycházet z konkrétního stavu $p$, po zpracování posledního symbolu se dostaneme do nějakého stavu $p_k$)
        • takže vlastně začátek každé strany pravidla vždycky vychází z přechodu, konec je „náhodný“
      • speciálně pro $(p,\epsilon)\in\delta(q,a,A)$ vytvoříme pravidlo $[qAp]\to a$
• Algoritmus: Konstrukce PDA z CFG
  • mějme gramatiku $G=(V,T,P,S)$
  • konstruujeme PDA $P=(\set{q},T,V\cup T,\delta,q,S)$
    • $\forall A\in V:\delta(q,\epsilon,A)=\set{(q,\beta)\mid (A\to \beta)\in P}$
    • $\forall a\in T:\delta(q,a,a)=\set{(q,\epsilon)}$
    • $P$ přijímá prázdným zásobníkem
  • idea
    • stavy nás nezajímají – stačí nám jeden
    • na zásobníku nedeterministicky generujeme všechny možné posloupnosti terminálů
• Definice: Deterministický zásobníkový automat (DPDA)
  • zásobníkový automat $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ je deterministický PDA, právě když platí zároveň
    • $\delta(q,a,X)$ je nejvýše jednoprvková pro libovolnou trojici $q,a,X$
    • je-li $\delta(q,a,X)$ neprázdná pro nějaké $a\in\Sigma$, pak $\delta(q,\epsilon,X)$ musí být prázdná
• Věta: Zařazení $L_{DPDA}$ mezi $L_{PDA}$ a regulární jazyky
  • věta: nechť je $L$ regulární jazyk, pak $L=L(P)$ pro nějaký DPDA $P$
    • DPDA může simulovat deterministický konečný automat a ignorovat zásobník
  • lemma: jazyk $L_{wcwr}$ je přijímaný DPDA, ale není regulární
    • $L_{wcwr}$ … jazyk palindromů se středovou značkou $c$
    • důkaz neregularity plyne z pumping lemmatu na slovo $0^nc0^n$
  • lemma: jazyk $L_{abb}$ je bezkontextový, ale není přijímaný žádným DPDA
    • $L_{abb}=\set{a^ib^i\mid i\in\mathbb N}\cup \set{a^ib^{2i}\mid i\in\mathbb N}$
    • dokážeme sporem, uvažujme DPDA $M$ přijímající $L_{abb}$
    • vytvořme dvě kopie, $M_1$ a $M_2$
    • v $M_2$ místo $b$ budeme mít písmenko $c$
    • zkonstruujeme nový automat, počátečním stavem bude počáteční stav $M_1$, koncovými stavy budou koncové stavy $M_2$
    • z koncových stavů $M_1$ uděláme přechody do odpovídajících stavů v $M_2$
    • takový automat bude nutně přijímat $\set{a^ib^ic^i\mid i\in\mathbb N}$, což je spor, protože ten jazyk není bezkontextový, takže deterministický $M$ nemůže existovat
• Věta: $L\in N(P_{DPDA})$, právě když $L$ bezprefixový a $L\in L(P'_{DPDA})$
  • definice: jazyk $L\subset\Sigma^*$ je bezprefixový, pokud neexistují slova $u,v\in L$ a $z\in\Sigma^+$ taková, že $u=vz$
    • tj. pro žádná dvě slova $u,v$ není $v$ vlastním prefixem $u$
  • věta: jazyk $L$ je $N(P)$ pro nějaký DPDA $P$, právě když $L$ je bezprefixový a $L$ je $L(P')$ pro nějaký DPDA $P'$
  • důkaz$\implies$
    • prefix přijmeme prázdným zásobníkem
    • pro prázdný zásobník neexistuje instrukce, tj. žádné prodloužení není v $N(P)$
  • důkaz $\impliedby$
    • převod $P'$ na $P$ nepřidá nedeterminismus

Uzávěrové vlastnosti

• Věta: CFL uzavřené na sjednocení, konkatenaci, iteraci, reverzi, naopak neuzavřené na průnik
  • důkazy
    • sjednocení
      • pokud $V_1\cap V_2\neq\emptyset$, musíme přejmenovat neterminály
      • přidáme nový symbol $S_{new}$ a pravidlo $S_{new}\to S_1|S_2$
    • zřetězení
      • pokud $V_1\cap V_2\neq\emptyset$, musíme přejmenovat neterminály
      • $S_{new}\to S_1S_2$
    • iterace
      • $S_{new}\to SS_{new}|\epsilon$
    • pozitivní iterace
      • $S_{new}\to SS_{new}|S$
    • zrcadlový obraz (reverze)
      • obrátíme pravou stranu pravidel
  • protipříklad uzavřenosti na průnik
    • jazyk $L=\set{0^n1^n2^n\mid n\geq 1}=\set{0^n1^n2^i\mid n,i\geq 1}\cap \set{0^i1^n2^n\mid n,i\geq 1}$ není bezkontextový, přestože oba členy průniku jsou bezkontextové
• Věta: CFL i DCFL jsou uzavřené na průnik s regulárním jazykem
  • zásobníkový a konečný automat můžeme spojit
  • uvažujeme PDA přijímající koncovým stavem
  • sestrojíme vlastně něco jako součinový automat
  • pokud se v daném přechodu nečte vstup, tak konečný automat stojí
• Věta: CFL jsou uzavřené na substituci a homomorfismus
  • idea: listy v derivačním stromě generují další stromy
  • přejmenujeme neterminály na jednoznačné ve všech gramatikách
  • máme $G=(V,\Sigma,P,S)$ a $\forall a\in\Sigma: G_a=(V_a,T_a,P_a,S_a)$
  • vytvoříme novou gramatiku $G'=(V',T',P',S')$
    • $V'=V\cup\bigcup_{a\in\Sigma} V_a$
    • $T'=\bigcup_{a\in\Sigma}T_a$
    • $P'=\bigcup_{a\in\Sigma}P_a$ sjednoceno s pravidly z $P$, ve kterých všechna $a\in\Sigma$ nahradíme $S_a$
  • $G'$ generuje jazyk $\sigma(L)$
  • idea pro homomorfismus: terminál $a$ v derivačním stromě nahradím slovem $h(a)$
• Věta: CFL jsou uzavřené na inverzní homomorfismus
  • věta
    • mějme bezkontextový jazyk $L$ a homomorfismus $h$
    • pak $h^{-1}(L)$ je bezkontextový jazyk
    • je-li $L$ deterministický CFL, je i $h^{-1}(L)$ deterministický CFL
  • idea důkazu
    • podobně jako u regulárních jazyků
    • máme PDA s bufferem
    • buffer je konečný, takže ho lze modelovat ve stavu
  • důkaz v prezentaci
• Věta: Odečtení regulárního jazyka
  • věta
    • mějme bezkontextový jazyk $L$ a regulární jazyk $R$
    • pak $L-R$ je CFL
  • důkaz
    • $L-R=L\cap\overline R$
    • $\overline R$ je regulární
• Věta: CFL nejsou uzavřené na doplněk ani rozdíl
  • $\overline L$ nemusí být CFL
    • protože $L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}$
  • $L_1-L_2$ nemusí být CFL
    • jelikož $\Sigma^*-L$ (tedy doplněk) není vždy CFL
• Věta: Uzavřenost DCFL na doplněk, sjednocení, průnik a homomorfismus
  • lemma: doplněk deterministického CFL je opět deterministický CFL
    • převrátíme koncovost stavů
    • nedefinované kroky ošetříme podložkou na zásobníku
    • cyklus odhalíme pomocí čítače
    • až po přečtení slova prochází koncové a nekoncové stavy (stačí si pamatovat, zda prošel koncovým stavem)
  • lemma: DCFL nejsou uzavřené na sjednocení ani průnik
    • jako protipříklad průniku opět použijeme $L=\set{0^n1^n2^n\mid n\geq 1}=\set{0^n1^n2^i\mid n,i\geq 1}\cap \set{0^i1^n2^n\mid n,i\geq 1}$
    • uzavřenost sjednocení pak vylučuje identita $L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}$
  • lemma: DCFL nejsou uzavřené na homomorfismus
    • problém nastane např. když pomocí $h(c)=\epsilon$ odstraníme středovou značku z jazyka palindromů $L_{wcwr}$

Turingův stroj

• Definice: Turingův stroj
  • turingův stroj (TM) je sedmice $M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$
  • $Q$ … konečná množina stavů
  • $\Sigma$ … konečná neprázdná množina vstupních symbolů
  • $\Gamma$ … konečná množina všech symbolů pro pásku
    • vždy $\Gamma\supseteq\Sigma,,Q\cap\Gamma=\emptyset$
  • $\delta$ … (částečná) přechodová funkce
    • zobrazení $(Q-F)\times\Gamma\to Q\times\Gamma\times\set{L,R}$
    • $\delta(q,X)=(p,Y,D)$
      • $q\in (Q-F)$ … aktuální stav
      • $X\in \Gamma$ … aktuální symbol na pásce
      • $p\in Q$ … nový stav
      • $Y\in\Gamma$ … symbol pro zapsání do aktuální buňky, přepíše aktuální obsah
      • $D\in\set{L,R}$ … směr pohybu hlavy (doleva, doprava)
  • $q_0\in Q$ … počáteční stav
  • $B\in\Gamma-\Sigma$ … blank = symbol pro prázdné buňky, na začátku všude kromě konečného počtu buněk se vstupem
  • $F\subseteq Q$ … množina koncových neboli přijímajících stavů
  • poznámka: někdy se nerozlišuje $\Gamma$ a $\Sigma$ a neuvádí se $B$, pak je TM pětice
• Definice: Konfigurace Turingova stroje, krok Turingova stroje
  • konfigurace Turingova stroje (ID) je řetězec $X_1X_2\dots X_{i-1}qX_iX_{i+1}\dots X_n$
    • $q$ … stav Turingova stroje
    • čtecí hlava je vlevo od $i$-tého symbolu
    • $X_1\dots X_n$ je část pásky mezi nejlevějším a nejpravějším symbolem různým od prázdného
      • výjimka: pokud je hlava na kraji, na tom kraji vkládáme jeden $B$ navíc
  • kroky turingova stroje $M$ značíme podobně jako u zásobníkových automatů ($\vdash_M,\vdash_M^*$)
• Definice: TM přijímá jazyk, rekurzivně spočetný jazyk
  • turingův stroj $M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$ přijímá jazyk $L(M)=\set{w\in\Sigma^:(\exists p\in F)(\exists \alpha,\beta\in\Gamma^)(q_0w\vdash_M^*\alpha p\beta)}$
    • tj. množinu slov, po jejichž přečtení se dostane do koncového stavu
    • pásku nemusí uklízet (v naší definici)
  • jazyk nazveme rekurzivně spočetným, pokud je přijímán nějakým Turingovým strojem
• Definice: Přechodový diagram pro TM
  • jako pro konečný automat
  • hrana $q\to p$ je označena seznamem všech dvojic $X/YD$, kde $\delta(q,X)=(p,Y,D)$
    • $D\in\set{\leftarrow,\rightarrow}$
• Definice: Vícepáskový Turingův stroj
  • počáteční pozice
    • vstup na první pásce, ostatní zcela prázdné
    • první hlava vlevo od vstupu, ostatní libovolně
    • hlava v počátečním stavu
  • jeden krok vícepáskového TM
    • hlava přejde do nového stavu
    • na každé pásce napíšeme nový symbol
    • každá hlava se nezávisle posune vlevo, zůstane na místě nebo se posune vpravo
• Věta: Vícepáskový Turingův stroj
  • věta: každý jazyk přijímaný vícepáskovým TM je přijímaný i nějakým (jednopáskovým) Turingovým strojem
  • důkaz
    • máme $k$-páskový TM
    • konstruujeme jednopáskový TM
    • pásku si představíme, že má $2k$ stop (nad sebou)
      • liché stopy: pozice $k$-té hlavy
      • sudé stopy: znak na $k$-té pásce
    • pro simulaci jednoho kroku navštívíme všechny hlavy
    • ve stavu si pamatujeme
      • počet hlav vlevo
      • pro každé $k$ symbol pod $k$-tou hlavou
    • pak už umíme provést jeden krok
  • simulaci výpočtu $k$-páskového stroje o $n$ krocích lze provést v čase $O(n^2)$
• Definice: Nedeterministický TM
  • nedeterministickým Turingovým strojem nazýváme sedmici stejnou jako u TM
  • akorát $\delta:(Q-F)\times\Gamma\to\mathcal P(Q\times\Gamma\times\set{L,R})$
  • slovo $w\in\Sigma^$ je přijímáno nedeterministickým TM, pokud existuje nějaký výpočet $q_0w\vdash^\alpha p\beta$, kde $p\in F$
• Věta: Nedeterministický TM
  • věta: pro každý $M_N$ nedeterministický TM existuje $M_D$ deterministický TM takový, že $L(M_N)=L(M_D)$
  • idea
    • prohledáváme do šířky všechny možné výpočty $M_N$
    • modelujeme TM se dvěma páskami
      • první páska: posloupnost (fronta) konfigurací
      • druhá páska: pomocný výpočet
    • vždycky vezmeme konfiguraci z fronty, provedeme na ní postupně každý možný krok a výsledek vždy přidáme na konec fronty
• Věta: TM s jednosměrnou páskou
  • věta: pro každý TM existuje TM, který přijímá stejný jazyk a nikdy nejde vlevo od počáteční pozice a nikdy nepíše blank $B$
  • důkaz
    • zákaz psaní blanku $B$
      • místo psaní $B$ budeme psát $B_1$
      • všechny instrukce pro čtení $B$ zkopírujeme rovněž pro čtení $B_1$
    • jednosměrná páska
      • přepíšeme vstup do horní stopy dvoustopé pásky
      • pod nejlevější symbol dáme nový znak $*$, abychom věděli, že jsme na levém okraji a máme přepnout z horní stopy do dolní
      • ve stavu („hlavě“) si pamatujeme, jestli čteme horní nebo spodní stopu
      • pokud vidíme $*$, odpovídající instrukce přepíšeme na změnu stopy

LBA, diagonální jazyk

• Definice: Separovaná gramatika
  • definice: gramatika je separovaná, pokud obsahuje pouze pravidla tvaru $\alpha\to\beta$, kde
    • buď $\alpha,\beta\in V^+$ (neprázdné posloupnosti neterminálů),
    • nebo $\alpha\in V$ a $\beta\in T\cup\set{\epsilon}$
  • lemma: ke každé gramatice $G$ lze sestrojit ekvivalentní separovanou gramatiku $G'$
    • stačí všechny terminály nadtrhnout a přidat pravidla $\forall a\in T:\overline a\to a$
• Definice: Monotónní (nevypouštějící) gramatika
  • gramatika je monotónní (nevypouštějící), jestliže pro každé pravidlo $(\alpha\to\beta)\in P$ platí $|\alpha|\leq|\beta|$
  • monotónní gramatiky slovo v průběhu generování nezkracují
  • lemma: ke každé monotónní gramatice lze nalézt ekvivalentní kontextovou gramatiku
    • připomenutí: v kontextové gramatice povolujeme pravidla $\alpha A\beta\to\alpha\omega\beta$
      • $A\in V$
      • $\alpha,\beta\in (V\cup T)^*$
      • $\omega\in (V\cup T)^+$
    • nejprve gramatiku separujeme
    • stále jsme se nezbavili pravidel tvaru $AB\to CD$ (a delších), kde všechna písmena jsou neterminály
    • přidáme sadu nových neterminálů
    • např. $AB\to CD$ převedeme na $AB\to\bar AB\to\bar A\bar B\to C\bar B\to CD$
• Věta: Příklad kontextového jazyka
  • lemma: jazyk $L=\set{a^ib^jc^k\mid1\leq i\leq j\leq k}$ je kontextový jazyk, není bezkontextový
  • důkaz (na jedničku je potřeba umět)
    • $S\to aSBC|aBC$ … generování symbolů $a$
    • $B\to BBC$ … množení symbolů $B$
    • $C\to CC$ … množení symbolů $C$
    • $CB\to BC$ … uspořádání symbolů $B$ a $C$ (pravidlo není kontextové, je potřeba ho upravit nadtrháváním)
    • $aB\to ab$ … začátek přepisu $B$ na $b$
    • $bB\to bb$ … pokračování přepisu $B$ na $b$
    • $bC\to bc$ … začátek přepisu $C$ na $c$
    • $cC\to cc$ … pokračování přepisu $C$ na $c$
  • je důležité, že tam chybí $cB\to cb$
• Definice: Lineárně omezený automat (LBA)
  • lineárně omezený automat je nedeterministicý TM, kde na pásce je označen levý a pravý konec $\underline l,\underline r$
  • tyto symboly nelze při výpočtu přepsat a nesmí se jít nalevo od $\underline l$ ani napravo od $\underline r$
  • slovo $w$ je přijímáno LBA, pokud existuje přijímající výpočet $q_0\underline l w\underline r\vdash^*\underline l\alpha p\beta\underline r$, kde $p\in F$
• Věta: Každý kontextový jazyk lze přijímat pomocí LBA
  • máme kontextovou gramatiku, sestrojíme LBA
  • prázdné slovo vyřešíme zvlášť
  • derivaci gramatiky budeme simulovat pomocí LBA
  • použijeme pásku se dvěma stopami
  • slovo $w$ dáme nahoru, na začátek dolní stopy dáme $S$
  • nedeterministicky přepisujeme slovo ve druhé stopě podle pravidel $G$
    • pravá část se odsune
  • pokud jsou ve druhé stopě samé terminály, porovnáme ji s první stopou
    • slovo přijmeme nebo zamítneme
• Věta: LBA přijímají pouze kontextové jazyky
  • máme LBA, sestrojíme monotónní gramatiku
  • výpočet ukryjeme do „dvoustopých“ neterminálů
  • nejprve vygenerujeme slovo, kde v horní stopě bude nějaké slovo $\in\Sigma^*$ a ve spodní bude páska LBA s tímto slovem (v prvním neterminálu dole bude trojice $q_0,\underline l,a_0$, v posledním bude dole dvojice $a_n,\underline r$)
  • pak simulujeme práci LBA ve „druhé“ stopě
  • jakmile se dostaneme do koncového stavu, smažeme „druhou“ stopu
  • speciálně je potřeba ošetřit přijímání prázdného slova – pomocí speciálního startovacího pravidla
• Věta: Rekurzivně spočetné jsou $\mathcal L_0$
  • máme TM, sestrojíme gramatiku
  • gramatika nejprve vygeneruje slovo a obrácenou pásku stroje (se slovem)
  • potom simuluje výpočet
  • nakonec smaže pásku, nechá pouze slovo
• Věta: Každý jazyk typu 0 je rekurzivně spočetný
  • idea: TM postupně generuje všechny derivace
  • derivaci $S\Rightarrow \omega_1\Rightarrow\dots\Rightarrow \omega_n=w$ kódujeme jako slovo $#S#\omega_1#\dots#w#$
  • umíme udělat TM, který přijímá slova $#\alpha#\beta#$, kde $\alpha\Rightarrow\beta$
  • umíme udělat TM, který přijímá takto zapsanou posloupnost derivací
  • tedy umíme udělat TM postupně generující všechna slova
    • vygenerujeme slovo
    • tvoří slovo derivaci?
    • končí derivace slovem $w$?
    • pokud ano, přijímáme $w$
    • pokud ne, generujeme další slovo
• Definice: TM zastaví
  • TM zastaví, pokud vstoupí do stavu $q$ s čteným symbolem $X$ a pokud neexistuje instrukce pro tuto konfiguraci, tedy $\delta(q,X)$ není definováno
  • z definice vyplývá, že v přijímajícím stavu TM zastaví
  • dokud nezastaví, nevíme, jestli přijme nebo nepřijme slovo
• Definice: Rekurzivní jazyky
  • říkáme, že TM $M$ rozhoduje jazyk $L$, pokud $L=L(M)$ a pro každé $w\in\Sigma^*$ stroj nad $w$ zastaví
  • jazyky rozhodnutelné TM nazýváme rekurzivní jazyky
  • rekurzivní jazyky jsou podmnožinou rekurzivně spočetných jazyků
• Definice: Diagonální jazyk
  • diagonální jazyk $L_d$ je definovaný jako jazyk slov $w\in\set{0,1}^*$ takových, že TM reprezentovaný jako $w$ nepřijímá slovo $w$
  • kódování TM
    • $M=\set{Q,\set{0,1},\Gamma,\delta,q_1,B,\set{q_2}}$
    • předpokládáme
      • počáteční stav je vždy $q_1$
      • $q_2$ je vždy jediný koncový stav
      • první symbol je $0$, druhý $1$, třetí $B$, ostatní symboly pásky očíslujeme libovolně
      • směr $L$ je 1, směr $L$ je 2
    • krok $\delta(q_i,X_j)=(q_k,X_l,D_m)$ kódujeme jako $0^i10^j10^k10^l10^m$
      • zjevně nebudou dvě jedničky za sebou, protože stavy, symboly i směry číslujeme od jedničky
    • celý TM se skládá z kódů přechodů v nějakém pořadí oddělených dvojicemi jedniček
  • pořadí kódů: jsou seřazeny podle délky, stejně dlouhé jsou uspořádány lexikograficky
• Věta: $L_d$ není rekurzivně spočetný jazyk
  • věta: $L_d$ není rekurzivně spočetný jazyk, tj. neexistuje TM přijímající $L_d$
  • idea důkazu
    • kdyby existoval TM přijímající $L_d$, spuštění takového stroje na vlastním kódu by vedlo k paradoxu
  • důkaz
    • mějme uspořádanou spočetnou množinu Turingových strojů
    • kód každého z nich označím jako $w_i$
    • mějme tabulku, kde v buňce $ij$ bude 1 nebo 0 podle toho, jestli automat s kódem $w_i$ přijímá slovo $w_j$
      • $L_d$ pak bude obsahovat slova $w_k$ taková, že v buňce $kk$ bude napsáno „nepřijímá“
    • předpokládejme, že $L_d$ je rekurzivně spočetný, tedy $L_d=L(M_d)$ pro nějaký TM $M_d$ (kód takového automatu máme označený jako $w_d$)
    • co bude v tabulce v buňce $dd$, které odpovídá otázce, zda automat $M_d$ přijímá svůj vlastní kód?
      • pokud $M_d$ přijímá svůj kód, je to spor, protože kód $M_d$ pak nemůže náležet do $L_d$
      • pokud $M_d$ nepřijímá svůj kód, je to spor, protože kód $M_d$ pak musí náležet do $L_d$
• Definice: Univerzální jazyk
  • univerzální jazyk $L_u$ definujeme jako množinu binárních řetězců, které kódují pár $(M,w)$, kde $M$ je TM a $w\in L(M)$
  • TM přijímající $L_u$ se nazývá univerzální Turingův stroj
• Věta: Existence univerzálního Turingova stroje
  • věta: existuje Turingův stroj $U$, pro který $L_u=L(U)$
  • idea: pojďme sestrojit Turingův stroj, který simuluje Turingův stroj s kódem $M$
  • důkaz
    • popíšeme $U$ jako vícepáskový Turingův stroj
    • na první pásce máme přechody $M$ a řetězec $w$
    • na druhé pásce simulujeme výpočet $M$ používající stejný formát jako kód $M$ (takže nuly oddělené jedničkami)
    • třetí páska obsahuje stav $M$ reprezentovaný $i$ nulami
    • dále máme pomocnou čtvrtou pásku
    • průběh výpočtu
      • otestujeme, zda je kód $M$ legitimní (jestli ne, zastavíme $U$ bez přijetí)
      • inicializujeme 2. pásku kódovaným slovem (každý znak kódujeme jako jedničku a $k$ nul, kde $k$ je číslo znaku)
        • blanky necháme prázdné a nahradíme 1000 pouze v případě potřeby
      • na 3. pásku napíšeme počáteční stav 0
      • posuneme hlavu na 2. pásce na první simulované políčko
      • simulace jednoho přechodu
        • na první pásce najdeme přechod
        • změníme stav na 3. pásce
        • nahradíme znak na 2. pásce (tady používáme pomocnou 4. pásku)
        • posuneme hlavu na 2. pásce správným směrem
      • pokud jsme nenašli instrukci pro $M$, zastavíme
      • pokud $M$ přejde do přijímajícího stavu, tak $U$ také přijme
• Věta: Postova věta
  • lemma: je-li $L$ rekurzivní jazyk, je rekurzivní i $\overline L$
    • stroj se vždycky zastaví, stačí prohodit přijetí/nepřijetí
  • Postova věta: jazyk $L$ je rekurzivní $\iff$ $L$ i $\overline L$ jsou rekurzivně spočetné
  • důkaz $\implies$
    • triviální
  • důkaz $\impliedby$
    • máme TM pro $L$ (označíme $M_1$) i pro $\overline L$ (označíme $M_2$)
    • pro $w$ naráz simulujeme běh $M_1$ i $M_2$ v Turingově stroji $M$
    • pokud jeden z $M_i$ přijme, $M$ zastaví a odpoví
    • jazyky jsou komplementární, takže jeden z $M_i$ vždy zastaví
• Věta: Nerozhodnutelnost univerzálního jazyka
  • věta: $L_u$ je rekurzivně spočetný, ale není rekurzivní
  • důkaz
    • máme TM přijímající $L_u\implies$ $L_u$ je rekurzivně spočetný
    • kdyby byl $L_u$ rekurzivní, tak by $\overline{L_u}$ byl také rekurzivní
    • pro TM $M$ přijímající $\overline{L_u}$ můžeme zkontruovat TM $M'$ přijímající $L_d$
      • stačí ze slova $w$ na vstupu $M'$ vytvořit dvojici $(w,w)$ a předat ji Turingovu stroji $M$
      • výsledek jeho výpočtu určí výsledek výpočtu $M'$
    • protože víme, že $L_d$ není rekurzivně spočetný, pak $\overline{L_u}$ není rekurzivně spočetný a $L_u$ není rekurzivní

Nerozhodnutelné problémy

• Definice: Rozhodnutelný problém
  • problém … množina otázek (nebo spíše vstupů) kódovatelná řetězci nad abecedou $\Sigma$ s odpověďmi $\in\set{\text{ano},\text{ne}}$
    • pokud problém definuji jako množinu, jde o otázku, zda vstup kóduje prvek dané množiny (např. polynom s celočíselným kořenem)
  • problém je (algoritmicky) rozhodnutelný, pokud existuje TM takový, že pro každý vstup $w\in P$ TM zastaví a navíc přijme, právě když $P(w)=\text{ano}$ (tj. pro $P(w)=\text{ne}$ zastaví v nepřijímajícím stavu)
  • nerozhodnutelný problém … není rozhodnutelný
  • existuje analogie mezi rozhodnutelným problémem a rekurzivním jazykem
• Věta: Redukce problému
  • definice: redukcí problému $P_1$ na $P_2$ nazýváme algoritmus $R$, který pro každou instanci $w\in P_1$ zastaví a vydá $R(w)\in P_2$, přičemž…
    • $P_1(w)=\text{ano}\iff P_2(R(w))=\text{ano}$
    • tedy i $P_1(w)=\text{ne}\iff P_2(R(w))=\text{ne}$
  • věta: existuje-li redukce problému $P_1$ na $P_2$, pak…
    • pokud $P_1$ je nerozhodnutelný, pak je nerozhodnutelný i $P_2$
    • pokud $P_1$ není rekurzivně spočetný, pak není rekurzivně spočetný ani $P_2$
  • důkaz
    • kdyby byl $P_2$ rozhodnutelný (respektive rekurzivně spočetný), mohli bychom algoritmus pro převod vstupu $P_1$ na vstup $P_2$ zkombinovat s algoritmem pro $P_2$, takže bychom dostali rozhodnutelný (nebo rekurzivně spočetný) algoritmus pro $P_1$, což by byl spor
• Věta: Problém zastavení není rozhodnutelný
  • definice: instancí problému zastavení je dvojice řetězců $M,w\in\set{0,1}^*$
  • definice: problém zastavení je najít algoritmus $\text{Halt}(M,w)$, který vydá 1, právě když stroj $M$ zastaví na vstupu $w$, jinak vydá 0
  • věta: problém zastavení není rozhodnutelný
  • idea důkazu: redukujeme $L_d$ na $\text{Halt}$
  • důkaz
    • předpokládejme, že máme algoritmus (Turingův stroj) pro $\text{Halt}$
    • modifikujeme ho na stroj $\text{Halt}_\text{no}(w)$
      • $w\in\set{0,1}^*$
      • pokud $\text{Halt}(w,w)$ vrátí 1, spustíme nekonečný cyklus
      • jinak zastavíme
    • takže $\text{Halt}_\text{no}(w)$ vlastně obrací výsledek $\text{Halt}(w,w)$
    • otázka $\text{Halt}(\text{Halt}\text{no},\text{Halt}\text{no})$ není řešitelná, proto algoritmus $\text{Halt}$ nemůže existovat

Časová složitost

• Definice: Časová složitost
  • mějme Turingův stroj $M$, který zastaví na každém vstupu
  • časová složitost $M$ je funkce $f:\mathbb N\to\mathbb N$, kde $f(n)$ je maximální počet kroků výpočtu $M$ nad vstupy délky $n$
• Definice: (Asymptotická) horní hranice $O(g(n))$
  • mějme funkce $f,g:\mathbb N\to\mathbb R^+$
  • říkáme, že $f(n)\in O(g(n))$, pokud existují $c,n_0\in\mathbb N^+$ taková, že $\forall n\geq n_0:f(n)\leq c\cdot g(n)$
  • v takovém případě říkáme, že $g(n)$ je (asymptotická) horní granice pro $f(n)$
• Definice: Třída časové složitosti
  • mějme funkci $t:\mathbb N\to\mathbb R^+$
  • definujeme třídu časové složitosti $\text{TIME}(t(n))$ jako množinu všech jazyků, které jsou rozhodnutelné jednopáskovým Turingovým strojem v čase $O(t(n))$
    • tj. pro vstup délky $n$ TM vždy zastaví nejpozději po $O(t(n))$ a vydá správnou odpověď
  • lemma: Turingův stroj s časem $t(n)$ má jednopáskový ekvivalent $O(t^2(n))$
• Definice: Doba běhu nedeterministického TM
  • mějme nedeterministický Turingův stroj, který zastaví na každém vstupu
  • doba běhu $M$ je funkce $f:\mathbb N\to\mathbb N$, kde $f(n)$ je maximální počet kroků, který $M$ potřebuje v jakékoliv větvi výpočtu nad jakýmkoliv vstupem délky $n$
  • o takovém nedeterministickém Turingově stroji $M$ říkáme, že rozhoduje jazyk $L(M)$ v čase $f(n)$
• Věta: Převod mezi časovou složitostí pro deterministický a nedeterministický TM
  • věta
    • mějme funkci $t:\mathbb N\to\mathbb R^+$, přičemž $t(n)\geq n$
    • každý nedeterministický Turingův stroj s časem $t(n)$ má deterministický ekvivalent $2^{O(t(n))}$
  • důkaz
    • máme-li pro dvojici $Q\times\Gamma$ maximálně $d$ variant, tak se TM po $k$ krocích může dostat maximálně do $d^k$ konfigurací
    • tedy simulujeme v čase $O(t(n)\cdot d^{t(n)})=2^{O(t(n))}$
• Věta: $CFL\subseteq P$
  • definice: $P$ ($\text{PTIME}$) … třída jazyků rozhodnutelných v polynomiálním čase jednopáskovým deterministickým Turingovým strojem
    • $P=\bigcup_k\text{TIME}(n^k)$
  • věta: každý bezkontextový jazyk patří do $P$
  • důkaz
    • gramatiku převedeme do Chomského normální formy (velikost nezávisí na $n$)
    • CYK algoritmus je polynomiální, konkrétně $O(n^3)$
• Definice: Verifikátor
  • verifikátor jazyka $L$ je algoritmus $V$, kde
    • $L=\lbrace w\mid V$ pro nějaký řetězec $c$ přijímá $\braket{w,c}\rbrace$
  • nápověda $c$ pro snadné ověření se nazývá certifikát
  • časová složitost verifikátoru se měří pouze vzhledem k délce $w$
    • polynomiální verifikátor rozhoduje v čase polynomiálním vzhledem k $|w|$
  • jazyk $L$ je polynomiálně verifikovatelný, pokud má polynomiální verifikátor
    • pak vždy existuje i polynomiální certifikát, delší by verifikátor nestihl ani přečíst
• Věta: $NP$, NTIME
  • definice: $NP$ … třída jazyků rozhodnutelných v polynomiálním čase
    • je tvořena jazyky s polynomiálním verifikátorem
  • definice: NTIME
    • mějme funkci $t:\mathbb N\to\mathbb R^+$
    • $\text{NTIME}(t(n))$ … třída jazyků rozhodnutelných nedeterministickým TM v čase $O(t(n))$
  • věta: $NP=\bigcup_k \text{NTIME}(n^k)$
  • idea důkazu
    • převedeme verifikátor na NTM a opačně
    • NTM uhodne certifikát a simuluje verifikátor
    • verifikátor bere prijímající větev NTM jakožto certifikát
  • důkaz $\implies$
    • mějme $L\in NP$
    • hledáme NTM $M$
    • vezmeme verifikátor $V$ z definice $NP$
      • nechť rozhoduje $L$ v čase $n^k$
    • $M$ na vstupu $w$ délky $n$
      • nedeterministicky uhodne řetězec $c$ délky $\leq n^k$
      • spustí $V$ na vstupu $\braket{w,c}$
      • pokud $V$ přijme, $M$ také přijme
  • důkaz $\impliedby$
    • mějme $L$ rozhodnutelný NTM $M$ v polynomiálním čase
    • hledáme verifikátor $V$
    • $V$ na vstupu $\braket{w,c}$
      • simuluje $M$ na vstupu $w$, v bodech větvení vybere větev podle $c$
      • pokud tato větev NTM přijme, $V$ přijme
    • pokud všechny větve selhaly, NTM nepřijímá, tedy ani $V$ nepřijímá
• Definice: Polynomiálně vyčíslitelná funkce, převoditelný jazyk, polynomiální redukce
  • funkce $f:\Sigma^\to\Sigma^$ je polynomiálně vyčíslitelná, pokud existuje Turingův stroj $M$, který pro každý vstup $w$ v polynomiálním čase zastaví s $f(w)$ na pásce
  • jazyk $A$ je převoditelný v polynomiálním čase na jazyk $B$, značíme $A\leq_P B$, pokud existuje funkce $f:\Sigma^\to\Sigma^$ vyčíslitelná v polynomiálním čase a $\forall w\in\Sigma^*:w\in A\iff f(w)\in B$
    • funkci $f$ pak nazýváme polynomiální redukcí $A$ do $B$
• Definice: SAT, 3SAT
  • formule je 3-cnf, pokud je v CNF a v každé klauzuli jsou nejvýše tři literály
  • formule je splnitelná, existuje-li takové ohodnocení výrokových proměnných, že je hodnota formule TRUE
  • problém 3SAT je pro každou 3-cnf formuli rozhodnout, zda je splnitelná
  • problém SAT je pro každou booleovskou formuli rozhodnout, zda je splnitelná
• Definice: NP úplnost
  • jazyk $B$ je NP-úplný, pokud je NP a každý jazyk $A\in NP$ je na $B$ polynomiálně převoditelný
  • věta: pokud $B$ je NP-úplný a $B\in P$, pak $P=NP$
  • věta: pokud $B$ je NP-úplný a $B\leq_P C$ pro nějaké $C\in NP$, pak $C$ je NP-úplný
• Věta: Cook-Levinova věta
  • věta: SAT je NP-úplný.
  • důkaz
    • SAT je NP: nedeterministický TM uhodne správné ohodnocení a v polynomiálním čase ověří, že je pro něj formule pravdivá
    • dále dokážeme, že je SAT NP-úplný
    • vezmeme libovolný $L\in NP$
    • nechť $M$ je nedeterministický TM, který rozhoduje jazyk $L$ v čase $n^k-3$ pro nějaké $k$
      • uvažujeme jenom $n^k-3$ kvůli šířce tabulky – aby hlava nemohla vyjet ven
    • pro jednoduchost uvažujeme NTM s jednostrannou páskou
    • vytvoříme tabulku $n^k\times n^k$, každý řádek odpovídá konfiguraci $M$ na vstupu $w$
    • tabulku „dláždíme“ okénky širokými 3 buňky a vysokými 2 buňky
    • na základě přechodové funkce $\delta$ jsou povoleny jen určité typy okének
    • pokud tabulku vydláždíme jen povolenými okénky, každý řádek bude odpovídat legální konfiguraci TM dosažitelné jedním krokem z předchozího řádku
      • nedeterminismus se schová v SATu
    • z tabulky vytvoříme formuli $\phi=\phi_\text{cell}\land\phi_\text{start}\land\phi_\text{move}\land\phi_\text{accept}$
    • $\phi_\text{cell}$ povoluje pro každé políčko tabulky právě jedno písmeno
    • $\phi_\text{start}$ definuje počáteční konfiguraci pro vstup $w$
    • $\phi_\text{move}$ popisuje povolené kroky (okénka)
    • $\phi_\text{accept}$ je disjunkce přes přítomnost přijímajícího stavu v libovolné buňce tabulky
    • tvrzení: převod má polynomiální složitost, konkrétně $O(n^{2k}\log n)$
• Věta: 3SAT je NP-úplný
  • použijeme důkaz Cook-Levinovy věty
  • je potřeba prevést okénka pohybu do CNF
    • stačí konstantní čas – velikost podformule závisí na stroji, nikoliv na délce vstupu
  • dlouhé klauzule rozdělíme zavedením nových proměnných

co-NP, prostorová složitost

• Věta: Problém tautologičnosti je co-NP
  • definice: jazyk $L\subseteq\Sigma^$ patří do třídy co-NP, právě když jeho doplněk $\Sigma^-L$ patří do NP
    • P je částí NP i co-NP
    • domníváme se, že NP-úplné problémy nejsou v co-NP (pokud P = NP, tak jsou)
  • definice: problém, zda je výroková formule tautologie, nazýváme tautologičnost (TAUT)
  • věta: problém tautologičnosti je co-NP
    • důkaz z pozorování, že doplněk TAUT (do množiny korektních formulí) je snadno převoditelný na SAT a SAT je v NP
    • doplněk TAUT
      • existuje ohodnocení, pro které je formule FALSE?
      • je negace formule splnitelná?
    • doplněk SAT
      • je negace formule tautologie?
• Definice: Prostorová složitost
  • pro deterministický Turingův stroj $M$, který zastaví na každém vstupu, je prostorová složitost $M$ funkce $f:\mathbb N\to\mathbb N$, kde $f(n)$ je maximální počet buněk pásky, které $M$ přečte při jakémkoliv vstupu délky $n$
  • pro nedeterministický Turingův stroj $M$, jehož všechny větve výpočtu zastaví na každém vstupu, je prostorová složitost $M$ funkce $f:\mathbb N\to\mathbb N$, kde $f(n)$ je maximální počet buněk pásky, které $M$ přečte při jakémkoliv vstupu délky $n$ na libovolné větvi výpočtu
• Definice: Třídy prostorové složitosti
  • mějme funkci $f:\mathbb N\to\mathbb R^+$
  • definujeme třídy prostorové složitosti $\text{SPACE}(f(n))$ a $\text{NSPACE}(f(n))$
  • $\text{SPACE}(f(n))$ … třída jazyků rozhodnutelných v prostoru $O(f(n))$ deterministickým TM
  • $\text{NSPACE}(f(n))$ … třída jazyků rozhodnutelných v prostoru $O(f(n))$ nedeterministickým TM
• Věta: Savitchova věta
  • věta: pro libovolnou funkci $f:\mathbb N\to\mathbb R^+$, pro kterou $f(n)\geq n$, platí $\text{NSPACE}(f(n))\subseteq\text{SPACE}(f^2(n))$
  • důkaz
    • nestačí NTM simulovat přímo, to bychom potřebovali prostor $2^{O(f(n))}$
    • v kvadratickém čase vyřešíme problém dosažitelnosti (CANYIELD)
      • „je v NTN z konfigurace $c_1$ dosažitelná konfigurace $c_2$ v maximálně $t$ krocích a maximálně používající prostor $f(n)$?“
      • metoda rozděl a panuj
      • za $c_1$ vezmeme počáteční konfiguraci, za $c_2$ přijímající
    • simulujeme NTM pomocí TM v kvadratickém prostoru
      • NTM modifikujeme, aby se před přijetím „vynuloval“ (smazal pásku a posunul se na nejlevější políčko)
      • sloučíme přijímající stavy do jednoho
      • tím máme jednoznačnou přijímající konfiguraci
      • najdeme $d$ maximální počet štěpení konfigurace v jednom kroku, tj. horní odhad pro počet konfigurací
        • je to $2^{d\cdot f(n)}$
      • tak získáme i horní odhad času běhu libovolné větve
    • složitost simulace
      • CANYIELD potřebuje ukládat konfigurace a $t$, tj. $O(f(n))$ prostoru
      • počet volání CANYIELD je logaritmický vzhledem k $t=2^{d\cdot f(n)}$
      • hloubka rekurze je $O(\log(2^{d\cdot f(n)}))$, tedy $O(f(n))$
      • celkem $O(f(n))\cdot O(f(n))=O(f^2(n))$ prostoru
      • potřebujeme znát $f(n)$, ale to nevadí, můžeme zkoušet postupně od jedničky nebo přidat do předpokladu, že NTM rozhoduje jazyk v prostoru $f(n)$
• Definice: PSPACE
  • PSPACE … třída jazyků rozhodnutelných v polynomiálním prostoru deterministickým Turingovým strojem
    • $\text{PSPACE}=\bigcup_{k\in\mathbb N}\text{SPACE}(n^k)$
  • NPSPACE ani nedefinujeme, protože NPSPACE = PSPACE, podle Savichovy věty
• Věta: Prostorové a časové třídy
  • věta: $P\subseteq NP\subseteq\text{PSPACE}=\text{NPSPACE}\subseteq\text{EXPTIME}=\bigcup_k\text{TIME}(2^{n^k})$
  • $P\subseteq \text{PSPACE}$, respektive $NP\subseteq\text{NPSPACE}$
    • stroj v čase $t(n)$ navštíví maximálně $t(n)$ políček, proto pro $t(n)\geq n$ stačí prostor $t(n)$
  • $\text{PSPACE}\subseteq\text{EXPTIME}$
    • pro $f(n)\geq n$ dosáhne TM $M$ pracující v prostoru $f(n)$ maximálně $f(n)\cdot 2^{O(f(n))}$ různých konfigurací
    • v konečném deterministickém výpočtu se žádná konfigurace neopakuje, proto existuje TM $M'$ simulující $M$ v čase $f(n)\cdot 2^{O(f(n))}$
  • jediná nerovnost, co víme, je $P\neq \text{EXPTIME}$