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$