Hoofdstuk 6: Simplification of context-free
grammars and normal forms
1 Het idee
• Parsing and membership checking of CFL very inefficient.
• Can we restrict the form of a CFG without reducing the expressive power?
• E.g., we easily get rid of lambda productions
Oplossing: normaalvormen
2 Transformeren van grammatica’s
2.1 Substitution theorem
Stelling:
Stel G = (V,T,S,P) een CV grammatica. Stel dat er een productieregel van de vorm 𝐴 → 𝑥1 𝐵𝑥2 met
𝐴 ≠ 𝐵 en 𝐵 → 𝑦1 |𝑦2 | … |𝑦𝑛 is de verzameling van productieregels met B aan de linker kant. Stel G’ =
(V,T,S,P’) de grammatica in welk de verzameling productieregels werd geconstrueerd door 𝐴 →
𝑥1 𝐵𝑥2 te vervangen door 𝐴 → 𝑥1 𝑦1 𝑥2 |𝑥1 𝑦2 𝑥2 | … |𝑥1 𝑦𝑛 𝑥2. Dan geldt 𝐿(𝐺 ′ ) = 𝐿(𝐺).
Bewijs:
Voorbeeld:
1
, 3 Useful productions
Definitie nuttige variabele:
Stel G = (V,T,S,P) is een CV grammatica. Een variabele A wordt nuttig genoemd indien er ten minste
een 𝑤 ∈ 𝐿(𝐺) bestaat waarvoor geldt dat
∗ ∗
𝑆 ⇒ 𝑥𝐴𝑦⇒ 𝑤
Met 𝑥, 𝑦 ∈ (𝑉 ∪ 𝑇)∗ .
Met andere woorden de variabele komt voor in een derivation van w.
• A variable that is not useful is called useless.
• A production is useless if it involves a useless variable.
Voorbeeld:
3.1 Verwijderen van nutteloze productieregels
Stelling:
Stel G = (V,T,S,P) is een CV grammatica. Dan bestaat er een equivalente grammatica G’ = (V’,T’,S,P’)
die geen nutteloze variabelen of productieregels bevat.
Bewijs:
2
grammars and normal forms
1 Het idee
• Parsing and membership checking of CFL very inefficient.
• Can we restrict the form of a CFG without reducing the expressive power?
• E.g., we easily get rid of lambda productions
Oplossing: normaalvormen
2 Transformeren van grammatica’s
2.1 Substitution theorem
Stelling:
Stel G = (V,T,S,P) een CV grammatica. Stel dat er een productieregel van de vorm 𝐴 → 𝑥1 𝐵𝑥2 met
𝐴 ≠ 𝐵 en 𝐵 → 𝑦1 |𝑦2 | … |𝑦𝑛 is de verzameling van productieregels met B aan de linker kant. Stel G’ =
(V,T,S,P’) de grammatica in welk de verzameling productieregels werd geconstrueerd door 𝐴 →
𝑥1 𝐵𝑥2 te vervangen door 𝐴 → 𝑥1 𝑦1 𝑥2 |𝑥1 𝑦2 𝑥2 | … |𝑥1 𝑦𝑛 𝑥2. Dan geldt 𝐿(𝐺 ′ ) = 𝐿(𝐺).
Bewijs:
Voorbeeld:
1
, 3 Useful productions
Definitie nuttige variabele:
Stel G = (V,T,S,P) is een CV grammatica. Een variabele A wordt nuttig genoemd indien er ten minste
een 𝑤 ∈ 𝐿(𝐺) bestaat waarvoor geldt dat
∗ ∗
𝑆 ⇒ 𝑥𝐴𝑦⇒ 𝑤
Met 𝑥, 𝑦 ∈ (𝑉 ∪ 𝑇)∗ .
Met andere woorden de variabele komt voor in een derivation van w.
• A variable that is not useful is called useless.
• A production is useless if it involves a useless variable.
Voorbeeld:
3.1 Verwijderen van nutteloze productieregels
Stelling:
Stel G = (V,T,S,P) is een CV grammatica. Dan bestaat er een equivalente grammatica G’ = (V’,T’,S,P’)
die geen nutteloze variabelen of productieregels bevat.
Bewijs:
2
