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

         

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


Теорема 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. Найти для языка, порождаемого грамматикой

МП-автомат, в котором каждый переход

удовлетворяет требованиям ,

и .



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