16 - Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky

Question 1

Základní pojmy

Answer 1

Abeceda (značíme Σ (Sigma))
• je neprázdná konečná množina, jejíž prvky nazýváme symboly, značíme Σ.

Řetězec / slovo / věta (značíme w(omega))
• konečná posloupnost symbolů abecedy
• Alternativní definice:
1) Prázdný řetezec je řetezec
2) Je-li w řetězec a a symbol abecedy pak wa je řetezec
3) Řetězce jsou vše, co lze získat jen a pouze aplikací pravidel 1) a 2)

Prázdný řetězec ε
• řetězec neobsahující žádný symbol

Konkatenace (značíme xy)
Připojení řetězce za jiný řetězec
• konkatenace je asociativní
• prázdný řetězec je neutrální prvek vzhledem ke konkatenaci

Iterace (značíme Σ^*)
• množina všech řetězců nad abecedou Σ
• (volný monoid nad abecedou Σ generovaný operací konkatenace)
○ Tj. konkatenace není komutativní jenom asociativní a neutrální prvek je prázdný řetězec

Pozitivní iterace (značíme Σ^+)
• Iterace bez prázdného řetězce

Formální jazyk (značíme L)
• Jakákoli podmnožina L⊆Σ^∗

Konkatenace jazyků
• Rozumíme binární operaci L1⋅L2={xy ┤|x∈L1∧y∈L2}

Iterace jazyka
	• L^0={ε}
	Lⁿ = L · Lⁿ⁻¹ pro n ≥ 1
	L* = ∪ Lⁿ pro pro n ≥ 0
	L⁺ = ∪ Lⁿ pro pro n ≥ 1
	• L^*=⋃_(n≥0)▒L^n

Question 2

Gramatika

Answer 2

Gramatika (značíme G) je čtveřice G = (N, Σ, P, S), kde:
• N je konečná množina nonterminálních symbolů (nonterminálů)
• Σ je konečná množina terminálních symbolů (terminálů)
• P je konečná množina přepisovacích pravidel
• S je počáteční (výchozí, startovací) nonterminál S∈N

Question 3

Gramatika - přepisovací pravidla, derivace, větná forma a jazyk generovaný gramatikou

Answer 3

Přepisovací pravidla
Podmnožina kartézského součinu (N∪Σ)^∗ N(N∪Σ)^∗×(N∪Σ)^∗
• (a,b)∈P zapisujeme ve tvaru a→b

Přímá derivace (značíme ⇒)
Binární relace mezi řetězci u, v která platí pokud můžeme řetězce zapsat jako u=gad, v=gbd a (a,b)∈P
• tj. pokud lze řetězec v vytvořit z řetězce u aplikací jednoho přepisovacího pravidla

Derivace ⇒^+
Tranzitivní uzávěr relace přímé derivace.
• tj. pokud lze vytvořit řetězec v z řetězce u postupnou aplikací několika přepisovacích pravidel

Derivace ⇒^∗
Tranzitivní a reflexivní uzávěr relace přímé derivace
• tj. pokud lze vytvořit řetězec v z řetězce u postupnou aplikací několika přepisovacích pravidel nebo pokud jsou řetězce stejné

Větná forma
Řetězec terminálů a nonterminálů (α), které jsou iterací derivace počátečního nontermínálu (S⇒^* α)
• S je tedy taky větná forma: S⇒^0 S

Věta
Větná forma obsahující pouze terminály.

Jazyk generovaný gramatikou
Množina všech vět, které patří do gramatiky (L(G)={w ┤|S⇒^* w∧w∈Σ^*})

Question 4

Chomského hierarchie klasifikace gramatik

Answer 4

Klasifikace je definována podle tvaru přepisovacích pravidel příslušných gramatik.
Platí: L_3⊂L_2⊂L_1⊂L_0

