Жемчужины теории
формальных языков
Jewels of formal
language theory
Arto Salomaa
University of Turku
Turku, Finland
Computer Science Press
Rockville, 1981
А. Саломаа
Жемчужины теории
формальных языков
Перевод с английского
А. А. Мучника
под редакцией
А. Л. Семенова
ББК81. 1
С 16
УДК 519. 765
Саломаа А. С16 Жемчужины теории формальных языков: Пер. с
англ. —М. : Мир, 1986, — 159 с, ил. Книга содержи! ряд замечательных результатов теории формальных
языков. Она отличается методическими достоинствами, большим числом
задач и примеров, постановкой новых проблем. Автор книги — профессор Уни*
верситета г Турку (Финляндия), президент Европейской ассоциации вы*
числительных наук — успешно решил поставленные им две основные задачи:
дать замкнутое введение в теорию для начинающих, изложить некоторые
блестящие и порой сложные результаты, интересные для специалистов. Для специалистов по вычислительным наукам, для студентов и аспи*
рантов университетов как введение в предмет.
^ 1502000000—063 е ое t ББК 81.
1
' О—ОО, 4. 1
041(01)—86 ' 4
Редакция литературы по математическим наукам
1981 Computer Science Press, Inc. перевод на русский язык с дополнением. «Мир», 1986
Предисловие редактора перевода
Теория формальных языков возникла на стыке
математической логики, теории алгоритмов и алгебры. Математическая логика и теория алгоритмов дали математике новый
объект исследования, а именно текст, обладающий и
синтаксической структурой, и смыслом (семантикой). Мощным
стимулом для изучения этого объекта явились приложения
математики к естественным языкам, языкам программирования
и вычислительной технике. Множества текстов,
объединенных общим синтаксисом, — языки — изучаются (вне связи с
семантикой) теорией формальных языков; при этом
используются комбинаторно-алгебраические методы. Сам термин
«теория формальных языков», как и его эквивалент
«математическая лингвистика», не отражает того, что исследуется
лишь синтаксический аспект языка и что исследование
ведется алгебраическими методами, но мы не пытаемся
предлагать ничего взамен. Мы уже отметили основные научные факторы,
обусловившие развитие теории формальных языков, — прогресс
математической логики и теории алгоритмов в тридцатых годах
и появление ЭВМ в пятидесятых. Однако и здесь, как часто
случается, есть пионерские работы, намного опередившие
свое время и поэтому иногда забываемые. В данном случае —
это исследования А. Туэ начала века. Одно из них служит
отправной точкой первой главы настоящей книги, о других
будет коротко сказано в послесловии к книге, которым с со*
гласия автора снабдили ее переводчик и редактор перевода
и в котором приводятся наиболее существенные (в основном
недавно полученные) результаты, идейно и тематически
связанные с содержанием книги. С именем А. Туэ в теории формальных языков по праву
соседствует имя другого знаменитого скандинавского
математика — президента Европейской ассоциации
вычислительных наук, автора настоящей книги — Арто Саломаа.