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



         

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


Теорема 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.

Пусть ,

и язык

порождается некоторым детерминированным МП-автоматом. Тогда этот язык порождается также некоторым детерминированным МП-автоматом , где , ,




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