Послесловие. А. А. Мучник, А. Л. Семенов

Пытаться в послесловии к книге А. Саломаа дополнить ее какими-то новыми "драгоценными камнями" или тем более дать обзор всей области, значило бы вступить в противоречие с самим замыслом книги. Задача настоящего послесловия в другом: обратить внимание читателя на некоторые новые грани собранных автором "драгоценных камней" (мы продолжаем его метафору). Иначе говоря, мы попытались дополнить книгу комментариями, имея в виду познакомить читателя с результатами, непосредственно относящимися к содержанию книги, но в ней не упомянутыми (прежде всего потому, что они были получены уже после ее написания). Названия рассматриваемых тем выделены курсивом.

Начнем мы, однако, с работ А. Туэ (отметим, что в 1977 г. в Норвегии вышло его собрание сочинений [Th77]).

Задача Туэ о бесповторных словах и ее обобщения. Книга Саломаа начинается с рассмотрения задачи Туэ о построении слов и сверхслов, не содержащих x² и x³. Эта задача допускает замечательное обобщение. Заметим, что x² само есть слово, а именно слово в алфавите переменных. Возьмем вместо x² какое-либо другое слово φ в алфавите переменных и поставим ту же самую задачу - построить сверхслово в заданном алфавите, не содержащее ни одного значения слова φ (под значением понимается образ φ при действии нестирающего морфизма). Конечно, в такой постановке задача оказывается разрешимой не при любом слове φ. (Тривиальный пример - слово φ = x менее тривиальный - слово xyxzxyx, значение которого содержится в каждом сверхслове над любым алфавитом.) Слово, значение которого содержит любое сверхслово в заданном алфавите, называется блокирующим (или неизбежным). В работе [BEM] доказывается, что для каждого алфавита переменных X существует сверхслово, не содержащее значений ни одного не блокирующего слова в алфавите X (и, конечно, содержащее значения всех блокирующих).

Как отмечает Саломаа, результат Туэ нашел применение в различных областях математики, в частности в теории динамических систем. Еще одним применением является его Использование в решении знаменитой проблемы Бернсайда, остававшейся открытой более 50 лет (см. упр. 8 гл. 1). Проблема Бернсайда для показателя n состоит в существовании бесконечной группы с конечным числом образующих, для каждого элемента x которой выполнено xⁿ=1. Начиная изучать эту проблему, П. С. Новиков естественно пришел к вопросу о существовании сколь угодно длинных слов, не содержащих вхождений xⁿ. Ответ на этот вопрос П. С. Новиков нашел в статье С. Е. Аршона, заново открывшего в работе [Арш] результат Туэ. Работу по решению проблемы Бернсайда П. С. Новиков завершил совместно со своим учеником С. И. Адяном. Они построили при любом нечетном n ≥4381 нужный пример группы. Впоследствии С. И. Адян в книге [Ад75] переработал и уточнил доказательство и понизил оценку для нечетного n до 665. Конечно, в доказательстве Новикова - Адяна, являющемся на сегодняшний день наиболее сложным результатом в комбинаторике слов, пример Аршона - лишь небольшая деталь, но деталь необходимая и принципиальная. Решение проблемы Бернсайда нашло многочисленные применения в задачах теории групп, а также в новом разделе вычислительных наук, возникшем на стыке математической логики, теории алгоритмов и теоретического программирования - динамической логике (см. [StT]). Тесно связанными с теорией формальных языков оказываются и некоторые аналоги проблемы Бернсайда с дополнительными условиями (см. [Lu]). Здесь возникает много интересных открытых проблем в связи с "леммами о накачке" (см. упр. 4 к гл. 2).

Посмотрим еще раз на последовательность (1.6), решающую проблему построения бескубного слова и получающуюся итерацией морфизма h:

В ней каждый член получается применением h к предыдущему. Можно, однако, посмотреть на нее иначе. Будем строить не последовательность слов, а последовательность пар слов

Тогда очередное слово x_i+1⁽⁰⁾ в верхнем ряду получается как x_i⁽⁰⁾x_i⁽¹⁾, а слово x_i+1⁽¹⁾ в нижнем ряду - как x_i⁽¹⁾x_i⁽⁰⁾. Иначе говоря, возникает рекуррентное соотношение, аналогичное тем, которые (для чисел, а не для слов) рассматривает теория линейных рекуррентных последовательностей. Обобщая эту конструкцию, можно естественно определить рекуррентную последовательность наборов слов и рекуррентно задаваемые сверхслова.

