Глава 3

НЕКОТОРЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ

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

Параграф 1 затрагивает сложную тему поиска эффективных алгоритмов, проверяющих регулярность детерминированного языка. В нем представлено достаточное условие регулярности детерминированного языка, проверяемое по ядру определяющего этот язык детерминированного D графа или детерминированного магазинного автомата. Отметим, что этот результат был усилен в диссертации [Вылиток 98].

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

Построить алгоритм, который по произвольной паре эквивалентных D графов получает их граф сопряжений.

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

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

(состояние, непустая цепочка магазинных символов),

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

Кроме того, в параграфе 3 доказывается неразрешимость проблемы регулярно -сти объединения двух непустых детерминированных языков.

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

ее основе лежит понятие модуля. В рассматриваемом случае привлечение алгебраических понятий и приемов оказалось возможным в той же мере, в какой это сделано в [Eilenberg 74] для изучения конечных автоматов. В частности, техника сравнения конечных автоматов, описанная в [Eilenberg 74], обобщается для проверки эквивалентности совершенных магазинных автоматов с одним поворотом, действующих в реальное время.

§1. Праволинейные магазинные автоматы и проблема регулярности

Вопрос регулярности является одним из наиболее важных в теории формальных языков и ее приложениях. В случае детерминированных языков он представляет особый интерес. Однако после работы [Stearns 67] проблема регулярности в этом случае практически не рассматривалась. Не появилось эффективных алгоритмов проверки регулярности даже для формализмов, описывающих подклассы детер минированных языков. Настоящая глава содержит достаточное условие регуляр ности бесконтекстного языка, проверяемое по (4,4) ядру магазинного автомата. В детерминированном случае для этой проверки можно взять несколько меньшее ядро. Здесь существенно используется понятие графа магазинного автомата.

Раздел 1.1 определяет понятие праволинейного магазинного автомата. Пометки парных циклов праволинейного магазинного автомата удовлетворяют ограничению, позволяющему только такое разрастание допускаемых цепочек, которое обеспечивается конечными автоматами или праволинейными грамматиками. Устанавливается, что праволинейный магазинный автомат допускает регулярное мно жество. Рассматривается признак праволинейности магазинного автомата, опре деляющий достаточное условие регулярности допускаемого языка. Формулирует -ся алгоритм проверки праволинейности магазинного автомата, представляющий собой частичный алгоритм проверки регулярности бесконтекстного языка.

В разделе 1.2 приводится более "сильное"достаточное условие регулярности бесконтекстного языка, полученное в работе [Вылиток 98] путем обобщения ре -зультата, представленного в разделе 1.1. Точнее, в [Вылиток 98] расширяется понятие так называемого монома; это расширение позволяет выделить подкласс магазинных автоматов, который является аналогом определенного Н. Хомским класса грамматик без самовставления.

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

1.1. Мономы и праволинейность

Пусть маршрут T таков, что для некоторых Ti, T2 тройка (T, Ti, T2) является гнездом. Тогда назовем T открывающим маршрутом.

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

Пусть T - читающий открывающий цикл. Пусть T2 не является читающим стирающим циклом для любой четверки (T0, Ti, T2, T3), такой, что T0TTiT2T3 есть маршрут, в котором T и T2 парны. Тогда будем говорить, что цикл T есть моном (в маршруте T0TTiT2T3).

Пусть каждый читающий открывающий цикл магазинного автомата M является мономом. Тогда назовем автомат M праволинейным.

Заметим, что регулярность языка, допускаемого праволинейным автоматом, было бы нетрудно вывести из построения по магазинному автомату бесконтекстной грамматики, которое рассмотрено в [Вылиток -Станевичене -Чернцов 96] и [Вылиток 98] и явилось базой остальных приведенных в последней работе результатов. Упомянутое построение является обобщением алгоритма, который сформулирован в, например, [Ginsburg 66] и который строит по конечному автомату праволинейную грамматику. Оно позволяет легко установить синонимичность для целого ряда названий подклассов бесконтекстных языков, возникших независимо в теории автоматов и теории грамматик.

Но мы докажем регулярность языка, допускаемого праволинейным магазинным автоматом, опираясь на материал главы 1.

Теорема 1. Пусть M - праволинейный магазинный автомат. Тогда язык L(M) регулярен.

Доказательство. Пусть, для определенности, входной алфавит автомата M есть Е. Пусть D = Graph(M).

Докажем, что КСвыражение Expr(D), определенное в параграфе 3 главы 1, является псевдосогласующим. Так как псевдосогласующее КСвыражение задает регулярный язык, отсюда будет следовать регулярность языка L(M) = L(D) = L(Expr(D)).

Вспомним определенные в параграфе 3 главы 1 КСвыражение E(D), которое задает множество Sentences(D), и морфизм у, который переводит КСвыражение E(D) в Expr(D). Заметим, что

Sentences(D) для £ £ Clan(E(D)),

u(T) £ L(D) для T £

Здесь толкование операции со (пометка фракции или пометка маршрута) опреде -ляется видом ее операнда.

Индукцией по k > 0 докажем, что для нейтрального маршрута T длины 2k фракция

£т = y(schemes(T))

не является вставляющей.

При k = 0 маршрут T пуст, и фракция

£T = (pair(T )t)pair(T)

не является вставляющей, поскольку даже циклов не содержит.

Пусть k > 0. Тогда для некоторых парных дуг п\, п2 и нейтральных маршрутов Ti, T2 имеем (по определению схемы) равенства

T = n{TiTl2T2,

scheme(T) = (Pair(T)niScheme(Ti)n2Scheme(T2))pair(T). По предположению индукции фракции

£Tl = y(scheme(Ti))

£T2 = y(scheme(T2))