Typ 0 – obecné (neomezené) gramatiky
• Jazyky: rekurzivně vyčíslitelné jazyky (rekurzivně spočetné jazyky = TS se může zacyklit, rekurzivní = stroj vždy akceptuje nebo zamítá (úplný TS))
• Automaty: Turingovy stroje
• Tvar pravidel: α→β
○ α∈(N∪Σ)^∗ N(N∪Σ)^*
○ β∈(N∪Σ)^*
Tedy je to to stejné, jako když jsme obecně definovali tvar pravidel programatiky.

Typ 1 – kontextové gramatiky (Příklad - L={1^n 2^n 3^n |N≥1})
• Jazyky: kontextové jazyky
• Automaty: lineárně omezené Turingovy stroje (lineárně omezené automaty) - nikdy neopustí tu část pásky na které byl zapsán vstup
• Tvar pravidel: αAβ→αγβ (nebo S→ϵ pokud ϵ∈L a S se nevyskytuje na pravé straně žádného pravidla.)
○ A∈N
○ α, β∈(N∪Σ)^*
○ γ∈(N∪Σ)^+ //gamma
+ Substitujeme A za γ. α a β tvoří kontext a proto zůstávají.
+ Rozdíl oproti typu 2 je v kontextu. α, β tvoří kontext (proto jsou u typu 1 kontextové jazyky) a typ 2 kontext (reprezentovaný jako α, β) nemá (tedy tato tyto gramatiky generuji bezkontextové jazyky).
Nesmí dojít ke zkrácení větné formy.!

Typ 2 – bezkontextové gramatiky
	• Jazyky: bezkontextové jazyky
	• Automaty: zásobníkové automaty
	• Tvar pravidel: A→γ
		○ A∈N
		○ γ∈(N∪Σ)^*
Upřesnění: Gramatiky typu 2 mohou obsahovat ϵ pravidla. Přesto jsou jimi generované jazyky podmnožinou jazyků generovaných gramatikami typu 1, protože existuje algoritmus na převod libovolné gramatiky typu 2 na gramatiku bez ϵ pravidel.
Příklad: S → Xa, X → a, X → aX, X → abc, X → ε

Typ 3 – pravé/levé lineární gramatiky
• Jazyky: regulární jazyky
• Automaty: konečné automaty
• Tvar pravidel:
○ Pravá lineární: A→xB nebo A→x
○ Levá lineární: A→Bx nebo A→x
§ A, B∈N - max jeden neterminál
§ x∈Σ - vždycky jeden terminál (jeden znak)
§ Případně S→ϵ (takže x∈Σ∗)pokud S není na pravé straně žádného pravidla - regulární gramatika!
Pravé lineární gramatiky a levé lineární gramatiky jsou ekvivalentní.
Příklad: X → ε, X → a, X → aY

Question 5

Speciální podtypy gramatik

Answer 5

Stejné jako 3, ale x ∈ Σ (bez *).
Lineární gramatiky
Podmnožina gramatik typu 2
	• A → xBy nebo A → x
	• A, B ∈ N
	• x, y ∈ Σ*

Deterministické bezkontextové gramatiky
• Podmnožina typu 2
• jazyky přijímané deterministickým zásobníkovým automatem.

Rekurzivní gramatiky
• Podmnožina typu 0
• Přijímají je úplné TS (TS, které pro každý vstup rozhodnou – nikdy necyklí).
• Všechny kontextové jazyk jsou rekurzivní, ale ne všechny rekurzivní jazyky jsou kontextové.

LL1 (k) gramatika
Při syntaktické analýze shora-dolů bezkontextové gramatiky občas (skoro vždy) nemáme to štěstí a pro danou levou stranu pravidla existuje více pravých stran, čili jsme v situaci, kterou nejsme schopni deterministicky rozhodnout.
Tento nedeterminismus jsme ale často schopni odstranit pomocí nápovědy, kterou je pro nás následující, dosud nezpracovaný, terminál. Pomocí něj jsme schopni ve většině případů rozhodnout, které pravidlo se má použít, tak aby byl vstup korektně zpracován - aby terminál na vrcholu zásobníku vždy odpovídal zpracovávanému znaku vstupu.