Наряду с DOL-сверхсловами естественно рассматривать HDOL-сверхслова. HDOL-сверхслово - это образ DOL-сверхслова под действием произвольного нестирающего гомоморфизма. Можно показать, что класс HDOL-сверхслов совпадает с классом гомоморфных образов рекуррентно задаваемых сверхслов.

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

Исчисления Туэ. В другой группе своих работ Туэ рассматривал исчисления, которые теперь называются его именем. Для нас сейчас исчисления Туэ (в которых каждое правило может применяться в любую сторону) - прежде всего способ задания полугрупп (в частности, групп). Туэ же рассматривал свои исчисления безотносительно к алгебре; они имели для него скорее логико-лингвистическое содержание. Работа [Th14] замечательна по меньшей мере в следующих отношениях. Во-первых, в ней абсолютно ясно сформулирована (не менее ясно, чем десятая проблема в историческом докладе Гильберта) алгоритмическая массовая проблема - проблема выводимости слова в данной грамматике. Во-вторых, в ней получено решение этой проблемы в некоторых случаях; использованные методы представляют собой примеры того, что сейчас называется комбинаторикой слов. В-третьих, помимо общей алгоритмической проблемы (получившей отрицательное решение в известных работах Маркова и Поста), он сформулировал интересный частный случай - когда используется одно правило, причем с пустой левой частью. В этом частном случае, как показал Адян [Ад66] проблема имеет положительное решение. Замечательно, что Туэ предвосхитил не только грамматики над словами но и грамматики над деревьями (см. [Th10]). Еще для одного важного вида грамматик - грамматик над целочисленными векторами (систем сложения векторов) - лишь недавно в работе [Kos] было получено решение (причем положительное) проблемы выводимости в грамматике.

Из важных направлений, относящихся к системам Туэ и возникших в последние годы, отметим изучение систем со свойством Чёрча - Россера. Пусть задана система продукций - некоторое множество объектов и некоторый класс преобразований над ними, называемых элементарными упрощениями (и соответственно понимаемых). Рефлексивное транзитивное замыкание множества элементарных упрощений задает на объектах отношение упрощения; рефлексивное транзитивное симметричное замыкание - отношение эквивалентности. Основным в определении свойства Чёрча - Россера является следующее: для любых двух эквивалентных объектов x, y существует объект z, получаемый упрощением и из x, и из y. Это свойство использовалось при изучении самых различных систем продукций. В частности, само его название связано с известной теоремой Чёрча - Россера, относящейся к комбинаторной логике. Другим классическим примером системы с таким свойством является свободная группа, где элементарные упрощения - это вычеркивания стоящих рядом взаимно-обратных образующих. С полной ясностью, однако, роль этого свойства была осознана только в рамках теории формальных языков в начале семидесятых годов различными группами исследователей (см. [Bo], [Niv], [Як]). Свойство Чёрча - Россера обычно обеспечивает довольно редкое для классических алгоритмических проблем алгебры и практически весьма ценное качество строящихся на его основе алгоритмов: эти алгоритмы обычно оказываются очень эффективными (с линейным или квадратичным временем работы). Тем более удивительным оказывается, для сколь широкого класса алгебраических систем удается задать их системой продукций, обладающих свойством Чёрча - Россера. В частности, таким образом можно задать произвольные конечно-определенные уноиды, что дает возможность доказать разрешимость монадической теории любого такого уноида (см. [Rys]); о других классах см. [Ot].

Конечные автоматы и регулярные множества. Наиболее важным событием на начальном этапе развития теории формальных языков было открытие класса конечных автоматов и нахождение различных характеризаций для класса задаваемых ими множеств. Почти одновременно Хомским были предложены классы формальных грамматик (один из этих классов, образованный грамматиками типа 3, дает вариант характеризаций регулярных множеств). Регулярные множества и конечные автоматы сохранили свое значение и до сих пор. Книга Саломаа ярко это иллюстрирует.

Изучая конечные автоматы с точки зрения общей теории алгоритмов и исчислений, сразу можно заметить, что их возможности очень ограниченны. В то же время именно эта ограниченность делает возможным применение комбинаторно-алгебраических методов и приводит к алгоритмической разрешимости самых разных задач, связанных с конечными автоматами. Однако это не главная причина, обеспечивающая им прочное место в современной вычислительной науке. Конечные автоматы являются моделями всевозможных естественных и искусственных устройств, входят как элементарные составные части в целый ряд формальных уточнений понятия вычислимой функции, в определение магазинных и счетчиковых автоматов, итеративных сетей (автоматов Неймана), схем программ и автоматов. Конечные автоматы и их обобщения сыграли большую роль в установлении разрешимости ряда логических теорий (см., например, [Ce83] или [ТрБ*]).

