• 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 ...

  • http://mff.lokiware.info/AutomatyAGramatiky - mnoho odkazu a animaci z roku 2008

Slovníček pojmů

Kvocient

Levý kvocient

  • Levý kvocient L1L_{1} podle L2L_{2}

    • L2∖L1={ v∣uv∈L1  &  u∈L2 }L_{2} \setminus L_{1} = \{\, v \mid uv \in L_{1} \;\&\; u \in L_{2} \,\}

Levá derivace

  • Levá derivace L podle w

    • ∂w={w}∖L\partial_{w} = \{w\} \setminus L

Pravý kvocient

  • Pravý kvocient L1L_{1} podle L2L_{2}

    • L1/L2={ u∣uv∈L1  &  v∈L2 }L_{1} / L_{2} = \{\, u \mid uv \in L_{1} \;\&\; v \in L_{2} \,\}

Pravá derivace

  • Pravá derivace L podle w

    • ∂wR=L/{w}\partial^{R}_{w} = L / \{w\}

Kongruence

Nechť X je konečná abeceda, ∼\sim je relace ekvivalence na X*.

Potom:

  • ∼\sim je pravá kongruence, jestliže ∀u,v,w∈X∗:u∼v⇒uw∼vw\forall u,v,w \in X^* : u \sim v \Rightarrow uw \sim vw

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.

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∗/∼X^*/\sim .

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.

Iterační (pumping) lemma

Pokud je jazyk L regulární, existuje číslo n > 0 tak, že každé slovo z∈Lz \in L, pro které platí ∣z∣≥n|z| \geq n, lze zapsat ve tvaru z = uvw, kde pro slova u, v a z platí, že ∣uv∣≤n|uv| \leq n, |v| > 0 a uviw∈Luv^{i}w \in L pro každé i≥0i \geq 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 hierarchieGramatikyJazykyAutomatyPravidla
Typu 0Gramatiky typu 0Rekurzivně spočetné jazykyTuringův strojPravidla v obecné formě (tj. u→vu \to v, kde u,v∈(VN∪VT)∗u,v \in (V_{N} \cup V_{T})^{*} a u obsahuje alespoň 1 neternimální symbol)
není(není společný název)Rekurzivní jazykyVždy zastavující Turingův stroj
Typu 1Kontextové gramatikyKontextové jazykyLineárně omezené automatyPouze pravidla ve tvaru αXβ→αwβ\alpha X \beta \to \alpha w \beta, X∈VNX \in V_{N}; α,β∈(VN∪VT)∗\alpha,\beta \in (V_{N} \cup V_{T})^{*}; w∈(VN∪VT)+w \in (V_{N} \cup V_{T})^{+}
Jedinou výjimkou je pravidlo S→λS \to \lambda, potom se ale S nevyskytuje na pravé straně žádného pravidla.
Typu 2Bezkontextové gramatikyBezkontextové jazyky(Nedeterministický) Zásobníkový automatPouze pravidla ve tvaru X→wX \to w, X∈VNX \in V_{N}; w∈(VN∪VT)∗w \in (V_{N} \cup V_{T})^{*}
neníDeterministické bezkontextové gramatikyDeterministické bezkontextové jazykyDeterministický zásobníkový automat
Typu 3Regulární gramatikyRegulární (pravé lineární) jazykyKonečný automatPouze pravidla ve tvaru X→wYX \to wY, X→wX \to w; X,Y∈VNX,Y \in V_{N}; w∈VT∗w \in V_{T}^{*}
[[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∈Lu \in L takové, že rovněž uw∈Luw \in L, w∈X+w \in 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)M=(Q,X,Y,\delta,q_{0},Z_{0},F), je deterministický, jestliže platí:

– ∀p∈Q, ∀a∈X∪{λ}, ∀Z∈Y ∣δ(p,a,Z)∣≤1\forall p \in Q,\ \forall a \in X \cup \{\lambda\},\ \forall Z \in Y\ |\delta(p,a,Z)| \leq 1 <small>v kazdem kroku si nemuzeme vybirat</small>

– ∀p∈Q, ∀Z∈Y ( δ(p,λ,Z)≠∅⇒∀a∈X δ(p,a,Z)=∅ )\forall p \in Q,\ \forall Z \in Y\ (\ \delta(p,\lambda,Z) \neq \emptyset \Rightarrow \forall a \in X\ \delta(p,a,Z) = \emptyset\ ) <small>definuje ukončení vypoctu</small>

Každý krok výpočtu je přesně určen.