Устранение бесполезных символов

Определение 8.1.1. Пусть дана порождающая грамматика . Символ называется полезным (useful), если существуют такие слова , и , что и . Символ называется бесполезным (useless), если он не является полезным. Символ называется порождающим (generating), если существует такое слово , что . Символ называется достижимым если существуют такие слова и , что .

Лемма 8.1.2. Пусть дана контекстно-свободная грамматика , в которой все символы из N являются порождающими. Пусть N' - множество всех достижимых символов грамматики G, а P' - множество тех правил из P, которые не содержат ни одного символа из множества . Тогда в контекстно-свободной грамматике все символы из N' являются порождающими. \end{ lemma }

Теорема 8.1.3. Пусть дана контекстно-свободная грамматика и . Тогда существуют такие множества и , что в контекстно-свободной грамматике нет бесполезных символов и она эквивалентна исходной грамматике.

Доказательство. На первом этапе удалим все непорождающие символы (удалим также каждое правило, содержащее хотя бы один такой символ). На втором этапе из полученной грамматики удалим все недостижимые символы (и правила, их содержащие). Согласно 8.1.2 на втором этапе ни один порождающий символ не может стать непорождающим.

Пример 8.1.4. Рассмотрим контекстно-свободную грамматику G с правилами

Удалив четыре правила, содержащие непорождающий символ U, получим грамматику G₁. В ней символ X является недостижимым. Удалив три правила, содержащие X, получим грамматику G₂ с правилами

Очевидно, что L(G) = L(G₂) и грамматика G₂ не содержит бесполезных символов.

Упражнение 8.1.5. Найти контекстно-свободную грамматику без бесполезных символов, эквивалентную грамматике

Устранение эпсилон-правил

Теорема 8.2.1. Пусть язык является контекстно-свободным. Тогда язык порождается некоторой контекстно-свободной грамматикой без - правил.

Доказательство. Пусть дана контекстно-свободная грамматика , порождающая язык L. Проведем серию преобразований множества P.

Если для каких-то , , и множество P содержит правила и , но не содержит правила , то добавим это правило в P. Повторяем эту процедуру, пока возможно.

Теперь исключим из множества P все правила вида . Полученная грамматика порождает язык .

Пример 8.2.2. Рассмотрим язык L, порождаемый грамматикой

Язык порождается грамматикой

Нормальная форма Хомского

Определение 8.3.1. Грамматика в нормальной форме Хомского (грамматика в бинарной нормальной форме, квадратичная грамматика, grammar in Chomsky normal form) - контекстно-свободная грамматика , в которой каждое правило имеет один из следующих трех видов: , , , где , , , .

Пример 8.3.2. Грамматика

является грамматикой в нормальной форме Хомского.

Теорема 8.3.3. Каждая контекстно-свободная грамматика эквивалентна некоторой грамматике в нормальной форме Хомского.

Доказательство. Пусть дана контекстно-свободная грамматика . Проведем ряд преобразований этой грамматики так, что порождаемый ею язык остается неизменным.

Если правая часть какого-нибудь правила содержит символ S, то заменим грамматику на грамматику

где S₀ - новый символ, не принадлежащий множеству .

Заменим во всех правилах каждый терминальный символ a на новый нетерминальный символ T_a и добавим к множеству P правила для всех .

Устраним правила вида , где , заменив каждое из них на ряд более коротких правил (при этом добавляются новые нетерминальные символы).

Теперь устраним все правила вида , где A не является начальным символом. Это можно сделать так же, как в доказательстве теоремы 8.2.1.

Если для каких-то , и множество P содержит правила и , но не содержит правила , то добавим это правило в P. Повторяем эту процедуру, пока возможно. После этого исключим из множества P все правила вида .

Пример 8.3.4. Грамматика

эквивалентна следующей грамматике в нормальной форме Хомского:

Теорема 8.3.5. Если контекстно-свободный язык не содержит пустого слова, то он порождается некоторой грамматикой, в которой каждое правило имеет один из следующих двух видов: , , где , , , .

 