Замечательной особенностью класса регулярных языков является замкнутость относительно большого числа естественных операций: булевых операций, регулярных операций (теорема Клини), прямых и обратных морфизмов, конечно-автоматных отображений. В силу этого класс регулярных языков входит как часть в любое абстрактное семейство языков (АСЯ). Таким большим числом "хороших" свойств в математике обладают, пожалуй, лишь рациональные функции над полями.

Степенные ряды. Описанная аналогия не случайна. Регулярные грамматики, записанные в виде линейных уравнений от некоммутативных переменных, приводят к "изображению" порождаемых ими регулярных языков в виде рациональных степенных рядов от некоммутативных переменных (алфавитных букв), куда каждое слово языка входит с той кратностью (вариант - вероятностью), с какой оно порождается грамматикой, а коммутативные образы этих рядов являются обычными степенными рядами. В связи с указанной аналогией операции Клини часто называют рациональными. (Заметим, что итерация A* может быть записана как (1-A)^-1.) В свою очередь контекстно-свободные грамматики могут быть сопоставлены с алгебраическими системами уравнений, решение которых ищется в виде набора формальных степенных рядов от некоммутирующих переменных. Коэффициенты рядов указывают на число различных выводов одного слова в грамматике. Если подставлять в ряды вместо переменных действительные числа, будем получать обыкновенные алгебраические функции. Пользуясь алгоритмом разрешения для элементарной теории поля действительных чисел, можно решать алгоритмическую проблему равенства получающихся функций. Отсюда вытекает, например, разрешимость проблемы равенства для языков, один из которых порождается однозначной грамматикой, а другой регулярен, и других алгоритмических проблем (см. [Ce73], [SaSo], [My]).

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

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

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

Мы сейчас изложим очень простое доказательство гипотезы Эренфойхта, принадлежащее В. С. Губе. Как мы видим, эта гипотеза представляет собой принцип компактности. Известно, что этот принцип имеет место и для алгебраических уравнений от конечного числа переменных (например, над полем действительных чисел). Для алгебраических уравнений он является следствием известной теоремы Гильберта о нетеровости кольца многочленов от нескольких переменных (см. [Л]). Другой известный алгебраический факт (используемый в упомянутом подходе Маркова) - это существование точного представления свободной полугруппы матрицами (например, (2×2)-матрицами над полем действительных чисел). Заменив в системе уравнений над полугруппой константы (символы алфавита) их образами при представлении, а переменные - матрицами с переменными коэффициентами, мы получим систему матричных уравнений.

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

конечную подсистему. Элементы этой подсистемы возникли из конечного числа исходных уравнений в словах. Это и доказывает принцип компактности для них. Однако выбор тестового множества в общем случае не может быть эффективным, хотя для семейства контекстно-свободных языков и ряда других семейств это делается эффективно (см. [CuP*], [Kar] с библиографией и [MY*]).

Из гипотезы Эренфойхта вытекает разрешимость алгоритмической проблемы последовательной эквивалентности для DOL-систем и даже для HDOL-систем. (HDOL-система состоит из DOL-системы и морфпзма, применяемого к слову или сверхслову после окончания работы DOL-системы; см. [Kar].)

Как видно хотя бы из приведенных выше результатов, А. Саломаа действительно удалось указать "точки роста" теории формальных языков, в которых математическая глубина и ясность результатов, характерная для теорем классической математики, соседствуют с актуальностью для вычислительных наук.

В заключение несколько советов читателям, которые захотят подробнее познакомиться с теорией формальных языков и родственными проблемами математической логики, теории алгоритмов и теории полугрупп по легко доступной литературе на русском языке. Мы рекомендуем им обратиться к обзору [АУ*], сборникам [СВиА*] и [ПМЛ*], монографиям Гинзбурга [G1], Лаллемана [La] и [Г]. Ориентироваться в море статей по теории формальных языков за 1969-1974 гг. могут помочь обзоры [ГД] и [МС]. Просматривая РЖ "Математика", раздел Г (до 1984 г. раздел В), отдел "Математическая лингвистика", можно быть в курсе последних достижений в этой области.