Математическая теория формальных языков
Однозначные контекстно-свободные грамматики
Определение 7.2.1.
Вывод в контекстно-свободной грамматике называется левосторонним (левым, leftmost derivation), если на каждом шаге вывода заменяется самое левое из всех вхождений вспомогательных символов (то есть каждый шаг вывода имеет вид , где ,
и ). Иногда в левосторонних выводах вместо
пишут . Правосторонний (правый) вывод определяется аналогично. В правосторонних выводах вместо
пишут .
Пример 7.2.2.
Вывод
из примера 7.2.1 не является левосторонним.
Лемма 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.2.1 неоднозначна. Слово ababab имеет два левосторонних вывода:
и
Пример 7.2.8.
Пусть . Контекстно-свободная грамматика
порождает множество всех булевых формул, составленных из переменных p, p#, p##, ..., с помощью скобок и операторов ,
и . Эта грамматика является однозначной.
Определение 7.2.9.
Контекстно\df свободный язык называется существенно неоднозначным (inherently ambiguous), если каждая контекстно-свободная грамматика, порождающая этот язык, является неоднозначной.
Пример 7.2.10.
Язык, порождаемый контекстно-свободной грамматикой из примера 7.2.1, не является существенно неоднозначным. Он порождается однозначной грамматикой
Пример 7.2.11.
Пусть . Контекстно-свободный язык {akbmcn | k = m или m = n} является существенно неоднозначным. Доказательство этого факта можно найти в [АхоУль, с. 234-236].
Упражнение 7.2.12. Однозначна ли контекстно-свободная грамматика
с алфавитом ?
Упражнение 7.2.13. Однозначна ли контекстно-свободная грамматика
с алфавитом ?
Упражнение 7.2.14. Однозначна ли контекстно-свободная грамматика
с алфавитом ?
Упражнение 7.2.15. Однозначна ли контекстно-свободная грамматика
Упражнение 7.2.16.Найти однозначную контекстно-свободную грамматику, эквивалентную грамматике
Упражнение 7.2.17.Найти однозначную контекстно-свободную грамматику, эквивалентную грамматике
