Redukované gramatiky
Následující studijní materiál se zabývá tzv. redukovanými gramatikami, neboli bezkontextovými
gramatikami bez nepoužitelných symbolů. Často se nám může stát, že budeme uvažovat
bezkontextovou gramatiku, kde je spousta informací redundantních, tj. takových, že neovlivní
výsledný jazyk generovaný gramatikou. Můžeme si podat následující příklad gramatiky, která
tuto redundanci obsahuje.
Příklad 1.
Je dána bezkontextová gramatika G = ({S, A, B, C}, {a, b}, P, S), kde množina pravidel
P = {S → aAb | bC
A → aAA
B → aB | bbB | b
C → bC | b
Všimněte si neterminálů A, B. Abychom mohli uplatnit pravidla pro neterminál A, tj. abychom
při derivaci použili tento symbol, musíme na začátku použít odvození S ⇒ aAb. Pro další
odvozování už můžeme aplikovat pouze pravidlo A → aAA. To znamená, že výsledkem derivace
S ⇒ aAb ⇒ aaAAb ⇒ . . . nikdy nebude slovo, čili řetězec pouze terminálních symbolů. Takový
neterminál je pro nás nadbytečný, nemusíme ho v gramatice mít, protože pomocí něj stejně nic
nevygenerujeme.
S neterminálem B je to podobné. Dokonce neexistuje derivace, která by začínala v počátečním
neterminálu S a „dosáhla neterminálu B. Díky tomu je pro nás neterminál B také
zbytečný a můžeme jej z gramatiky vypustit.
Pokud bychom tedy odstranili všechna A-pravidla, B-pravidla a pravidlo S → aAb, zbyde
nám pouze obyčejná regulární gramatika s pravidly
P = {S → bC
C → bC | b
generující jazyk L = {bi
| i > 1}. Co je však důležité, odstranění neterminálů A, B bylo
užitečné, neboť z původní složitější gramatiky zbyla jednodušší gramatika, u které si můžeme
lépe představit, co generuje.
Definice – nepoužitelný symbol
Buď G = (N, Σ, P, S) bezkontextová gramatika. Symbol X ∈ N ∪ Σ nazveme nepoužitelným,
právě když v G neexistuje derivace tvaru
S ⇒∗
wXy ⇒∗
wxy
pro žádné w, x, y ∈ Σ∗
.
Definice – redukovaná gramatika
Bezkontextová gramatika G = (N, Σ, P, S) se nazývá redukovaná, právě když neobsahuje
nepoužitelné symboly.
1
Poznámka.
Nepoužitelnost symbolů si můžeme rozdělit na dva typy:
1. Nepoužitelnost 1. typu (nenormovanost): neexistuje w ∈ Σ∗
takové, že A ⇒∗
w.
2. Nepoužitelnost 2. typu (nedosažitelnost): neexistují x, y ∈ (N ∪ Σ)∗
takové, že S ⇒∗
xAy.
V následujícím textu se budeme zabývat tím, že nepoužitelné symboly 1. a 2. typu odstranit, a
také, v jakém pořadí použít dané dva algoritmy tak, aby výsledná gramatika byla redukovaná.
Algoritmus (nalezení nepoužitelných symbolů 1. typu)
Následující algoritmus hledá takové neterminály A, pro něž existuje w ∈ Σ∗
tak, že A ⇒∗
w.
Takové neterminály přidává do množiny Ni. Poslední takovou množinu Ni, která už není rozdílná
od té předcházející Ni−1, přiřadí do výsledné množiny Ne obsahující pouze použitelné symboly
1. typu (tj. normované).
Vstup: CFG G = (N, Σ, P, S)
Výstup: Množina Ne = {A ∈ N | ∃w ∈ Σ∗
. A ⇒∗
w}.
i := 0; N0 := ∅
repeat i := i + 1
Ni := Ni−1 ∪ {A ∈ N | A → α ∈ P, α ∈ (Ni−1 ∪ Σ)∗
}
until Ni = Ni−1
Ne := Ni
Poznámka.
Algoritmus si ještě raději popíšeme slovně. Kroky probíhají v tomto pořadí:
1. Počáteční inicializace: Vytvoříme množinu N0, která nebude mít žádný prvek.
2. Konstruujeme množinu N1. Přidáme do ní pouze ty neterminály, z nichž můžeme přímo
odvodit terminální řetěz.
3. Konstruujeme množiny Ni, i ∈ {2, 3, . . . }. Do Ni nejdříve přidáme všechny neterminály
patřící do Ni−1. Poté uvažujeme ty neterminály A chybějící v množině Ni−1. Sledujeme
všechna A-pravidla a obsahuje-li některé z nich pouze řetězec terminálů či neterminálů
patřících do Ni−1, přidáme A do Ni.
4. Krok 3. opakujeme tak dlouho, dokud Ni obsahuje více prvků než Ni−1.
5. Položíme Ne = Ni.
Poznámka.
Výsledná gramatika neobsahující nepoužitelné symboly 1. typu se získá tak, že místo původní
množiny N uvažujeme pouze množinu Ne, přičemž z množiny pravidel P odstraníme všechny
pravé strany obsahující neterminály nepatřící do Ne, tj. ta pravidla obsahující nepoužitelné
symboly 1. typu.
2
Příklad 2.
Odstraňte nepoužitelné symboly 1. typu z gramatiky G = ({S, A, B, C, D, E, F}, {a, b, c}, P, S),
kde
P = {S → aA | bB
A → aAB | aa | AC | AE
B → bBA | bb | CB | BF
C → DE
D → cc | DD
E → FF | FE
F → EcE}
Řešení.
1. Nejdříve provedeme počáteční inicializaci množin Ni, tj. nastavíme N0 = ∅.
2. Do množiny N1 přidáme ty neterminály, které se dají přímo derivovat na terminální řetěz,
tedy symboly A (díky pravidlu A → aa), B (díky pravidlu B → bb) a D (díky pravidlu
D → cc). Platí tedy, že N1 = {A, B, D}.
3. Uvažujeme, co přidat do množiny N2 kromě neterminálů A, B, D, které do ní už automaticky
patří. Např. neterminál S obsahuje pravidlo S → aA – pravá strana se skládá z
terminálu a a neterminálu A ∈ N1. S můžeme do N2 přidat. Totéž ale neplatí pro zbylé
neterminály C, E, F. Množina N2 = {S, A, B, D}.
4. Uvažujme zbylé neterminály. Neterminálu C se týká jediné pravidlo C → DE, kde sice
D ∈ N2, avšak E ∈ N2. To znamená, že C nemůžeme přidat do N3. Sledujme dále
obě E-pravidla. Pravidlo E → FF nám nepomůže – vždyť F ∈ N2. Stejně tak pravidlo
E → FE, ani neterminál E nemůžeme přidat do N3. Posledním uvažovaným neterminálem
je F, který bohužel také nemůžeme zahrnout do N3, neboť pravidlo F → EcE obsahuje
neterminál E ∈ N2.
5. Jelikož N3 = N2, hledaná množina Ne = {S, A, B, D}.
Výsledná gramatika bez nepoužitelných symbolů 1. typu je následující: G = ({S, A, B, D}, {a, b, c}, P , S),
kde
P = {S → aA | bB
A → aAB | aa
B → bBA | bb
D → cc | DD}
3
Příklad 3.
Je dána bezkontextová gramatika G = ({S, A, B, C, D, E}, {a, b, c}, P, S), kde
P = {S → aAB | bBC | cE
A → aA | bD | cC
B → aBS | ab
C → DE
D → cB | DD
E → cEE}
Nalezněte ekvivalentní bezkontextovou gramatiku bez nepoužitelných symbolů 1. typu.
Poznámka.
Uvedený algoritmus se po mírném doplnění používá též ke zjištění toho faktu, zda daná gramatika
G generuje prázdný či neprázdný jazyk. Uvědomte si, že pokud startovní neterminál
S nepatří do množiny Ne, nelze z něj odvodit žádný terminální řetěz. To však znamená, že
L(G) = ∅. Pokud S ∈ Ne, tak je jazyk L(G) neprázdný.
Algoritmus (nalezení nepoužitelných symbolů 2. typu)
2. algoritmus, který probereme, odstraňuje tzv. nedosažitelné symboly, neboli takové symboly
A, které nelze odvodit z počátečního neterminálu S. Přesněji to znamená, že neexistují x, y ∈
(N ∪ Σ)∗
takové, že S ⇒∗
xAy.
Vstup: CFG G = (N, Σ, P, S)
Výstup: CFG G = (N , Σ , P , S) bez nepoužitelných symbolů 2. typu a splňující L(G) =
L(G ).
i := 0; V0 := {S}
repeat i := i + 1
Vi := Vi−1 ∪ {X ∈ N ∪ Σ | ∃A ∈ Vi−1. (A → αXβ ∈ P)}
until Vi = Vi−1
N := N ∩ Vi
Σ := Σ ∩ Vi
P := P ∩ (Vi × V ∗
i )
Poznámka.
Raději si předchozí algoritmus opět slovně popíšeme. Naznačíme si v jednotlivých krocích, jak
by měl „uživatel algoritmu postupovat.
1. Počáteční inicializace: Do množiny V0 vložíme pouze neterminál S.
2. Do množiny V1 přidáme S (tj. jediný prvek množiny V0) a dále všechny terminální i
neterminální symboly vyskytující se na pravé straně S-pravidel.
4
3. V dalších krocích konstruujeme množiny Vi, i ∈ {2, 3, . . . }. Provádíme to tím způsobem,
že vybíráme nové neterminály A, které ještě nebyly zahrnuty ve Vi−1. Do množiny Vi
vkládáme ty symboly (terminální či neterminální), které se vyskytují na pravé straně
všech A-pravidel a nejsou prvkem Vi−1.
4. Pokračujeme tak dlouho, dokud Vi je různé od Vi−1.
5. Posledním krokem je úprava původní gramatiky G. Do nové gramatiky G zahrneme pouze
ty terminály a neterminály patřící do Vi a samozřejmě odstraníme pravidla obsahující
symboly nepatřící do Vi, tj. nepoužitelné symboly 2. typu.
Příklad 4.
Je dána následující gramatika G = ({S, A, B, C, D}, {a, b, c}, P, S), kde
P = {S → aA | bB
A → aAB | aa
B → bBA | bb
C → cD | bCa
D → cc | DD}
Převeďte gramatiku G na ekvivalentní gramatiku G bez nepoužitelných symbolů 2. typu.
Řešení.
1. Opět nejdříve provedeme počáteční inicializaci množiny Vi, tj. položíme V0 = {S}.
2. Sledujeme všechna S-pravidla a do V1 přidáme symboly vyskytující jejich pravé straně.
Díky pravidlu S → aA přidáme a, A, díky pravidlu S → bB vložíme b, B. Množina V1 =
{S, A, B, a, b} – nesmíme zapomenout na S, které bylo v předchozí množině V0.
3. V množině V1 se nově objevily neterminály A, B. Pokud však projdeme všechna A-pravidla
a B-pravidla, tak nic nového do V2 nepřibývá, tudíž V2 = V1.
4. Nová gramatika G bude obsahovat pouze symboly množiny V2, proto z ní odstraníme
symboly C, D, c a všechna C-pravidla a D-pravidla.
Výsledkem bude G = ({S, A, B}, {a, b}, P , S), kde
P = {S → aA | bB
A → aAB | aa
B → bBA | bb}
Příklad 5.
Je dána následující gramatika G = ({S, A, B, C, D, E}, {a, b, c, d}, P, S), kde
P = {S → aBC
A → cAD | ccA
B → bBB | EE
C → Cd | CCa
D → AcD
E → ECd | aBC}
5
Převeďte gramatiku G na ekvivalentní gramatiku G bez nepoužitelných symbolů 2. typu.
Algoritmus (převod CFG na redukovanou gramatiku)
Poslední, 3. algoritmus je nejjednodušší a využívá předchozích dvou. Je však velmi důležité,
abyste zachovali správné pořadí použití obou algoritmů.
Vstup: CFG G = (N, Σ, P, S)
Výstup: Redukovaná gramatika G2 taková, že L(G) = L(G2).
1. Použijte 1. algoritmus pro odstranění nepoužitelných symbolů 1. typu – výsledkem je
gramatika G1 taková, že L(G1) = L(G).
2. Použijte 2. algoritmus pro odstranění nepoužitelných symbolů 2. typu – aplikujte jej na
gramatiku G1. Výsledkem je redukovaná gramatika G2 taková, že L(G2) = L(G1) = L(G).
Příklad 6.
K demonstraci faktu, že nelze měnit pořadí použití jednotlivých algoritmů, předkládáme následující
příklad gramatiky G = ({S, A, B}, {a, b}, P, S), kde množina pravidel
P = {S → a | A
A → AB
B → b}
Použijeme-li správné pořadí, tak nejdříve odstraňujeme nenormované symboly, tj. takové, které
se nedají odvodit na terminální řetěz. Postupně přidáváme do množiny Ne neterminály S, B.
Neterminál A, jeho pravidla i všechny pravé strany, kde se vyskytuje, musíme odstranit. Výsledkem
je gramatika
G1 = ({S, B}, {a, b}, {S → a, B → b}, S).
Aplikací 2. algoritmu odstraňujeme nedosažitelné symboly, tj. takové, které se nedají odvodit z
počátečního neterminálu S. Zjistíme, že ani neterminál B, ani terminál b není dosažitelný z S.
Zůstává nám tedy výsledná gramatika
G2 = ({S}, {a}, {S → a}, S).
Pokud bychom však použili opačné pořadí a začali 2. algoritmem, zjistíme postupně, že jsou
dosažitelné všechny symboly gramatiky G. Následnou aplikací 1. algoritmu na stejnou gramatiku
G odstraňujeme nenormované symboly, tj. takové, které nelze vyderivovat na terminální řetěz.
Je zřejmé, že neterminál A opět nezahrneme do výsledné gramatiky, avšak neterminál B ano,
což je chyba. Všimněte si, že následující derivací
S ⇒∗
A ⇒∗
AB ⇒∗
Ab ⇒∗
. . .
se k němu sice dostaneme, ale není nám to nic platné, protože z neterminálu A terminální řetězec
nedostaneme.
6
Příklad 7.
Je dána následující gramatika G = ({S, A, B, C, D, E}, {a, b, c, d}, P, S), kde
P = {S → acE | bSD | dB
A → abA | cdC
B → db | dB
C → caA | bdC | ab
D → bB
E → bdE | acDE}
Převeďte gramatiku G na ekvivalentní redukovanou gramatiku G .
Příklad 8.
Nechť G = (N, Σ, P, S) je bezkontextová gramatika. Řekneme, že
• neterminál X ∈ N je normovaný, pokud existuje w ∈ Σ∗
takové, že X ⇒∗
w.
• neterminál Y ∈ N je dosažitelný, pokud existují α, β ∈ (N ∪ Σ)∗
takové, že S ⇒∗
αY β.
Zkonstruujte bezkontextovou gramatiku obsahující neterminály A, B, C, D, pro které platí
• A je nedosažitelný a normovaný,
• B je dosažitelný a nenormovaný,
• C je nedosažitelný a nenormovaný,
• D je dosažitelný, normovaný a nepoužitelný.
Terminály volte libovolně. Gramatika může obsahovat i další neterminály.
7