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


         

и только тогда, когда найдется


,
и каждый переход
удовлетворяет условиям
и .
Доказательство. Применив лемму 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. Является ли детерминированным контекстно-свободный язык ?

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