{{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> }
countless of times, any proxy template preeivws are disabled due to hosting reasons.This template does in fact work, you should try reading the instructions on how to install, this isn't a PHProxy where you can just upload your files.
=== 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]
Too cool! I've been waiting for the reutrn of the automat for years.I'm old enough to have fond memories of Horn and Hardart's and I've missed it since they closed for good about 15 years ago. I'll be sure to check out Bamn next time I'm downtown.Oddly, I was walking around St. Mark's just a couple of weeks ago and I didn't even spot it.whMhZJ <a href="http://ekimcxdneakc.com/">ekimcxdneakc</a>
