Предисловие редактора перевода

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

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

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

Говоря о содержании книги, хотелось бы отметить блестящую подачу

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

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

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

А. Л. Семенов, Москва, 1985 г.