Formální jazyky II

Note	Bezkontextové jazyky a jejich reprezentace. Varianty zásobníkových automatů (metody akceptování, determinismus a nedeterminismus, rozšířené zásobníkové automaty). Nedeterministická syntaktická analýza. Uzávěrové vlastnosti bezkontextových jazyků. IB102/IB005

Bezkontextové jazyky

Bezkontextové jazyky jsou generovány bezkontextovými gramatikami.

Bezkontextová gramatika (CFG)

Gramatika s pravidly tvaru $A \to α$ , kde $A$ je neterminál a $α$ je řetězec terminálů a neterminálů nenulové délky. Výjimkou je $S \to ε$ , pokud se počáteční neterminál $S$ nevyskytuje na pravé straně žádného pravidla.

Nenormovaný neterminál $X$

Nelze se z nich dostat na řetěz terminálů. Neexistuje derivace $X \Rightarrow^{*} w$ , pro nějaké $w \in Σ^{*}$ .

Nedosažitelné symbol $X$

Nelze se do něj dostat z $S$ . Neexistuje derivace $S \Rightarrow^{*} wX y$ pro nějaká $w, y \in Σ^{*}$ .

Nepoužitelný symbol $X$

Neexistuje derivace $S \Rightarrow^{*} wX y \Rightarrow^{*} w x y$ pro nějaká $w, x, y \in Σ^{*}$ .

Redukovaná CFG

Neobsahuje nenormované neterminály ani nedosažitelné symboly.

CFG $ε$ -pravidel

Neobsahuje žádné $ε$ -pravidlo, nebo obsahuje právě pravidlo $S \to ε$ a $S$ se nevyskytuje na pravé straně žádného pravidla.

Jednoduché pravidlo

$A \to B$ , kde $A, B \in N$ .

Necyklická gramatika

Neexistuje neterminál $A \in N$ , který by se po nenulovém počtu kroků přepsal sám na sebe $A \Rightarrow^{+} A$ .

Vlastní CFG

Je necyklická CFG bez nepoužitelných symbolů a bez $ε$ -pravidel. Ke každému CFL existuje vlastní CFG.

Chomského normální forma

CFG je v Chomského normální formě, právě když je bez $ε$ -pravidel a každé pravidlo je v jednom z tvarů:

$A \to BC$ , kde $B, C \in N$
$A \to a$ , kde $A \in N, a \in Σ$
$S \to ε$

Levorekurzivní neterminál

Neterminál $A$ je levorekurzivní, pokud existuje derivace $A \Rightarrow^{+} A β$ .

Greibachové normální forma

CFG je v Greibachové normální formě, právě když je bez $ε$ -pravidel a každé pravidlo je v jednom z tvarů:

$A \to a α$ , kde $a \in Σ, α \in N^{*}$
$S \to ε$

Zásobníkový automat (PDA)

Šestice $M = (Q, Σ, Γ, δ, q_{0}, Z_{0}, F)$ , kde

$Q$ je neprázdná konečná množina stavů,
$Σ$ je konečná vstupní abeceda,
$Γ$ je konečná zásobníková abeceda,
$δ : Q \times (Σ \cup {ε}) \times Γ \to P_{Fin} (Q \times Γ^{*})$ je parciální přechodová funkce,
$q_{0} \in Q$ je počáteční stav,
$Z_{0} \in Γ$ je počáteční symbol na zásobníku,
$F \subseteq Q$ je množina akceptujících stavů.

Note	$P_{F in} (Q \times Γ^{})$ značí množinu všech konečných podmnožin $Q \times Γ^{}$ .

Konfigurace: Stav PDA. $(p, ω, α) \in Q \times Σ^{*} \times Γ^{*}$ .
Krok výpočtu: $(p, aω, Z α) ∣ M —— (q, ω, γ α) ⟺ \exists (q, γ) \in δ (p, a, Z), kde a \in Σ \cup {ε}$

$∣ M —— *$ je tranzitivní uzávěr nad $∣ M ——$ .
Jazyk akceptovaný konvovým stavem: $L (M) = {w \in Σ^{*} : (q_{0}, w, Z_{0}) ∣ M —— * (q_{f}, ε, α), q_{f} \in F, α \in Γ^{*}}$
Jazyk akceptovaný prázdným zásobníkem: $L_{e} (M) = {w \in Σ * : (q_{0}, w, Z_{0}) ∣ M —— * (q, ε, ε), q \in Q}$

Deterministický zásobníkový automat (DPDA)

Zásobnikový automat $M = (Q, Σ, Γ, δ, q_{0}, Z_{0}, F)$ je deterministický, pokud platí:

Pro všechna $q \in Q$ a $Z \in Γ$ platí, že kdykoliv $δ (q, ε, Z) \neq = \emptyset$ , pak $δ (q, a, Z) = \emptyset$ pro všechna $a \in Σ$ .
- (Když má stav přechod pod $ε$ , pak tam není žádný jiný.)
Pro každé $q \in Q, Z \in Γ, a \in Σ \cup ε$ obsahuje $δ (q, a, Z)$ nejvýše jeden prvek.
- (Vždycky je maximálně jedna cesta, kam se dá při daném stavu a písmenech jít.)

