Предисловие

Посвящается памяти моего отца Я. Э. Саломаа

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

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

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

В книге, несомненно, содержатся не все "жемчужины" теории, и, конечно же, некоторые из вошедших в нее результатов могут оказаться не столь красивыми, как не вошедшие. Может случиться, что кто-то не найдет здесь своей любимой "жемчужины". Однако, исходя из задачи (i) и учитывая, что настоящая работа замкнута и невелика по объему, мы не могли включить в нее материал из слишком разнородных областей. Своего рода "общим знаменателем" в книге является понятие морфизма свободного моноида.

Хотя книга и не предполагает никаких предварительных знаний, от читателя все же требуется известная математическая культура. Руководствуясь задачей (и), мы включили в книгу некоторые довольно сложные результаты. Да и вообще, нельзя ожидать, что красивые результаты окажутся тривиальными! Читатель, уже знакомый с теорией формальных языков, заметит, что мы едва упоминаем контекстные языки из классификации Хомского,- уже давно стало ясно, что этот класс языков не интересен с точки зрения приложений. Я также считаю, что он дал мало интересных теоретических результатов, как относящихся к нему самому, так и связанных с другими понятиями теории. Остальные семейства классификации Хомского, а также семейство DOL-языков рассматриваются достаточно подробно.

Благодарности. Я хочу выразить свою признательность Академии наук Финляндии за созданные для меня условия, позволившие спокойно работать над настоящей книгой. Трудно перечислить всех, так или иначе способствовавших этой работе. Мне очень помогли дискуссии, в которых участвовали В. Бухер, К. Чулик II, Ю. Карумяки, М. Линна, Я. Мяенпя, X. Маурер, Г. Розенберг, К. Руохонен и Д. Вуд; я весьма обязан им за это, равно как и за сделанные ими замечания. Нелегкую работу по перепечатке рукописи самым тщательным образом выполнила Э. Сёдерблом. В заключение я хочу поблагодарить издательство Computer Science Press и особенно Д. Лейна и Б. Ньюленд за превосходную и быструю редакционную обработку рукописи и корректур.

Арто Саломаа ноябрь, 1980