Syntax highlighting of Archiv/Automaty a gramatiky

{{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 &isin; L<sub>1</sub> &amp; u &isin; L<sub>2</sub> }

=== Levá derivace ===

* Levá derivace L podle w
** &part;<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 &isin; L<sub>1</sub> &amp; v &isin; L<sub>2</sub> }

=== Pravá derivace ===

* Pravá derivace L podle w
** &part;<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 a ti další==
{| border="1"
! Typ
! Gramatiky
! Jazyky
/! Automaty
! Pravidla
|- 
| Typu 0
| Gramatiky typu 0
| Rekurzivně spočetné jazyky
| Turingův stroj
| Pravidla v obecné formě (tj. u &rarr; v, kde u,v &isin; (V<sub>N</sub>&cup;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 &alpha;X&beta; &rarr; &alpha;w&beta;, X &isin; V<sub>N</sub>; &alpha;,&beta; &isin; (V<sub>N</sub>&cup;V<sub>T</sub>)*; w &isin; (V<sub>N</sub>&cup;V<sub>T</sub>)<sup>+</sup>

Jedinou výjimkou je pravidlo S &rarr; &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 &rarr; w, X &isin; V<sub>N</sub>; w &isin; (V<sub>N</sub>&cup;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 &rarr; wY, X &rarr; w; X,Y &isin; V<sub>N</sub>; w &isin; 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/>
Z originálu: http://en.wikipedia.org/wiki/Template:Formal_languages_and_grammars
</small>
|-
|}

== Iterační (pumping) lemma ==
Pokud je jazyk L regulární, existuje číslo n > 0 tak, že každé slovo z &isin; 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 &isin; L pro každé i≥0.

<small>(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>