Характеризация контекстно-свободных языков

Теорема 10.2.1. Если язык L является контекстно-свободным, то существует МП-автомат, распознающий этот язык.

Доказательство. Пусть язык L порождается контекстно-свободной грамматикой , в которой каждое правило имеет вид , где , и (в силу теоремы 8.8.3 такая грамматика существует). Положим , , , и

Можно доказать, что тогда и только тогда, когда существует левосторонний вывод (здесь и ).

Пример 10.2.2. Пусть . Контекстно-свободная грамматика

и МП-автомат , где

задают один и тот же язык.

Лемма 10.2.3. Каждый МП-автомат эквивалентен некоторому МП-автомату , где |I| = 1, |F| = 1 и каждый переход удовлетворяет требованиям и .

Пример 10.2.4. Рассмотрим МП-автомат , где , , ,

Он эквивалентен МП-автомату , где и

Пример 10.2.5. Рассмотрим МП-автомат , где , , ,

Он эквивалентен МП-автомату , где , и

Пример 10.2.6. Рассмотрим МП-автомат , где , , ,

Он эквивалентен МП-автомату , где , , , ,

Теорема 10.2.7. Если язык L распознается некоторым МП-автоматом, то L является контекстно-свободным.

Доказательство. Пусть язык L распознается МП-автоматом . Без ограничения общности можно считать, что , и каждый переход удовлетворяет требованию . Построим искомую контекстно-свободную грамматику , положив , и

Можно доказать, что тогда и только тогда, когда (здесь ).

Пример 10.2.8. МП-автомат , где , ,

и контекстно-свободная грамматика

задают один и тот же язык. Здесь S, T и U соответствуют символам A_1,2, A_1,1 и A_2,2 из доказательства теоремы 10.2.7.

Упражнение 10.2.9. Найти МП-автомат, распознающий язык, порождаемый грамматикой

Упражнение 10.2.10. Найти контекстно-свободную грамматику, порождающую язык

10.3*. Автоматы с магазинной памятью с однобуквенными переходами

Теорема 10.3.1. Каждый МП-автомат эквивалентен некоторому МП-автомату , где |Q| = 2 и каждый переход удовлетворяет требованиям |x| = 1, и .

Доказательство. Пусть исходным МП-автоматом распознается контекстно-свободный язык . Согласно теореме 8.4.6 язык порождается некоторой контекстно-свободной грамматикой , в которой каждое правило имеет вид , где , , и . Аналогично тому, как было сделано при доказательстве теоремы 10.2.1, положим , Q = {1,2}, I = {1},

Теорема 10.3.2. Каждый МП-автомат эквивалентен некоторому МП-автомату , в котором каждый переход удовлетворяет требованиям |x| = 1, и .

Доказательство. Пусть исходным МП-автоматом распознается контекстно-вободный язык . Согласно теореме 8.4.6 язык порождается некоторой контекстно-вободной грамматикой , в которой каждое правило имеет один из следующих трех видов: , , , где , , , . Легко добиться того, чтобы в правилах грамматики G вспомогательные символы в правой части (то есть символы B и C) были отличны от начального символа S.

Положим , где . Далее, положим ,

Упражнение 10.3.3. Найти для языка, порождаемого грамматикой

МП-автомат, в котором каждый переход удовлетворяет требованиям |x| = 1, и .

Упражнение 10.3.4. Найти для языка, порождаемого грамматикой

МП-автомат, в котором каждый переход удовлетворяет требованиям , и .

В этой лекции излагаются те свойства контекстно-свободных языков, которые удобно доказывать с привлечением автоматов с магазинной памятью. В первых двух разделах приводятся некоторые свойства замкнутости класса контекстно-свободных языков (замкнутость относительно деления, взятия гомоморфного образа и полного гомоморфного прообраза). В конце лекции формулируются два критерия контекстной свободности, интересных в основном с теоретической точки зрения.

11.1*. Деление контекстно-свободных языков

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

Доказательство. Пусть - МП-автомат, распознающий язык L₁. Без ограничения общности можно считать, что для каждого перехода выполняется неравенство .