утверждают статьи [Мейтус 92] и [Senizergues 97]. Они не полны, содержат опечатки и ошибочные вспомогательные утверждения (но влияние этих ошибок на правильность основного результата не ясна). В настоящий момент нам не удалось преодолеть все эти трудности и понять, почему их авторы правы. По нашим сведениям упомянутые статьи непонятны и многим другим людям, даже высоко квалифицированным математикам.

Существуют работы, которые доказывают разрешимость проблемы эквивалентности для детерминированных магазинных автоматов или бесконтекстных грам матик частного вида, не охватывающих весь класс детерминированных язы ков (см., например, [Анисимов 77], [Зубенко 78], [Мейтус 89], [Непомнящая 81], [Романовский 80], [Романовский 86], [Яффе 74], [Korenjak -Hopcroft 66], [Nepomnjashchaja 84], [Oyamaguchi 87], [Valiant 73], [Valiant 74], [Yair -Amiram 84], [Tomita 95] и ссылки в перечисленных работах). Есть и работы, которые предприняты в сязи с проблемой эквивалентности детерминированных магазин ных автоматов и содержат алгоритмы проверки эквивалентности устройств, опре деляющих не все детерминированные языки, но зато определяющих и некоторые недетерминированные языки. К таковым относится выполненная под нашим руководством работа Б.Ф.Мельникова.

Проблема эквивалентности некоторых минимальных линейных грамматик (мо гущих порождать не только детерминированные языки), рассматриваемая в [Мельников 89], [Мельников 90] и [Melnikov 93], связана с наблюдением, ко -торое касается поведения так называемых парных циклов на D графе.

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

В [Станевичене 93б], [Станевичене 95], [Станевичене 96а] вводится в терми нах графов магазинных автоматов понятие сопряжения, формально определяющее совокупность сведений, необходимых имитирующему устройству для прослежи вания одновременной работы двух магазинных автоматов над одной и той же входной цепочкой. Затем определяется понятие графа сопряжений двух магазин ных автоматов, который является подграфом некоторого конечного графа, легко создаваемого по заданным автоматам. Граф сопряжений, по существу, представ -ляет собой квинтэссенцию всех возможных имитирующих устройств. Понятие

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

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

Отметим, что проблема соответствия Поста широко применяется в теории формальных языков; одно из первых наших упражнений в применении этой проблемы излагается в [Станевичене 87б]. Недаром сравнительно простое доказательство ее неразрешимости дано Р.Флойдом в [Floyd 64], сделавшим большой вклад в теорию перевода языков программирования. Он же сформулировал проблему ча стичного соответствия - вариант проблемы соответствия Поста, послуживший, например, для доказательства неразрешимости проблемы вхождения бесконтекст ной грамматики в LR(k)класс для какогонибудь k > 0 [Knuth 65]. Видоизменения постановки проблемы соответствия Поста можно найти в [Ruohonen 83].

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

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

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

В главе 3 указаны и положительно решаемые проблемы как примеры изло жения известных фактов в наших терминах. Тут привлекательна лаконичность доказательств.

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

Итак, работа предлагает новый подход в теории бесконтекстных языков, осно -ванный на обобщении языков Дика, которое, по сравнению с последними, удачнее отражает особенности парных объектов, присутствующих в цепочках нерегулярных бесконтекстных языков. Этот подход позволяет выявить внутреннюю общ -ность различных характеризаций бесконтекстных языков и получить ответы на достаточно трудные теоретические вопросы. В подтверждение действенности под хода рассмотрен ряд теорем. К основным можно отнести следующие результаты работы.

1.Предложены способы описания бесконтекстных языков так называемыми D-графами и КСвыражениями. На базе этих формализмов разработана система понятий, плодотворная в исследовании вопросов теории бесконтекстных языков.

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

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

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

5.Найдена методика расщепления Dграфов, которая опирается на результаты теории графов и позволяет активнее использовать прием разделения в практике обработки языковых описаний.

Не определяемые в работе термины и обозначения заимствованы из книги [Ginsburg 66]. Они большей частью повторяются и в других широко распро -страненных источниках. Термин "алфавит"применяется к непустому конечному множеству. Пустая цепочка обозначается буквой Л.

Маленькие буквы начала латинского алфавита обозначают символы входного алфавита автомата или терминального алфавита грамматики. Большие латинские буквы обозначают символы вспомогательных алфавитов. Маленькие буквы кон ца латинского алфавита обозначают цепочки. Эти соглашения обычно позволяют при задании грамматики (автомата) ограничиться выписыванием правил (соот ветственно команд).

Допускается вольность речи и обозначений, направленная на сокращение тек ста и принятая без оговорок во многих работах. Так, мы нередко пишем обороты вроде "множество L С Е*"или "число m > 1". Используются распространенные правила умолчания. Например, подразумевается, что термин, вводимый некото рым определением, применяется ко всем объектам, которые указываются данным определением, и только к ним.