# 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}$