Chomského normální forma
Posledním kanonickým tvarem, který probereme, je Chomského normální forma (zkráceně CNF).
Nejdříve si uvedeme definici.
Definice – Chomského normální forma
Řekněme, že bezkontextová gramatika G = (N, Σ, P, S) je v Chomského normální formě, právě
když všechna pravidla v P jsou následujícího tvaru:
1. A → a, a ∈ Σ
2. A → BC, B, C ∈ N
3. pokud ε ∈ L(G), pak S → ε ∈ P za podmínky, že se S nevyskytuje na pravé straně
žádného pravidla.
Poznámka.
Buď G = (N, Σ, P, S) bezkontextová gramatika v CNF. Derivační strom s výsledkem w ∈ L(G)
je speciální binární strom, pro jehož libovolný vnitřní uzel u platí:
1. má-li u právě dva následníky, pak se jedná o vnitřní uzly s návěštím z N.
2. má-li u právě jednoho následníka, pak je to list s návěštím ze Σ.
U takto definovaného derivačního stromu lze ukázat souvislost mezi max. délkou nějaké cesty
od kořene k listu a max. počtem všech listů. Této skutečnosti se podstatně využívá v důkazové
technice zvané Pumping lemma pro bezkontextové jazyky.
Příklad 1.
Buď dána bezkontextová gramatika G = ({S, A, B}, {a, b}, P, S), kde množina pravidel P = {
S → a | ba | AB
A → bA | Ba
B → b | BAB}
Chceme-li mít uvedenou gramatiku v Chomského normální formě, musíme ji upravit. Naznačíme
si postupně 3 možné „úpravy , které poté formalizujeme v algoritmu pro převod do CNF.
1. Některá pravidla ponecháme tak, jak jsou, protože odpovídají CNF. Jsou to
S → a | AB, B → b.
2. U pravidel A → α, |α| ≥ 2 obsahujících terminální symboly provedeme jejich „očárkování
, tj. libovolný terminál x ∈ Σ nahradíme za nový neterminál x a přidáme pravidlo
x → x. Takto si můžeme pomoci u pravidel S → ba, A → bA | Ba, která nahradíme
S → b a ,
A → b A | Ba ,
a → a,
b → b.
Je patrné, že nová pravidla již vyhovují CNF.
1
3. V předchozím případě jsme „očárkováním zajistili splnění CNF u pravidel, jejichž pravá
strana má délku právě 2. Co však pravidla A → β, kde délka řetězce β je více než 2? Toto
kritérium splňuje pravidlo B → BAB. I zde je však pomoc snadná. Místo B → BAB
zapíšeme B → BX a přidáme X → AB.
Tento postup navíc můžeme opakovat libovolně krát dlouho. Tedy: máme-li pravidlo
A → β1β2 . . . βn, pak jej postupně nahradíme pravidly:
A → β1X1,
X1 → β2X2,
X2 → β3X3,
. . .
Xn−2 → βn−1βn
Algoritmus (převod do Chomského normální formy)
Vstup: Bezkontextová gramatika G = (N, Σ, P, S) bez jednoduchých pravidel.
Výstup: Bezkontextová gramatika G = (N , Σ, P , S) v Chomského normální formě.
P := ∅
N := N
foreach pravidlo A → α do
1. je-li α = a nebo α = BC, kde a ∈ Σ, B, C ∈ N, pak P := P ∪ {A → α}.
(Tj. přidej do P pravidla, která splňují CNF.)
2. je-li |α| = |α1α2| = 2 a alespoň jeden symbol αi ∈ Σ, přidej do P pravidla
• A → α1α2, α1 → α1, je-li pouze α1 ∈ Σ;
N := N ∪ {α1}
• A → α1α2, α2 → α2, je-li pouze α2 ∈ Σ;
N := N ∪ {α2}
• A → α1α2, α1 → α1, α2 → α2, jsou-li oba α1, α2 ∈ Σ;
N := N ∪ {α1, α2}
3. Pokud α = α1α2 . . . αn, kde n > 2, pak do P přidej následující sadu pravidel:
A → β1X1,
X1 → β2X2,
X2 → β3X3,
. . . ,
Xn−2 → βn−1βn,
kde
• βi = αi, je-li αi ∈ N.
• βi = αi, je-li αi ∈ Σ. V tomto případě přidej do P pravidlo αi → αi a do množiny
neterminálů N doplň αi.
N := N ∪ {X1, . . . , Xn−2}
done
2
Poznámka.
Zmíněný algoritmus prochází všechna pravidla a u každého z nich provede jeden ze tří následujících
kroků:
1. ponechá pravidlo ve stávajícím tvaru, protože splňuje Chomského normální formu.
2. Má-li pravá strana pravidla pouze dva symboly a nesplňuje CNF, je zřejmé, že alespoň
jeden ze symbolů musí být terminál. V takovém případě očárkujeme terminály x na pravé
straně pravidla a přidáme x → x do P .
3. Má-li pravá strana pravidla A → α1 . . . αn více než dva symboly, pak ji nahrazujeme
řetězcem α1X1, kde X1 je nový neterminál. Je-li navíc symbol α1 ∈ Σ, pak jej očárkujeme
a do P přidáme α1 → α1.
Za neterminál X1 jsme „ukryli zbylou část řetězce α2α3 . . . αn. Jakým způsobem přidáme
pravidla generující zmíněný řetězec tak, aby byla v CNF? Provedeme stejný krok jako
v případě A-pravidla. Přidáme X1 → α2X2, je-li α2 ∈ Σ, „očárkujeme α2 a do P vložíme
α2 → α2. A takto pokračujeme, dokud se pod Xi neskrývají pouze dva symboly...
Příklad 2.
Je dána bezkontextová gramatika G = ({S, A, B}, {a, b}, P, S) s pravidly P = {
S → SaSbS | aAa | bBb
A → aA | aaa
B → Bb | bb | b}
Převeďte gramatiku G do Chomského normální formy.
Řešení.
• S → SaSbS nahradíme (dle kroku 3.) postupně pravidly S → SS1, S1 → a S2, S2 →
SS3, S3 → b S a přidáme ještě a → a, b → b.
• S → aAa nahradíme (dle kroku 3.) pravidly S → a S4, S4 → Aa .
• S → bBb nahradíme (dle kroku 3.) pravidly S → b S5, S5 → Bb .
• A → aA nahradíme (dle kroku 2.) pravidlem A → a A.
• A → aaa nahradíme (dle kroku 3.) pravidly A → a A1, A1 → a a .
• B → Bb nahradíme (dle kroku 2.) pravidlem B → Bb .
• B → bb nahradíme (dle kroku 2.) pravidlem B → b b .
• B → b ponecháme (dle kroku 1.) beze změny.
3
Výsledná gramatika G = ({S, A, B, S1, S2, S3, S4, S5, A1, a , b }, {a, b}, P , S) s pravidly P = {
S → SS1 | a S4 | bS5
A → a A | a A1
B → Bb | b b | b
S1 → a S2
S2 → SS3
S3 → b S
S4 → Aa
S5 → Bb
A1 → a a
a → a
b → b}
je v Chomského normální formě.
Příklad 3.
Buď dána bezkontextová gramatika G = ({S, A, B, C}, {a, b, c}, P, S) s pravidly P = {
S → ABc | ε
A → AbAa | BC,
B → bB | CAa | b
C → cCaA | abc}
Převeďte gramatiku G do Chomského normální formy.
4