IB102 – úkol 6, příklad 2 – řešení Odevzdání: 4. 11. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body] Nechť Σ = {a, b}. Napište algoritmus, který pro zadanou bezkontextovou
gramatiku G = (N, Σ, P, S) rozhodne, zda jazyk generovaný touto gramatikou obsahuje
alespoň 1 slovo ve tvaru xn
pro nějaké x ∈ Σ a n > 0.
Tedy algoritmus rozhodne, zda gramatika generuje alespoň jedno slovo délky alespoň
1 skládající se pouze z a-ček, nebo pouze z b-ček.
Popište princip fungování vašeho algoritmu a dokažte, že je tento algoritmus konvergentní
(vždy skončí).
Můžete využívat libovolné algoritmy z přednášky, musíte na to však upozornit v textu.
Pro řešení tohoto problému nejprve využijeme toho, že pro každou bezkontextovou
gramatiku G existuje jazykově ekvivalentní gramatika G, která je v Chomského normální
formě.
Algoritmus tedy bude probíhat ve 2 fázích:
1. Transformuj G na G = (N, Σ, P, S) takovou, že L(G) = L(G) a G je v Chomského
normální formě (algoritmus v 6. přednášce).
2. Rozhodni, zda G generuje slovo ve tvaru ak
nebo bk
pro nějaké k > 0.
Pro druhý bod nyní navrhneme algoritmus. Budeme tvořit množiny neterminálů Xa a
Xb, z nichž lze vygenerovat neprázdné slovo obsahující pouze písmena a, respektive pouze
písmena b, tedy:
Xa = {A ∈ N | A ⇒∗
ak
, k ∈ N, k > 0}
Xb = {A ∈ N | A ⇒∗
bk
, k ∈ N, k > 0}
Potom gramatika G splňuje požadavek ze zadání, jestliže se kořenový neterminál S
nachází alespoň v jedné z těchto množin, tedy pokud platí S ∈ Xa ∨ S ∈ Xb.
Jelikož G je jazykově ekvivalentní s G, tak i G splňuje požadavek ze zadání právě
tehdy, když jej splňuje G.
Množiny Xa, Xb budeme tvořit iterativně: budeme tvořit množiny Xi
a, respektive Xi
b,
které představují množiny neterminálů, které jsou kořeny derivačního stromu v G hloubky
nejvýše i+1, jehož listy jsou jenom terminály a, respektive b.
Začneme od neterminálů, které generují slovo a (respektive b) – to jsou množiny
X0
a, X0
b . Nyní budeme postupně tyto množiny rozšiřovat takto: máme-li Xi
a, pak Xi+1
a
získáme tak, že k Xi
a přidáme neterminály A pro něž existuje pravidlo ve tvaru A → CD,
kde C, D ∈ Xi
a, tedy takové, které dokážeme přepsat na neterminály z minulé iterace:
X0
a = {A ∈ N | A → a ∈ P}
Xi+1
a = Xi
a ∪ {A ∈ N | A → CD ∈ P, C ∈ Xi
a, D ∈ Xi
a}
X0
b = {A ∈ N | A → b ∈ P}
Xi+1
b = Xi
b ∪ {A ∈ N | A → CD ∈ P, C ∈ Xi
b, D ∈ Xi
b}
Tyto iterace budou pokračovat tak dlouho, dokud se množiny mění, tedy do té doby, než
nastane Xi
a = Xi+1
a , respektive Xj
b = Xj+1
b . Potom platí, že Xa = Xi
a, Xb = Xj
b .
1
IB102 – úkol 6, příklad 2 – řešení Odevzdání: 4. 11. 2013
Vypracoval(a): UČO:
Skupina:
Poznámka: Při sestavování množin X0
a (respektive X0
b ) stačí uvažovat pouze neterminály
C takové, že existuje pravidlo tvaru C → c, kde c je terminál (díky tomu, že
gramatika je v CNF). Navíc při rozšiřování množin Xi
a, Xi
b nemusíme uvažovat pravidla
jiného tvaru, než A → CD, opět proto, že gramatika je v CNF.
Algorithm 1 Algoritmus rozhodující, zda gramatika G generuje slovo ve tvaru xk
pro
nějaké x ∈ {a, b}, k ∈ N
Vstup: bezkontextová gramatika G = (N, {a, b}, P, S).
1: G ← G transformovaná do CNF
2: nechť G = (N, Σ, P, S)
3: i ← 0
4: ii ← 0
5: Xi
a ← {A ∈ N | A → a ∈ P}
6: repeat
7: ii ← i
8: i ← i + 1
9: Xi
a ← Xii
a
10: Přidáme všechny neterminály, které lze přepsat na dva neterminály z Xii
a
11: for all A → CD ∈ P do
12: if C ∈ Xii
a ∧ D ∈ Xii
a then
13: Xi
a ← Xi
a ∪ {A}
14: end if
15: end for
16: until Xii
a = Xi
a Dokud nedosáhneme toho, že se množina již dále nemění
17: Xa ← Xi
a
18:
19: j ← 0
20: jj ← 0
21: Xj
b ← {A ∈ N | A → b ∈ P}
22: repeat
23: jj ← j
24: j ← j + 1
25: Xj
b ← Xjj
b
26: for all A → CD ∈ P do
27: if C ∈ Xjj
b ∧ D ∈ Xjj
b then
28: Xj
b ← Xj
b ∪ {A}
29: end if
30: end for
31: until Xjj
b = Xj
b
32: Xb ← Xj
b
33:
34: return S ∈ Xa ∨ S ∈ Xb
2
IB102 – úkol 6, příklad 2 – řešení Odevzdání: 4. 11. 2013
Vypracoval(a): UČO:
Skupina:
Tento algoritmus je konvergentní (vždy skončí).
Důkaz. Konvergence algoritmu pro konverzi libovolné bezkontextové gramatiky do CNF
byla dokázána na přednášce.
Řádky 3 – 17 a řádky 19 – 32 jsou strukturálně stejné a navzájem na sobě nezávislé,
jen pro jiné vstupy, stačí tedy dokázat jeden případ, rozebereme tedy řádky 3 – 17.
• Cyklus for all na řádcích 11 – 14 iteruje přes konečnou množinu pravidel, tedy musí
jistě skončit.
• Cyklus repeat skončí proto, že
– vždy platí, že Xii
a ⊆ Xi
a, tedy velikost množin se nemůže zmenšovat a jednou
přidaný neterminál již nelze z množiny odstranit,
– pokud do množiny Xi
a není přidán v dané iteraci žádný neterminál (tedy Xi
a =
Xii
a ) pak cyklus skončí touto iterací,
– množina Xi
a nemůže růst nekonečně, může nastat nejvýše případ, že Xi
a = N,
tedy, že do množiny přidáme všechny neterminály.
Proto nutně musí ukončovací podmínka cyklu nastat po konečném počtu kroků.
Poznámka: Jistě by bylo možné tento příklad řešit i bez převodu gramatiky do CNF.
Algoritmus by vypadal v podstatě stejně, nicméně konstrukce množin Xa, Xb by musela
zohledňovat obecný tvar pravidel v bezkontextových gramatikách.
3