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

Теорема 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 соответствуют символам A1,2, A1,1

и A2,2

из доказательства теоремы 10.2.7.

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

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