Математическая теория формальных языков
Нормальная форма Грейбах
Определение 8.4.1.
Грамматика в нормальной форме Грейбах (grammar in Greibach normal form) - контекстно-свободная грамматика , в которой каждое правило имеет один из следующих четырех видов: , , , , где , , , .
Пример 8.4.2.
Грамматика
является грамматикой в нормальной форме Грейбах.
Замечание 8.4.3.
Некоторые авторы разрешают в грамматиках в нормальной форме Грейбах использовать также правила вида , где , ,
(в определении 8.4.1 разрешены, только если ).
Теорема 8.4.4.
Каждая контекстно-свободная грамматика эквивалентна некоторой грамматике в нормальной форме Грейбах.
Доказательство. Докажем теорему для контекстно-свободных языков, не содержащих пустого слова. Согласно теореме 8.3.5 исходный язык порождается некоторой грамматикой , в которой каждое правило имеет вид
или , где , , , .
Введем |N|2
новых вспомогательных символов, соответствующих упорядоченным парам из множества . Новый символ, соответствующий паре , будем обозначать (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. Найти контекстно-свободную грамматику в нормальной форме Грейбах, эквивалентную грамматике
