Математическая теория формальных языков

       

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


Определение 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. Найти контекстно-свободную грамматику в нормальной форме Грейбах, эквивалентную грамматике



Содержание раздела