{{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, co třeba vědet na zkoušku ...
= 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>
== Chomského hierarchie ==
=== Rekurzivně spočetné jazyky ===
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)
=== Kontextové jazyky ===
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.
=== Bezkontextové jazyky ===
Pouze pravidla ve tvaru X → w, X ∈ V<sub>N</sub>; w ∈ (V<sub>N</sub>∪V<sub>T</sub>)*
=== Regulární (pravé lineární) jazyky ===
Pouze pravidla ve tvaru X → wY, X → w; X,Y ∈ V<sub>N</sub>; w ∈ V<sub>T</sub>*
