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

Abstract

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