{{predmet|Automaty a gramatiky|Roman Barták|TIN071}}
*[http://kti.ms.mff.cuni.cz/~bartak/automaty/index.html Bartákova stránka] - odkazy, slajdy, cvičení, ...
*[http://mff.modry.cz/autogra/pisemky/pisemky.txt Zadání z Modrého] - 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<sub>1</sub> podle L<sub>2</sub>
** L<sub>2</sub> \ L<sub>1</sub> = { v | uv ∈ L<sub>1</sub> & u ∈ L<sub>2</sub> }
=== Levá derivace ===
* Levá derivace L podle w
** ∂<sub>w</sub> = {w} \ L
=== Pravý kvocient ===
* Pravý kvocient L<sub>1</sub> podle L<sub>2</sub>
** L<sub>1</sub> / L<sub>2</sub> = { u | uv ∈ L<sub>1</sub> & v ∈ L<sub>2</sub> }
=== Pravá derivace ===
* Pravá derivace L podle w
** ∂<sup>R</sup><sub>w</sub> = L / {w}
== Kongruence ==
Nechť X je konečná abeceda, <math>\sim</math> je relace ekvivalence na X*.
Potom:
* <math>\sim</math> je pravá kongruence, jestliže <math>
\forall u,v,w \in X^*
</math><math>u \sim v \Rightarrow uw \sim vw</math>
<small>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.</small>
== Nerodova věta ==
Nechť L je jazyk nad konečnou abecedou X. Pak platí:
L je rozpoznatelný konečným automatem <math>\Leftrightarrow</math> existuje pravá kongruence konečného indexu <math>\sim</math> na množině X*, pro níž platí, že L je sjednocením jistých tříd rozkladu <math>X^*/\sim</math> .
<small>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.</small>
== Iterační (pumping) lemma ==
Pokud je jazyk L regulární, existuje číslo n > 0 tak, že každé slovo z ∈ L, pro které platí |z| ≥ n, lze zapsat ve tvaru z = uvw, kde pro slova u, v a z platí, že |uv| ≤ n, |v| > 0 a uv<sup>i</sup>w ∈ L pro každé i≥0.
<small>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.</small>
== Kleeneova věta ==
Jazyk je regulární, právě když je rozpoznatelný konečným automatem.
<small>Důkaz se dá indukcí podle počtu hran v nedeterministickém automatu.</small>
== Chomského hierarchie a ti další==
{| border="1"
! 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 → v, kde u,v ∈ (V<sub>N</sub>∪V<sub>T</sub>)* a <i>u</i> obsahuje alespoň 1 neternimální symbol)
|-
| není
| (není společný název)
| Rekurzivní jazyky
| [http://en.wikipedia.org/wiki/Machine_that_always_halts Vždy zastavující Turingův stroj]
|
|- style="border-bottom:1px solid grey;"
| Typu 1
| Kontextové gramatiky
| Kontextové jazyky
| Lineárně omezené automaty
| Pouze pravidla ve tvaru αXβ → αwβ, X ∈ V<sub>N</sub>; α,β ∈ (V<sub>N</sub>∪V<sub>T</sub>)*; w ∈ (V<sub>N</sub>∪V<sub>T</sub>)<sup>+</sup>
Jedinou výjimkou je pravidlo S → λ, 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 → w, X ∈ V<sub>N</sub>; w ∈ (V<sub>N</sub>∪V<sub>T</sub>)*
|-
| 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 → wY, X → w; X,Y ∈ V<sub>N</sub>; w ∈ V<sub>T</sub>*
|-
|colspan="5"|[[Image:Chomskeho_hierarchie.png|right]]<small>Každá kategorie jazyků nebo gramatik je podmnožinou jazyků nebo gramatik kategorie přímo nad ní,<br/> a jakýkoli automat v každé kategorii má ekvivaletní automat v kategorii přímo nad ním.<br/>
"není" znamená že nepatří do Chomskeho hierarchie.<br/>
Z originálu: http://en.wikipedia.org/wiki/Template:Formal_languages_and_grammars
</small>
|-
|}
=== Bezprefixový jazyk ===
L je bezprefixový, pokud neexistuje slovo u ∈ L takové, že rovněž uw ∈ L, w ∈ X<sup>+</sup>
=== 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 [http://en.wikipedia.org/wiki/Linear_grammar#Expressive_power Lineární gramatiky na wikipedii]
== (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,δ,q<sub>0</sub>,Z<sub>0</sub>,F), je deterministický, jestliže platí:
– ∀p∈Q, ∀a∈X∪{λ}, ∀Z∈Y |δ(p,a,Z)|≤1 <small>v kazdem kroku si nemuzeme vybirat</small>
– ∀p∈Q, ∀Z∈Y ( δ(p,λ,Z)≠∅ ⇒ ∀a∈X δ(p,a,Z)=∅ ) <small>definuje ukončení vypoctu</small>
Každý krok výpočtu je přesně určen.
[[Category:Informatika]]
