Языки и автоматы. Сборник переводов

Книга входит в известную серию «Библиотека
«Кибернетического сборника» и содержит переводы наиболее важных статей
последних лет по теории языков программирования. Эта тематика
ранее затрагивалась в «Кибернетических сборниках» и сборниках
переводов «Проблемы математической логики» («Мир», 1970) и
«Сложность вычислений и алгоритмов» («Мир», 1974).
В сборнике три раздела. Первый посвящен
контекстно-свободным языкам и открывается классической статьей Д. Кнута о
языках, допускающих однопроходной анализ; в других статьях
рассматриваются скорость распознавания языков и алгоритмические
проблемы. Во втором разделе излагаются грамматики более
общего вида — индексные, контекстные и грамматики с рассеянным
контекстом. Несколько основополагающих статей третьего раздела
посвящены аксиоматическому описанию языков; эта тематика еще
не затрагивалась в отечественной литературе.
Книга рассчитана на специалистов по математической логике,
языкам программирования, теории алгоритмов и математической
лингвистике. Она будет полезна студентам и аспирантам
указанных специальностей.