Математическая теория формальных языков
Свойства класса детерминированных языков
Теорема 12.2.1.
Каждый автоматный язык является детерминированным контекстно-свободным языком.
Доказательство. Утверждение следует из теоремы 2.7.1.
Лемма 12.2.2.
Каждый детерминированный МП-автомат эквивалентен некоторому детерминированному МП-автомату , где для каждого перехода
выполняется неравенство .
Доказательство. Пусть дан детерминированный МП-автомат . Назовем избытком перехода
натуральное число . Докажем лемму индукцией по сумме избытков всех переходов.
Шаг индукции. Пусть существует переход
с положительным избытком. Рассмотрим четыре случая.
Случай 1. . Обозначим первый символ слова x0 через a0. Преобразуем МП-автомат M в эквивалентный ему детерминированный МП-автомат с меньшей суммой избытков всех переходов. Для этого добавим новое состояние r и переход . Каждый переход вида заменим на переход . К полученному таким образом детерминированному МП-автомату применимо предположение индукции.
Случай 2. . Обозначим первый символ слова
через C0. Преобразуем МП-автомат M в эквивалентный ему детерминированный МП-автомат с меньшей суммой избытков всех переходов. Для этого добавим новое состояние r и переход . Каждый переход вида заменим на переход . К полученному таким образом детерминированному МП-автомату применимо предположение индукции.
Случай 3. Существует переход . Тогда переходы
и
совместны. Противоречие.
Случай 4. Существуют переход
и переход , где
и . Тогда переходы
и
совместны. Противоречие.
Лемма 12.2.3.
Каждый детерминированный МП-автомат
эквивалентен некоторому детерминированному МП-автомату , где каждый переход
удовлетворяет условиям
и .
Доказательство. Сначала применим лемму 12.2.2, затем преобразуем МП-автомат так, чтобы для каждого перехода
выполнялось неравенство
(см. пример 10.2.4), и в заключение заменим каждый переход вида
на два последовательных перехода (см. пример 10.2.5).
Лемма 12.2.4.
Пусть ,
и язык
порождается некоторым детерминированным МП-автоматом. Тогда этот язык порождается также некоторым детерминированным МП-автоматом , где , ,
,
и каждый переход
удовлетворяет условиям
и .
Доказательство. Применив лемму 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. Является ли детерминированным контекстно-свободный язык ?
