Читать онлайн «Жемчужины теории формальных языков»

Жемчужины теории формальных языков 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 Предисловие редактора перевода Теория формальных языков возникла на стыке математической логики, теории алгоритмов и алгебры. Математическая логика и теория алгоритмов дали математике новый объект исследования, а именно текст, обладающий и синтаксической структурой, и смыслом (семантикой). Мощным стимулом для изучения этого объекта явились приложения математики к естественным языкам, языкам программирования и вычислительной технике. Множества текстов, объединенных общим синтаксисом, — языки — изучаются (вне связи с семантикой) теорией формальных языков; при этом используются комбинаторно-алгебраические методы. Сам термин «теория формальных языков», как и его эквивалент «математическая лингвистика», не отражает того, что исследуется лишь синтаксический аспект языка и что исследование ведется алгебраическими методами, но мы не пытаемся предлагать ничего взамен. Мы уже отметили основные научные факторы, обусловившие развитие теории формальных языков, — прогресс математической логики и теории алгоритмов в тридцатых годах и появление ЭВМ в пятидесятых. Однако и здесь, как часто случается, есть пионерские работы, намного опередившие свое время и поэтому иногда забываемые. В данном случае — это исследования А. Туэ начала века. Одно из них служит отправной точкой первой главы настоящей книги, о других будет коротко сказано в послесловии к книге, которым с со* гласия автора снабдили ее переводчик и редактор перевода и в котором приводятся наиболее существенные (в основном недавно полученные) результаты, идейно и тематически связанные с содержанием книги. С именем А. Туэ в теории формальных языков по праву соседствует имя другого знаменитого скандинавского математика — президента Европейской ассоциации вычислительных наук, автора настоящей книги — Арто Саломаа.