Jazyk je deterministický bezkontextový, pokud existuje DPDA, který ho akceptuje koncovým stavem. Deterministické bezkontextové jazyky jsou podmnožinou bezkontextových jazyků.

Rozšířený zásobníkový automat

Šestice $R = (Q, Σ, Γ, δ, q_{0}, Z_{0}, F)$ lišící se od PDA jen v typu $δ$ :

$δ : Q \times (Σ \cup {ε}) \times Γ^{*} \to P_{Fin} (Q \times Γ^{*})$ je parciální přechodová funkce.

Note	Činí rozhodnutí ne na základě vrcholu zásobníku, ale na základě libovolné konečné horní části zásobníku.

Ke každému rozšířenému PDA existuje ekvivalentní PDA.

Krok výpočtu $∣ R ——$: $(p, a w, γ_{2} α) ∣ R —— (q, w, γ_{2} α) ⟺ \exists (q, γ_{2}) \in δ (p, a, γ_{1}), kde a \in Σ \cup {ε}$

Uzávěrové vlastnosti CFL

Operace	Formulka	Uzavřenost
Sjednocení	$L_{1} \cup L_{2}$	✓
Průnik s regulárním jazykem $L_{R}$	$L \cap L_{R}$	✓
Zřetězení	$L_{1} . L_{2}$	✓
Iterace (i pozitivní)	$L^{*}$ (i $L^{+}$ )	✓
Průnik	$L_{1} \cap L_{2}$
Doplněk	$\overline{L}$

Operace

Formulka

Uzavřenost

Sjednocení

$L_{1} \cup L_{2}$

✓

Průnik s regulárním jazykem $L_{R}$

$L \cap L_{R}$

✓

Zřetězení

$L_{1} . L_{2}$

✓

Iterace (i pozitivní)

$L^{*}$ (i $L^{+}$ )

✓

Průnik

$L_{1} \cap L_{2}$

Doplněk

$\overline{L}$

Uzávěrové vlastnosti DCFL

Operace	Formulka	Uzavřenost
Doplňek	$\overline{L}$	✓
Průnik s regulárním jazykem $L_{R}$	$L \cap L_{R}$	✓
Průnik	$L_{1} \cap L_{2}$
Sjednocení	$L_{1} \cup L_{2}$

Operace

Formulka

Uzavřenost

Doplňek

$\overline{L}$

✓

Průnik s regulárním jazykem $L_{R}$

$L \cap L_{R}$

✓

Průnik

$L_{1} \cap L_{2}$

Sjednocení

$L_{1} \cup L_{2}$

Pumping lemma pro bezkontextové jazyky

Nechť $L$ je bezkontextový jazyk. Pak existují $p, q \in N$ (závisející na $L$ ) taková, že každé slovo $z \in L, ∣ z ∣ > p$ lze psát ve tvaru $z = α . ψ . β . ω . γ$ , kde

$ψ . ω \neq = ε$ (alespoň jedno ze slov $ψ, ω$ je neprázdné),
$∣ α . β . γ ∣ \leq q$ a
$α . ψ^{i} . β . ω^{i} . γ \in L$ pro všechna $i \in N$ .

Nedeterministická syntaktická analýza

Generuje bezkontextová gramatika dané slovo?

Cílem syntaktické analýzy je vybudovat strom derivací (aplikací pravidel gramatiky), které se musely stát, aby analyzované slovo v gramatice vzniklo.

Shora dolů

Od počátečního neterminálu $S$ dolů přes levé derivace (rozvíjíme vždy nejlevější neterminál).

Mějme dvojici $(w, S)$ , kde $w$ je analyzované slovo.
Pokud prvky dvojice začínají stejným terminálem, odstraníme ho u obou $(a . x, a . α) ∣ —— a (x, α)$
Pokud druhý prvek začíná neterminálem, zkus ho rozvinout podle nějakého jeho pravidla.
Pokud prvky dvojice začínájí různými neterminály, tak tudy cesta nevede.
Pokud dvojice je $(ε, ε)$ , tak je slovo generováno danou gramatikou.

Zdola nahoru

Od analyzovaného slova $w$ až k počátečnímu neterminálu $S$ pomocí rozšířeného PDA.

Mějme trojici $(q, w, ⊥)$ , kde $q \in Q$ a $⊥ \in Γ$ je nově přidaný počáteční symbol na zásobníku.
Postupně načítám písmena zleva a přidávám je zprava do zásobníku (za $⊥$ , protože tady píšeme vrchol vlevo).
Když můžu, přepíšu symboly vpravo od $⊥$ na nějaký neterminál (v takovém případě čtu $ε$ ).
Snažím se vyprázdnit zásobník (dostat se do akceptujícího stavu a načíst celé slovo).

Algoritmus CYK (Cock-Younger-Kasami)

Deterministický algoritmus založený na analýze zdola nahoru, který má složitost $O (∣ w ∣^{3})$ .