Однозначные контекстно-свободные грамматики

Определение 7.2.1. Вывод в контекстно-свободной грамматике называется левосторонним (левым, leftmost derivation), если на каждом шаге вывода заменяется самое левое из всех вхождений вспомогательных символов (то есть каждый шаг вывода имеет вид , где , и ). Иногда в левосторонних выводах вместо пишут \lmarrow. Правосторонний (правый) вывод определяется аналогично. В правосторонних выводах вместо пишут \rmarrow.

Пример 7.2.2. Вывод

из примера 7.1.2 не является левосторонним.

Лемма 7.2.3. Для каждого слова, выводимого в контекстно-свободной грамматике, существует левосторонний вывод.

Лемма 7.2.4. Пусть G - контекстно-свободная грамматика над алфавитом . Пусть . Тогда существует взаимно-однозначное соответствие между левосторонними выводами слова w в грамматике G и деревьями вывода в грамматике G, кроной которых является w.

Пример 7.2.5. Рассмотрим дерево вывода из примера 7.1.2. Ему соответствует левосторонний вывод

Определение 7.2.6. Контекстно-свободная грамматика называется неоднозначной (ambiguous), если существует слово, которое имеет два или более левосторонних вывода (устаревший термин - неопределенная грамматика). В противном случае контекстно-свободная грамматика называется однозначной (unambiguous).

Пример 7.2.7. Контекстно-свободная грамматика из примера 7.1.2 неоднозначна. Слово ababab имеет два левосторонних вывода:

и

Пример 7.2.8. Пусть . Контекстно-свободная грамматика

порождает множество всех булевых формул, составленных из переменных p, p#, p##,..., с помощью скобок и операторов , и . Эта грамматика является однозначной.

Определение 7.2.9. Контекстно-свободный язык называется существенно неоднозначным (inherently ambiguous), если каждая контекстно-свободная грамматика, порождающая этот язык, является неоднозначной.

Пример 7.2.10. Язык, порождаемый контекстно-свободной грамматикой из примера 7.1.2, не является существенно неоднозначным. Он порождается однозначной грамматикой

Пример 7.2.11. Пусть . Контекстно-свободный язык {a^kb^mcⁿ | k = m или m = n} является существенно неоднозначным. Доказательство этого факта можно найти в [АхоУль, с. 234-236].

7.3*. Однозначные праволинейные грамматики

Теорема 7.3.1. Каждый праволинейный язык порождается некоторой однозначной праволинейной грамматикой. Другими словами, ни один праволинейный язык не является существенно неоднозначным.

Доказательство. Согласно теоремам 2.4.3 и 2.7.1 исходный язык распознается некоторым детерминированным конечным автоматом. Применив к нему конструкцию из доказательства теоремы 2.4.1, получим однозначную праволинейную грамматику.

Замечание 7.3.2. Этот факт можно получить также из более общей теоремы 12.2.6 с учетом теоремы 12.2.1.

Упражнение 7.3.3. Найти однозначную праволинейную грамматику, порождающую язык a^*((a+b)(a+b))^*b^*.

Языки Дика и Лукасевича

Определение 7.4.1. Языком Дика (Dyck language) над 2n буквами называется контекстно-свободный язык над алфавитом {a₁,b₁,a₂,b₂,...,a_n,b_n}, порождаемый грамматикой

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

Теорема 7.4.3. Слово w над алфавитом {a,b} выводится в грамматике

тогда и только тогда, когда

и для всех слов выполняется неравенство

Теорема 7.4.4. При любом положительном целом n грамматика из определения 7.4.1 является однозначной.

Определение 7.4.5. Языком Лукасевича (Lukasiewicz language) над n + 1 буквами называется контекстно-свободный язык над алфавитом {a₀,a₁,...,a_n}, порождаемый грамматикой

Теорема 7.4.6. Слово w над алфавитом {a₀,a₁,...,a_n} принадлежит языку Лукасевича над n + 1 буквами тогда и только тогда, когда

и для всех слов , кроме x = w, выполняется неравенство

Теорема 7.4.7. При любом грамматика из определения 7.4.5 является однозначной.

Основная цель этой лекции - доказать, что каждая контекстно-свободная грамматика эквивалентна некоторой контекстно-свободной грамматике специального вида, а именно грамматике в нормальной форме Хомского (раздел 8.3). Этот факт используется дальше в доказательствах многих теорем о контекстно-свободных языках. Два вспомогательных результата, на которые опирается приведение грамматик к нормальной форме Хомского, выделены в отдельные разделы в начале лекции.

В конце лекции доказывается, что каждую контекстно-свободную грамматику можно также привести к нормальной форме Грейбах.