{{predmet|Automaty a gramatiky|Roman Barták|TIN071}}

*[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<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, $\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$

<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 $\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$ .

<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ší ##

| 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| [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 α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>*|
|\[\[Image:Chomskeho_hierarchie.png
"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 [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,δ,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](Category:Informatika)