Здесь записи дуг используют в качестве разделителя вершин "дробь", в числителе которой пометка, а в знаменателе след дуги.

C2 есть открывающий и читающий цикл, но не моном.

Алгоритм 1. Проверка праволинейности.

Вход. Детерминированный магазинный автомат M.

Выход. Если M праволинеен, то ответ "L(M) регулярен", иначе "M имеет накапливающий цикл, который не есть моном".

Метод. Если каждый открывающий цикл любого маршрута из Core(M, 3, 3) есть моном, то ответить "L(M) регулярен", иначе ответить "M имеет накапливающий цикл, который не есть моном".

Из конечности множества Core(M, 3,3) и теоремы 2 следует, что алгоритм заканчивает работу и дает правильный ответ.

1.2. Согласующие и псевдосогласующие Эграфы. Охарактеризуем еще одно средство задания регулярных языков - магазинные автоматы без самовставления. Они определены в [Вылиток 98] и включают праволинейные магазинные автоматы как собственный подкласс. Сформулируем нашу версию определения магазинного автомата без самовставления, проводя параллель с понятием псевдосогласующего КСвыражения.

Пусть какоелибо предложение Dграфа D содержит гнездо, образованное парными циклами, каждый из которых имеет непустую пометку. Тогда назовем D согласующим Вграфом . В противном случае будем называть Dграф псевдосогласующим.

Пусть граф магазинного автомата M является псевдосогласующим D графом. Тогда назовем M магазинным автоматом без самовставления.

Вопрос принадлежности магазинного автомата данному классу разрешается с помощью (4,4)ядра. Действительно, применяя прием, используемый в доказательстве теоремы 2, можно убедиться, что предложение

ТГТ1ГТЛ ГТЛ ГТЛГТЛГТЛ

lnlT2n2T3T4T5n3T6n4T7,

в котором пометки дуг п2 и п3 непусты, а участки

П1Т2П2Т3 и Т57ГзТ67Г4

являются парными циклами, редуцируется до (4,4) канона

ТУ гтл! гтл! гтл! гтл! гтл! гтл!

с парными циклами

niT2n2T3и т5п316п4-

Увеличение параметров ядра по сравнению с детерминированным случаем обусловлено тем, что для недетерминированных магазинных автоматов нет возмож ности опереться на непустоту пометки открывающего цикла (ср. использование леммы 1 в доказательстве теоремы 2).

1.3. Некоторые неясности одной работы о проверке регулярности детерминированного языка. Некоторые детали работы [Stearns 67] перекликаются

с особенностями нашего подхода. Однако попытка разобраться в ней наталкивается на некоторые трудности. Они начинаются уже с определений. Одним из важнейших в работе является понятие квазипустого слова. Его определение вряд ли подразумевает, что каждое ленточное слово, стираемое едвижениями (этот и некоторые другие употребленные далее термины см. в [Stearns 67]), считается квазипустым. Действительно, рассмотрим пример магазинного автомата, определяемого дугами (po,Zo) +Z (po,Z

(po,Z) +Z (Ръг

(pi,Z) -Z (p2,Z), (P2,Z) -Z (f,Zo).

Единственное предложение автомата имеет пустую пометку. еДвижение

(pi,z) т (Л)(Р2, л)

не приводит автомат в состояние, в котором он остался бы при стирании копии слова Z. Следовательно, слово Z не удовлетворяет определению квазипустого слова.

(Взяв нужное число состояний, пример можно изменить так, что длина успеш -ного пути увеличится.)

Можно предположить, что автор хотел назвать квазипустыми слова, стирае -мые циклами с пустой пометкой (более того, такими циклами с пустой пометкой, которые имеют парный себе накапливающий цикл). Но тогда становится неясной теорема 3 работы [Stearns 67]. В самом деле, рассмотрим пример детерминиро -ванного магазинного автомата

Ми = ({po,pi,p2>, {a, Ь}, {Z0,...,Zn},Z0,$,P0, {Р2}),

допускающего (весьма нерационально) регулярный язык {amb m > 1}:

1)(po, Л, Zi) - (po, ZiZi+i), 0 < i < n - 1,

2)(po, a, Zn) - (po, ZnZi),

3)(po, Ь, Zn) - (pi, Л),

4)(pi, Л,Zi) - (pi, Л), 1 < i < n,

5)(pi, Zo) - (p2,Zo).

Команды 1, 2 соответственно каждому прочитанному a записывают в магазин цепочку

Z2 • • • ZnZi-

Это квазипустое слово: начав стирать его в состоянии po, автомат переходит в состояние pi, в котором и остается, пока не стерто все, кроме маркера дна.

При любом n > 1 автомат Mn имеет три состояния. Используемое в теореме 3 число q! + 1 есть 3! + 1 = 7.

Ленточные слова автомата Mn имеют вид

Zo(Zi •••Zn)ky,

где k > 0, а y есть префикс цепочки Zi • • • Zn.

Пусть n = 8, N = {1, • • •, 7}. Таким образом, множество N содержит q! + 1 различных целых чисел, меньших n. Рассмотрим Zi • • • Z8 - возможное из верхних в магазине слов. Пусть e = 7. Для любого числа / Е N, / < e, слово

Zf+i... Ze не является квазипустым, так как (Z/+1... Ze)k для любого k > 1 не может входить в ленточное слово автомата и не может быть стерто автоматом.

Теорема 3 работы [Stearns 67] вызывает сомнение и без приведенного обсуждения: подозрительна возможность оценить сверху длину квазипустого слова, как бы оно ни определялось, только с помощью числа состояний, без учета числа магазинных символов. Повидимому, возможен какойто аналог этой теоремы, использующий понятие вершины.

Заметим, что можно превратить автомат Mn в наполняющий магазин в реальное время заменой команд 1, 2 на команды

(po, a, Zo) - (po, ZZi... Zn), Z e {Zo, Zn}.

При этом вид ленточных слов остается таким же. Можно строить и совершенные автоматы МП, наполняющие магазин в реальное время, перейдя от языка

{amb m > 1}

к языкам

Ln = {amnb m > 1}.

Здесь для каждого Ln число n определяет число магазинных символов автомата МЛ, отличных от маркера дна.

§2. Проблема построения графа сопряжений

Проблема эквивалентности детерминированных магазинных автоматов являет ся ключевой в развитии некоторых направлений теории языков и автоматов. Естественна идея использовать имитацию одновременной работы двух детерминиро ванных магазинных автоматов для проверки их эквивалентности. Еще в [Valiant 73] предложена техника имитации, применимая в некоторых подклассах детер минированных магазинных автоматов и использованная впоследствии в работах [Романовский 80, Романовский 86], предлагающих решения проблемы эквивалентности в классах детерминированных магазинных автоматов частного вида. (Впрочем, решение, представленное в [Романовский 86], ошибочно, что обсужда -ется в разделе 2 настоящего параграфа.)

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

Для любой заданной пары детерминированных магазинных автоматов легко построить конечное множество, содержащее в себе все дуги соответствующе го графа сопряжений. Однако, выделение подмножества дуг графа сопряжений оказывается алгоритмически неразрешимым даже в классе детерминированных магазинных автоматов, наполняющих магазин в реальное время и допускающих регулярные языки. Это доказывается с помощью детерминированных магазинных