Formální jazyky a automaty
Jednoduchá pravidla a epsilon-pravidla, Chomského normální
forma, věta o vkládání pro bezkontextové jazyky
Jan Křetínský
Fakulta informatiky, MU Brno
Jaro 2024
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
2 / 18
ε-pravidla
Definice 3.13.
Řekneme, že CFG G = (N, Σ, P, S) je bez ε-pravidel právě když buď
1. P neobsahuje žádné ε-pravidlo (tj. pravidlo tvaru A → ε) nebo
2. v P existuje právě jedno ε-pravidlo S → ε a S se nevyskytuje na
pravé straně žádného pravidla z P.
Příklad
G = ({S, A, B}, {a, b, c}, P, S), kde P obsahuje pravidla
S → aAbBc
A → BB | a | ε
B → AcA | b
3 / 18
Algoritmus pro odstranění ε-pravidel
Vstup: CFG G = (N, Σ, P, S)
Výstup: CFG G′
= (N′
, Σ, P′
, S′
) bez ε-pravidel splňující L(G) = L(G′
)
1: Zkonstruuj Nε = {A ∈ N | A ⇒∗
ε}
2: Množinu pravidel P′
zkonstruuj takto:
3: for all A → X1 . . . Xn ∈ P, n > 0 do
4: přidej do P′
všechna pravidla tvaru A → α1 . . . αn splňující
5: (a) pokud Xi /∈ Nε pak αi = Xi
6: (b) pokud Xi ∈ Nε pak αi je buď Xi nebo ε
7: (c) ne všechna αi jsou ε
8: if S ∈ Nε then
9: přidej do P′
pravidla S′
→ S | ε
10: N′
:= N ∪ {S′
}
11: else
12: N′
:= N; S′
:= S
4 / 18
Algoritmus pro odstranění ε-pravidel
Vstup: CFG G = (N, Σ, P, S)
Výstup: CFG G′
= (N′
, Σ, P′
, S′
) bez ε-pravidel splňující L(G) = L(G′
)
1: Zkonstruuj Nε = {A ∈ N | A ⇒∗
ε}
2: Množinu pravidel P′
zkonstruuj takto:
3: for all A → X1 . . . Xn ∈ P, n > 0 do
4: přidej do P′
všechna pravidla tvaru A → α1 . . . αn splňující
5: (a) pokud Xi /∈ Nε pak αi = Xi
6: (b) pokud Xi ∈ Nε pak αi je buď Xi nebo ε
7: (c) ne všechna αi jsou ε
8: if S ∈ Nε then
9: přidej do P′
pravidla S′
→ S | ε
10: N′
:= N ∪ {S′
}
11: else
12: N′
:= N; S′
:= S
Korektnost algoritmu:
Konečnost
Výsledná gramatika je bez ε-pravidel
Ekvivalence gramatik
4 / 18
Příklad
G = ({S, A, B}, {a, b, c}, P, S), kde P obsahuje pravidla
S → aAbBc | AB
A → BB | a | ε
B → AA | b
5 / 18
Jednoduchá pravidla
Jednoduchým pravidlem nazýváme každé pravidlo tvaru A → B, kde
A, B ∈ N.
S → aAbBc
A → aA | B | a
B → bB | b
6 / 18
Algoritmus pro odstranění jednoduchých pravidel
Vstup: CFG G = (N, Σ, P, S) bez ε-pravidel
Výstup: CFG G′
= (N, Σ, P′
, S) bez jednoduchých a ε-pravidel, kde
L(G) = L(G′
)
1: for all A ∈ N do
2: i := 0; M0 := {A}
3: repeat
4: i := i + 1
5: Mi := Mi−1 ∪ {C | C → B ∈ P, B ∈ Mi−1}
6: until Mi = Mi−1
7: MA := Mi
8: P′
:= ∅
9: for all B → α ∈ P, které není jednoduché do
10: do P′
přidej A → α pro každé A ∈ MB , tj. A ⇒∗
G B
7 / 18
Příklad
G = ({S, A, B, C}, {a, b, c}, P, S), kde P obsahuje pravidla
S → ABC
A → aA | B | a
B → bB | A
C → cC | A
8 / 18
Korektnost algoritmu
Konečnost.
Výsledná gramatika neobsahuje jednoduchá pravidla ani ε-pravidla.
Ekvivalence gramatik:
L(G′
) ⊆ L(G) Nechť w ∈ L(G′
), pak existuje derivace
S = α0 ⇒G′ α1 ⇒G′ . . . ⇒G′ αn = w.
Pokud bylo při kroku αi ⇒G′ αi+1 použito pravidlo A → β, pak
A ∈ MB pro nějaké B ∈ N takové, že v G platí A ⇒∗
B a B → β.
Tedy v G platí A ⇒∗
β a αi ⇒∗
αi+1.
L(G) ⊆ L(G′
) Nechť w ∈ L(G), pak existuje levá derivace
S = α0 ⇒G α1 ⇒G . . . ⇒G αn = w.
Tu lze rozdělit na úseky tak, že v každém úseku se použila pouze
jednoduchá pravidla anebo žádné jednoduché pravidlo.
Úsek s jednoduchými pravidly lze vypustit (a ponechat pouze
jeho počáteční větnou formu).
9 / 18
Vlastní bezkontextová gramatika
Definice 3.17.
CFG G = (N, Σ, P, S) se nazývá necyklická, právě když neexistuje
A ∈ N takový, že A ⇒+
A.
G se nazývá vlastní, právě když je bez nepoužitelných symbolů, bez
ε-pravidel a necyklická.
Věta 3.18.
Ke každému neprázdnému bezkontextovému jazyku existuje vlastní
bezkontextová gramatika, která jej generuje.
Důkaz. Z bezkontextové gramatiky pro neprázdný jazyk odstraníme
ε-pravidla a jednoduchá pravidla. Odstraněním nepoužitelných
symbolů pak získáme vlastní gramatiku.
10 / 18
Chomského normální forma
Definice 3.19.
Bezkontextová gramatika G = (N, Σ, P, S) je v Chomského normální
formě (CNF), právě když G je bez ε-pravidel a každé pravidlo z P má
jeden z těchto tvarů:
1. A → BC, kde B, C ∈ N
2. A → a, kde a ∈ Σ
3. S → ε
Věta 3.21.
Každý bezkontextový jazyk lze generovat bezkontextovou gramatikou
v Chomského normální formě.
11 / 18
Příklad
G = ({S, A, B}, {a, b}, P, S), kde P obsahuje pravidla
S → AS | a
A → AB | AA | a
B → b
12 / 18
Algoritmus transformace do CNF
Algoritmus 3.6
Princip:
1. L = ∅
2. L ̸= ∅
Gramatiku pro L převedeme na vlastní a bez jednoduchých
pravidel.
X → ε
X → a
X → A
X → ab
X → aB
X → Ab
X → AB
...
X → aBcD
13 / 18
Lemma o vkládání pro bezkontextové jazyky
14 / 18
Lemma o vkládání pro bezkontextové jazyky
Věta 3.24.
Nechť L je CFL. Pak existují p, q ∈ N (závisející na L) taková, že
každé slovo z ∈ L delší než p lze psát ve tvaru z = uvwxy, kde
▶ alespoň jedno ze slov v, x je neprázdné (tj. vx ̸= ε),
▶ |vwx| ≤ q a
▶ uvi
wxi
y ∈ L pro každé i ∈ N0.
Poznámka 3.25. Tvrzení zůstává v platnosti i když namísto konstant
p, q budeme všude psát jen (jedinou) konstantu n.
14 / 18
Použití Lemmatu o vkládání pro bezkontextové jazyky
Lemma o vkládání je implikace P =⇒ Q, kde P je výrok, že L je CFL
a Q jsou uvedené vlastnosti.
Obměnu Lemmatu o vkládání ¬Q =⇒ ¬P lze použít k důkazu, že
nějaký jazyk L není CFL: stačí, když ukážeme platnost ¬Q.
¬Q:
1. Pro libovolnou konstantu n ∈ N
2. existuje slovo z ∈ L delší než n takové, že
3. pro všechny slova u, v, w, x, y splňující
z = uvwxy, vx ̸= ε a |vwx| ≤ n
4. existuje i ∈ N0 takové, že uvi
wxi
y ̸∈ L.
15 / 18
Příklad použití Lemmatu o vkládání
L = {ai
bi
ci
| i ≥ 1}
1. Pro libovolnou konstantu n ∈ N
2. existuje slovo z ∈ L delší než n takové, že
3. pro všechny slova u, v, w, x, y splňující
z = uvwxy, vx ̸= ε a |vwx| ≤ n
4. existuje i ∈ N0 takové, že uvi
wxi
y ̸∈ L.
=⇒ L není CFL.
16 / 18
Důkaz Lemmatu o vkládání pro bezkontextové jazyky
Nechť L je generován gramatikou v CNF.
hloubka stromu
def
= max. počet hran na cestě = max. počet
neterminálů na cestě
▶ Derivační strom hloubky k má max. 2k−1
listů =⇒ slovo délky
nejvýše 2k−1
.
▶ Derivační strom pro slovo delší než 2k−1
má hloubku alespoň
k + 1. Nejdelší cesta obsahuje alespoň k + 1 neterminálů.
17 / 18
Důkaz Lemmatu o vkládání pro bezkontextové jazyky
▶ Derivační strom pro slovo delší než 2k−1
má cestu délky alespoň
k + 1. Tato cesta obsahuje alespoň k + 1 neterminálů.
Označme k = |N| a položme p = 2k−1
, q = 2k
.
Nechť z ∈ L je slovo delší než p. Pak v libovolném derivačním stromu
slova z existuje cesta s alespoň k + 1 neterminály (vezměme tu
nejdelší).
S
A
A
u1
u2
u v w x y
u3
u1, u2 poslední opakování neterminálu na této cestě.
Tedy hloubka z u1 je nejvýše k + 1, a proto |vwx| ≤ 2k
. 18 / 18