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

*Bartákova stránka - odkazy, slajdy, cvičení, ... *Zadání z Modrého - téměř všechno (uz davno neplati), co třeba vědet na zkoušku ...

*AutomatyAGramatiky - mnoho odkazu a animaci z roku 2008

Slovníček pojmů

Kvocient

Levý kvocient

  • Levý kvocient L1 podle L2

    • L2 \ L1 = { v | uv ∈ L1 & u ∈ L2 }

Levá derivace

  • Levá derivace L podle w

    • w = {w} \ L

Pravý kvocient

  • Pravý kvocient L1 podle L2

    • L1 / L2 = { u | uv ∈ L1 & v ∈ L2 }

Pravá derivace

  • Pravá derivace L podle w

    • Rw = 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 uviw ∈ 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ší

Jedinou výjimkou je pravidlo S → λ, potom se ale S nevyskytuje na pravé straně žádného pravidla.
"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+

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

(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,δ,q0,Z0,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