8.4*. Нормальная форма Грейбах

Определение 8.4.1. Грамматика в нормальной форме Грейбах (grammar in Greibach normal form) - контекстно-свободная грамматика , в которой каждое правило имеет один из следующих четырех видов: , , , , где , , , .

Пример 8.4.2. Грамматика

является грамматикой в нормальной форме Грейбах.

Замечание 8.4.3. Некоторые авторы разрешают в грамматиках в нормальной форме Грейбах использовать также правила вида , где , , (в определении 8.4.1 разрешены, только если ).

Теорема 8.4.4. Каждая контекстно-свободная грамматика эквивалентна некоторой грамматике в нормальной форме Грейбах.

Доказательство. Докажем теорему для контекстно-свободных языков, не содержащих пустого слова. Согласно теореме 8.3.5 исходный язык порождается некоторой грамматикой , в которой каждое правило имеет вид или , где , , , .

Введем |N|² новых вспомогательных символов, соответствующих упорядоченным парам из множества . Новый символ, соответствующий паре , будем обозначать (A\B). Построим грамматику "почти в нормальной форме Грейбах" , положив и

Если в этой грамматике заменить

на

получим эквивалентную ей грамматику в нормальной форме Грейбах. Осталось лишь доказать, что .

Сначала проверим индукцией по длине слова , что если , то для любого . Чтобы провести шаг индукции, допустим, что и

где и . По предположению индукции имеем и . Подключая эти выводы к правилу и используя , получаем искомый вывод .

Докажем теперь, что для любого равносильны утверждения и . В одну сторону это следует из только что доказанного. Доказательство того, что если , то , проведем индукцией по длине слова . Чтобы провести шаг индукции, допустим, что , , , и . По предположению индукции и . Получаем искомый вывод

 

Теперь убедимся, что . Рассмотрим произвольное слово , где и для всех . Пусть

где для всех . Тогда

Обратно, пусть

где для всех . Тогда

Пример 8.4.5. Грамматика

эквивалентна следующей грамматике в нормальной форме Грейбах:

Здесь C, D, E и F соответствуют символам (A\S), (A\T), (V\T) и (U\T) из доказательства теоремы 8.4.4 (удален 21 бесполезный символ).

Теорема 8.4.6. Пусть язык L контекстно-свободный. Тогда язык порождается некоторой грамматикой в нормальной форме Грейбах без - правил.

Пример 8.4.7. Грамматика

эквивалентна следующей грамматике в нормальной форме Грейбах без -правил:

Упражнение 8.4.8. Найти контекстно-свободную грамматику в нормальной форме Грейбах, эквивалентную грамматике

Упражнение 8.4.9. Найти контекстно-свободную грамматику в нормальной форме Грейбах, эквивалентную грамматике

Упражнение 8.4.10. Найти контекстно-свободную грамматику в нормальной форме Грейбах, эквивалентную грамматике

Упражнение 8.4.11. Найти контекстно-свободную грамматику в нормальной форме Грейбах, эквивалентную грамматике

В "лекции 2" были доказаны лемма о разрастании и свойства замкнутости класса автоматных языков. Некоторые из этих теорем имеют аналоги для класса контекстно-свободных языков (разделы 9.1 и 9.4), но этот класс не замкнут относительно дополнения и пересечения (раздел 9.5).

Лемма о разрастании для контекстно-свободных языков формализует явление "периодичности" в этих языках. Для полноты картины в разделах 9.2* и 9.3 приведены некоторые аналогичные теоремы для класса линейных языков, хотя ни в теории, ни в практических приложениях класс линейных языков значительной роли не играет.

В разделе 9.6 доказывается, что пересечение контекстно-свободного языка с автоматным языком является контекстно-свободным. В сочетании с леммой о разрастании этот факт дает удобное средство, позволяющее во многих задачах доказать, что заданный язык не является контекстно-свободным. Еще одно необходимое условие контекстной свободности сформулировано в разделе 9.7*.