Нормальные формы контекстно-свободных грамматик
Теорема 8.2. Пусть дана контекстно-свободная грамма-
тика G = N,Σ,P,S и L(G) = ∅.Тогдасуществуюттакие
множества N
⊆ N и P
⊆ P , что в контекстно-свободной
грамматике N
, Σ,P
,S нет бесполезных символов и она эк-
вивалентна исходной грамматике.
Доказательство. Сначала удалим все непорождающие сим-
волы (удалим также каждое правило, содержащее хотя бы один
такой символ). Затем из полученной грамматики удалим все
недостижимые символы (и правила, их содержащие).
Пример 8.3. Рассмотрим контекстно-свободную граммати-
ку G справиламиS → UX, S → VZ, T → aa, T → bb, U → aU a,
U → bUb, V → aT b, V → bT a, W → YZY, W → aab, X → Xa,
X → Xb, X → ε, Y → YY, Y → aU , Y → ε, Z → W , Z → b.
Удалив четыре правила, содержащие непорождающий символ U ,
получим грамматику G
1
.ВнейсимволX является недостижи-
мым. Удалив три правила, содержащие X,получимграммати-
ку G
2
справиламиS → VZ, T → aa, T → bb, V → aT b,
V → bT a, W → YZY, W → aab, Y → YY, Y → ε, Z → W ,
Z → b.Очевидно,L(G)=L(G
2
) играмматикаG
2
не содержит
бесполезных символов.
8.2. Устранение ε-правил
[Гин, 1.8], [АхоУль, 2.4.2], [ХопМотУль, 7.1.3], [Лал, с. 295–296], [ГорМол,
с. 429–431], [Гла, 4.2], [Бра, с. 71–76], [ГроЛан, 7.2.6], [Сал, 6.2], [Sip, 2.1],
[Рей, с. 35–37], [КукБей, с. 288–289]
Теорема 8.4. Пусть язык L является контекстно-свобод-
ным. Тогда язык L −{ε} порождается некоторой контекст-
но-свободной грамматикой без ε-правил.
Доказательство. Пусть дана контекстно-свободная грамма-
тика G = N,Σ,P,S,порождающаяязыкL.Проведёмсерию
преобразований множества P .
Если для каких-то A ∈ N, B ∈ N, α ∈ (N ∪ Σ)
∗
и
β ∈ (N ∪Σ)
∗
множество P содержит правила B → αAβ и A → ε,
но не содержит правила B → αβ,тодобавимэтоправиловP .
Повторяем эту процедуру, пока возможно.
Теперь исключим из множества P все правила вида A → ε.
Полученная грамматика порождает язык L −{ε}.
36