Formální jazyky a automaty
Bezkontextové gramatiky, derivační stromy, redukované gramatiky
Jan Křetínský
Fakulta informatiky, MU Brno
Jaro 2024
Bezkontextové jazyky
Bezkontextová gramatika (Context-free grammar, CFG)
Bezkontextová gramatika G je čtveřice (N, Σ, P, S), kde
▶ N je neprázdná konečná množina neterminálních symbolů,
▶ Σ je konečná množina terminálních symbolů taková, že
N ∩ Σ = ∅ (značení: V = N ∪ Σ),
▶ S ∈ N je počáteční neterminál,
▶ P ⊆ N × V ∗
je konečná množina pravidel.
Jazyk je bezkontextový, pokud je generovaný nějakou bezkontextovou
gramatikou.
2 / 15
Příklad
G = ({E, T, F}, {+, ∗, (, ), i}, P, E), kde P obsahuje pravidla
E → E + T | T
T → T ∗ F | F
F → (E) | i
3 / 15
Derivační stromy pro bezkontextové gramatiky
Definice 3.1.
Nechť G = (N, Σ, P, S) je CFG.
Strom T nazveme derivačním stromem v G právě když
1. kořen má návěští S, vnitřní uzly mají návěští z N, listy mají
navěští z N ∪ Σ ∪ {ε},
2. má-li vnitřní uzel návěští A a jeho všichni synové n1, . . . , nk
mají v uspořádání zleva doprava návěští
X1, . . . , Xk ∈ N ∪ Σ ∪ {ε}, pak A → X1 . . . Xk ∈ P,
3. každý list s návěštím ε je jediným synem svého otce.
Výsledkem derivačního stromu T nazveme slovo vzniklé zřetězením
návěští listů v uspořádání zleva doprava.
4 / 15
Derivační stromy pro bezkontextové gramatiky
Definice 3.1.
Nechť G = (N, Σ, P, S) je CFG.
Strom T nazveme derivačním stromem v G právě když
1. kořen má návěští S, vnitřní uzly mají návěští z N, listy mají
navěští z N ∪ Σ ∪ {ε},
2. má-li vnitřní uzel návěští A a jeho všichni synové n1, . . . , nk
mají v uspořádání zleva doprava návěští
X1, . . . , Xk ∈ N ∪ Σ ∪ {ε}, pak A → X1 . . . Xk ∈ P,
3. každý list s návěštím ε je jediným synem svého otce.
Výsledkem derivačního stromu T nazveme slovo vzniklé zřetězením
návěští listů v uspořádání zleva doprava.
Věta 3.3. Vztah mezi derivačními stromy a relací ⇒∗
Nechť G = (N, Σ, P, S) je CFG. Pak pro libovolné α ∈ (N ∪ Σ)∗
platí
S ⇒∗
α právě když v G existuje derivační strom s výsledkem α.
Důkaz. Rozšířením na ∀A ∈ N + indukcí
4 / 15
Jednoznačnost derivačních stromů
Derivace
Derivace je sekvence S ⇒ α1 ⇒ α2 ⇒ . . . ⇒ αn.
Levá derivace je taková derivace, kde každé αi+1 vznikne z αi
přepsáním nejlevějšího neterminálu.
Každému derivačnímu stromu odpovídá jediná levá derivace.
Každé levé derivaci odpovídá jediný derivační strom.
Existuje pro každé w ∈ L(G) právě jeden derivační strom?
5 / 15
Jednoznačnost derivačních stromů
Derivace
Derivace je sekvence S ⇒ α1 ⇒ α2 ⇒ . . . ⇒ αn.
Levá derivace je taková derivace, kde každé αi+1 vznikne z αi
přepsáním nejlevějšího neterminálu.
Každému derivačnímu stromu odpovídá jediná levá derivace.
Každé levé derivaci odpovídá jediný derivační strom.
Existuje pro každé w ∈ L(G) právě jeden derivační strom?
Definice 3.5.
CFG G se nazývá víceznačná (nejednoznačná) právě když existuje
w ∈ L(G) mající alespoň dva různé derivační stromy.
V opačném případě říkáme, že G je jednoznačná.
Bezkontextový jazyk L se nazývá vnitřně (inherentně) víceznačný,
právě když každá bezkontextová gramatika, která jej generuje, je
víceznačná.
Příklad
5 / 15
Jednoznačnost derivačních stromů
Derivace
Derivace je sekvence S ⇒ α1 ⇒ α2 ⇒ . . . ⇒ αn.
Levá derivace je taková derivace, kde každé αi+1 vznikne z αi
přepsáním nejlevějšího neterminálu.
Každému derivačnímu stromu odpovídá jediná levá derivace.
Každé levé derivaci odpovídá jediný derivační strom.
Existuje pro každé w ∈ L(G) právě jeden derivační strom?
Definice 3.5.
CFG G se nazývá víceznačná (nejednoznačná) právě když existuje
w ∈ L(G) mající alespoň dva různé derivační stromy.
V opačném případě říkáme, že G je jednoznačná.
Bezkontextový jazyk L se nazývá vnitřně (inherentně) víceznačný,
právě když každá bezkontextová gramatika, která jej generuje, je
víceznačná.
Příklad
{w#vwR
v′
| v, v, w ∈ {0, 1}∗
}
5 / 15
Kanonické tvary bezkontextových gramatik
▶ redukované bezkontextové gramatiky
▶ gramatiky bez ε-pravidel
▶ gramatiky bez jednoduchých pravidel
▶ vlastní gramatiky
▶ Chomského normální forma
▶ gramatiky bez levé rekurze
▶ Greibachové normální forma
6 / 15
Redukované bezkontextové gramatiky
Definice 3.7.
Symbol X ∈ N ∪ Σ je nepoužitelný v CFG G = (N, Σ, P, S) právě když
v G neexistuje derivace tvaru
S ⇒∗
wXy ⇒∗
wxy
pro žádné w, x, y ∈ Σ∗
. Řekneme, že G je redukovaná, jestliže
neobsahuje žádné nepoužitelné symboly.
X je nepoužitelný typu I ⇐⇒ neexistuje w ∈ Σ∗
(tj. nenormovaný) splňující X ⇒∗
w
X je nepoužitelný typu II ⇐⇒ neexistují α, β ∈ (N ∪ Σ)∗
(tj. nedosažitelný) splňující S ⇒∗
αXβ
7 / 15
Nalezení nepoužitelných symbolů typu I
Nenormované neterminály: neexistuje w ∈ Σ∗
: A ⇒∗
w
Vstup: CFG G = (N, Σ, P, S)
Výstup: Ne = {A | ∃w ∈ Σ∗
. A ⇒∗
w} (normované neterminály)
1: i := 0; N0 := ∅
2: repeat
3: i := i + 1
4: Ni := Ni−1 ∪ {A | A → α ∈ P, α ∈ (Ni−1 ∪ Σ)∗
}
5: until Ni = Ni−1
6: Ne := Ni
8 / 15
Normované terminály: Korektnost algoritmu 1/2
Konečnost
9 / 15
Normované terminály: Korektnost algoritmu 1/2
Konečnost.
Správnost výsledku: Dokážeme A ∈ Ne ⇐⇒ ∃w ∈ Σ∗
. A ⇒∗
w.
(=⇒) Indukcí k i dokážeme A ∈ Ni =⇒ ∃w ∈ Σ∗
. A ⇒∗
w.
Základní krok i = 0: Platí triviálně, protože N0 = ∅.
Indukční krok: (IP) Tvrzení platí pro i. Dokážeme pro i + 1.
▶ A ∈ Ni . Tvrzení plyne z (IP).
▶ A ∈ Ni+1 ∖ Ni . Pak existuje A → X1 . . . Xk ∈ P,
kde každé Xj je terminál nebo neterminál patřící do Ni .
Podle (IP) existuje wj tak, že Xj ⇒∗
wj .
Tedy A ⇒ X1 . . . Xk ⇒∗
w1X2 . . . Xk ⇒∗
. . . ⇒∗
w1 . . . wk ,
kde w1 . . . wk ∈ Σ∗
.
9 / 15
Normované terminály: Korektnost algoritmu 2/2
(⇐=) Indukcí k n dokážeme
A
n
⇒ w, w ∈ Σ∗
=⇒ A ∈ Ni pro nějaké i.
Základní krok n = 1: A → w ∈ P okamžitě dává i = 1.
Indukční krok: (IP) Předpokládejme, že tvrzení platí pro všechna
n′
≤ n.
Nechť A
n+1
⇒ w. Pak A ⇒ X1 . . . Xk
n
⇒ w, kde Xj
nj
⇒ wj a nj ≤ n.
Pokud Xj ∈ N, pak podle (IP) Xj ∈ Nij
pro nějaké ij .
Pokud Xj ∈ Σ, klademe ij = 0.
Položme i = 1 + max{i1, . . . , ik }. Pak zřejmě A ∈ Ni .
10 / 15
Normovaná gramatika
Důsledek 3.10.
Existuje algoritmus, který pro libovolnou danou CFG G rozhoduje,
zda L(G) = ∅.
Důkaz.
Stačí ověřit, zda S ̸∈ Ne.
11 / 15
Normovaná gramatika
Důsledek 3.10.
Existuje algoritmus, který pro libovolnou danou CFG G rozhoduje,
zda L(G) = ∅.
Důkaz.
Stačí ověřit, zda S ̸∈ Ne.
Věta.
Nechť G = (N, Σ, P, S) je CFG taková, že L(G) ̸= ∅. Pak existuje
ekvivalentní CFG G′
bez nepoužitelných neterminálů typu I.
Důkaz.
Stačí spočítat množinu Ne a položit G′
= (Ne, Σ, P′
, S), kde
P′
= P ∩ Ne × (Ne ∪ Σ)∗
.
11 / 15
Nalezení nepoužitelných symbolů typu II
Nedosažitelné symboly: neexistují α, β ∈ (N ∪ Σ)∗
: S ⇒∗
αXβ
Vstup: CFG G = (N, Σ, P, S)
Výstup: CFG G′
= (N′
, Σ′
, P′
, S) bez nedosažitelných symbolů
splňující L(G) = L(G′
)
12 / 15
Nalezení nepoužitelných symbolů typu II
Nedosažitelné symboly: neexistují α, β ∈ (N ∪ Σ)∗
: S ⇒∗
αXβ
Vstup: CFG G = (N, Σ, P, S)
Výstup: CFG G′
= (N′
, Σ′
, P′
, S) bez nedosažitelných symbolů
splňující L(G) = L(G′
)
1: i := 0; V0 := {S}
2: repeat
3: i := i + 1
4: Vi := Vi−1 ∪ {X ∈ N ∪ Σ | ∃A ∈ Vi−1 . A → α′
Xβ′
∈ P}
5: until Vi = Vi−1
6: N′
:= N ∩ Vi ; Σ′
:= Σ ∩ Vi ; P′
:= P ∩ (Vi × V ∗
i )
12 / 15
Nalezení nepoužitelných symbolů typu II
Nedosažitelné symboly: neexistují α, β ∈ (N ∪ Σ)∗
: S ⇒∗
αXβ
Vstup: CFG G = (N, Σ, P, S)
Výstup: CFG G′
= (N′
, Σ′
, P′
, S) bez nedosažitelných symbolů
splňující L(G) = L(G′
)
1: i := 0; V0 := {S}
2: repeat
3: i := i + 1
4: Vi := Vi−1 ∪ {X ∈ N ∪ Σ | ∃A ∈ Vi−1 . A → α′
Xβ′
∈ P}
5: until Vi = Vi−1
6: N′
:= N ∩ Vi ; Σ′
:= Σ ∩ Vi ; P′
:= P ∩ (Vi × V ∗
i )
Idea korektnosti: X ∈ N′
∪ Σ′
⇐⇒ ∃α, β ∈ (N′
∪ Σ′
)∗
. S ⇒∗
αXβ
12 / 15
Příklad
G = ({S, A, B}, {a, b, c, d, e}, P, S), kde P obsahuje pravidla
S → aSb | c | aB
A → dA | d
B → eB
13 / 15
Eliminace nepoužitelných symbolů
Věta 3.11.
Každý neprázdný bezkontextový jazyk L je generován nějakou
redukovanou CFG.
Důkaz.
Nechť L je generován nějakou CFG G.
Krok 1. Z G odstraníme symboly typu I (výsledek označme G1).
Krok 2. Z G1 odstraníme symboly typu II (výsledek označme G2).
Platí L(G) = L(G1) = L(G2).
14 / 15
Korektnost: Dokážeme, že G2 je redukovaná CFG.
Nechť X je libovolný symbol z G2.
▶ v G2 existuje derivace S ⇒∗
G2
αXβ
▶ všechny symboly z G2 jsou též v G1
▶ pro nějaký terminální řetěz w platí S ⇒∗
G2
αXβ ⇒∗
G1
w
▶ žádný symbol z derivace αXβ ⇒∗
G1
w není krokem 2 eliminován
a proto αXβ ⇒∗
G2
w
Víme tedy, že existuje derivace S ⇒∗
G2
αXβ ⇒∗
G2
w, kde w je
terminální řetěz. Tudíž X není nepoužitelný v G2.
15 / 15
Korektnost: Dokážeme, že G2 je redukovaná CFG.
Nechť X je libovolný symbol z G2.
▶ v G2 existuje derivace S ⇒∗
G2
αXβ
▶ všechny symboly z G2 jsou též v G1
▶ pro nějaký terminální řetěz w platí S ⇒∗
G2
αXβ ⇒∗
G1
w
▶ žádný symbol z derivace αXβ ⇒∗
G1
w není krokem 2 eliminován
a proto αXβ ⇒∗
G2
w
Víme tedy, že existuje derivace S ⇒∗
G2
αXβ ⇒∗
G2
w, kde w je
terminální řetěz. Tudíž X není nepoužitelný v G2.
Příklad
S → AB | a
A → a
15 / 15