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

         

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


Теорема 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. Является ли детерминированным контекстно-свободный язык ?

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