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

         

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


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



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