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

Определение 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^*.