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



         

Свойства класса детерминированных языков - часть 2


,

и каждый переход

удовлетворяет условиям

и .

Доказательство. Применив лемму 12.2.3, получим детерминированный МП-автомат . Построим искомый МП-автомат , положив , , , , , ,

Теорема 12.2.5.

Язык

является детерминированным контекстно-свободным языком тогда и только тогда, когда найдется такой детерминированный МП-автомат , что

Доказательство. Достаточность проверяется легко. Докажем необходимость. Рассмотрим МП-автомат

о котором говорится в лемме 12.2.4.

Для любых

и

введем обозначение

Очевидно, что

для любых ,

и .

Построим искомый МП-автомат , положив

(Напоминаем, что через

обозначается множество всех подмножеств множества Q2.)

Индукцией по количеству тактов работы можно доказать, что

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

и

для каждого .

Теорема 12.2.6.

Пусть L - детерминированный контекстно-свободный язык. Тогда язык L не является существенно неоднозначным.

Доказательство. Пусть дан детерминированный контекстно-свободный язык L. Рассмотрим МП-автомат

о котором говорится в лемме 12.2.4. Применив к этому МП-автомату конструкцию из доказательства теоремы 10.2.7, получим однозначную контекстно-свободную грамматику G, порождающую язык . Стирая в этой грамматике все вхождения символа , получим контекстно-свободную грамматику G', порождающую язык L.

Так как МП-автомат M не содержит переходов, ведущих из Q2

в Q1, а символ

встречается только на переходах, ведущих из Q1

в Q2, то в каждом G'-выводе однозначно определяется правило, которому в G соответствует правило, содержащее . Поэтому существует естественное однозначное соответствие между деревьями вывода в грамматике G' и деревьями вывода в грамматике G (при этом кроны соответствующих друг другу деревьев различаются только символом ). Следовательно, грамматика G' тоже является однозначной.

Теорема 12.2.7.

Дополнение каждого детерминированного контекстно-свободного языка является детерминированным контекстно-свободным языком.

Доказательство можно найти в [7, c. 110-116] или [2, c. 212-217].

Пример 12.2.8.

Язык

над алфавитом {a,b,c} не является детерминированным контекстно-свободным языком, так как его дополнение не является контекстно-свободным.

Теорема 12.2.9.

Неверно, что для любых детерминированных контекстно-свободных языков L1

и L2

язык

тоже является детерминированным контекстно-свободным языком.

Доказательство. Достаточно рассмотреть детерминированные контекстно-свободные языки L1

и L2

из доказательства теоремы 9.5.1.

Теорема 12.2.10.

Неверно, что для любых детерминированных контекстно-свободных языков L1

и L2

язык

тоже является детерминированным контекстно-свободным языком.

Доказательство. Утверждение следует из теорем 12.2.7 и 12.2.9 и закона де Моргана.

Упражнение 12.2.11. Является ли детерминированным контекстно-свободный язык ?




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