- [Bartákova stránka](http://kti.ms.mff.cuni.cz/%7Ebartak/automaty/index.html) - odkazy, slajdy, cvičení, ... - [Zadání z Modrého](http://mff.modry.cz/autogra/pisemky/pisemky.txt) - téměř všechno (uz davno neplati), co třeba vědet na zkoušku ... - http://mff.lokiware.info/AutomatyAGramatiky - mnoho odkazu a animaci z roku 2008 # Slovníček pojmů ## Kvocient ### Levý kvocient - Levý kvocient $L_{1}$ podle $L_{2}$ - $L_{2} \setminus L_{1} = \{\, v \mid uv \in L_{1} \;\&\; u \in L_{2} \,\}$ ### Levá derivace - Levá derivace L podle w - $\partial_{w} = \{w\} \setminus L$ ### Pravý kvocient - Pravý kvocient $L_{1}$ podle $L_{2}$ - $L_{1} / L_{2} = \{\, u \mid uv \in L_{1} \;\&\; v \in L_{2} \,\}$ ### Pravá derivace - Pravá derivace L podle w - $\partial^{R}_{w} = L / \{w\}$ ## Kongruence Nechť X je konečná abeceda, $\sim$ je relace ekvivalence na X*. Potom: - $\sim$ je pravá kongruence, jestliže $\forall u,v,w \in X^* : u \sim v \Rightarrow uw \sim vw$ Pokud dvě různá slova u,v převedou automat do stejného stavu (=jsou navzájem ekvivalentní (u ~ v)), pak musí patřit do stejné třídy rozkladu. Pokud k těmto dvěma slovům přidáme stejné slovo zprava, pak tato zřetězená slova budou opět patřit do stejné třídy rozkladu (=musí být navzájem ekvivalentní (uw ~ vw)). A toto je právě ta vlastnost definující pravou kongruenci. ## Nerodova věta Nechť L je jazyk nad konečnou abecedou X. Pak platí: L je rozpoznatelný konečným automatem $\Leftrightarrow$ existuje pravá kongruence konečného indexu $\sim$ na množině X*, pro níž platí, že L je sjednocením jistých tříd rozkladu $X^*/\sim$ . Důležité tedy je, že pokud je jazyk regulární, pak pro něj musí existovat pravá kongruence, která (což je nejdůležitější) rozkládá všechna slova jazyka do konečně mnoha tříd. ## Iterační (pumping) lemma Pokud je jazyk L regulární, existuje číslo n > 0 tak, že každé slovo $z \in L$, pro které platí $|z| \geq n$, lze zapsat ve tvaru z = uvw, kde pro slova u, v a z platí, že $|uv| \leq n$, |v| > 0 a $uv^{i}w \in L$ pro každé $i \geq 0$. Je to trošku jiná formulace než používá Barták, ale je zní lépe vidět platnost pro konečné jazyky: když je jazyk konečný, tak si za n stačí vzít délku nejdelšího slova a pak to pro všechny slova delší než n (tj. žádná) platí taky. ## Kleeneova věta Jazyk je regulární, právě když je rozpoznatelný konečným automatem. Důkaz se dá indukcí podle počtu hran v nedeterministickém automatu. ## Chomského hierarchie a ti další | Zařazení do Chomskeho hierarchie| Gramatiky| Jazyky| Automaty| Pravidla| |----|----|----|----|----| | Typu 0| Gramatiky typu 0| Rekurzivně spočetné jazyky| Turingův stroj| Pravidla v obecné formě (tj. $u \to v$, kde $u,v \in (V_{N} \cup V_{T})^{*}$ a *u* obsahuje alespoň 1 neternimální symbol)| | není| (není společný název)| Rekurzivní jazyky| [Vždy zastavující Turingův stroj](http://en.wikipedia.org/wiki/Machine_that_always_halts)| | | Typu 1| Kontextové gramatiky| Kontextové jazyky| Lineárně omezené automaty| Pouze pravidla ve tvaru $\alpha X \beta \to \alpha w \beta$, $X \in V_{N}$; $\alpha,\beta \in (V_{N} \cup V_{T})^{*}$; $w \in (V_{N} \cup V_{T})^{+}$ Jedinou výjimkou je pravidlo $S \to \lambda$, potom se ale S nevyskytuje na pravé straně žádného pravidla.| | Typu 2| Bezkontextové gramatiky| Bezkontextové jazyky| (Nedeterministický) Zásobníkový automat| Pouze pravidla ve tvaru $X \to w$, $X \in V_{N}$; $w \in (V_{N} \cup V_{T})^{*}$| | není| Deterministické bezkontextové gramatiky| Deterministické bezkontextové jazyky| Deterministický zásobníkový automat| | | Typu 3| Regulární gramatiky| Regulární (pravé lineární) jazyky| Konečný automat| Pouze pravidla ve tvaru $X \to wY$, $X \to w$; $X,Y \in V_{N}$; $w \in V_{T}^{*}$| |\[\[Image:Chomskeho_hierarchie.png "není" znamená že nepatří do Chomskeho hierarchie.
Z originálu: http://en.wikipedia.org/wiki/Template:Formal_languages_and_grammars | || ### Bezprefixový jazyk L je bezprefixový, pokud neexistuje slovo $u \in L$ takové, že rovněž $uw \in L$, $w \in X^{+}$ ### Lineární jazyky Jsou jazyky generované gramatikami s pravidly ve tvaru X->aYb, kde a,b jsou řetězce terminálů a X,Y jsou neterminály. Jsou podmnožinou bezkontextových jazyků, a to vlastní (Dyckův jazyk je bezkontextový, ale není lineární). Viz [Lineární gramatiky na wikipedii](http://en.wikipedia.org/wiki/Linear_grammar#Expressive_power) ## (Nedeterministický) Zásobníkový automat ### Přijímání koncovým stavem Skončí když je slovo přečteno a automat je v koncovém stavu. ### Přijímání prázdným zásobníkem Skončí když je slovo přečteno a zásobník je prázdný. ### Deterministický zásobníkový automat Říkáme, že zásobníkový automat $M=(Q,X,Y,\delta,q_{0},Z_{0},F)$, je deterministický, jestliže platí: – $\forall p \in Q,\ \forall a \in X \cup \{\lambda\},\ \forall Z \in Y\ |\delta(p,a,Z)| \leq 1$ v kazdem kroku si nemuzeme vybirat – $\forall p \in Q,\ \forall Z \in Y\ (\ \delta(p,\lambda,Z) \neq \emptyset \Rightarrow \forall a \in X\ \delta(p,a,Z) = \emptyset\ )$ definuje ukončení vypoctu Každý krok výpočtu je přesně určen.