Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений

Новосибирск: Новосибирский гос. университет (НГУ), 1995. – 113 с. Излагаются основы теории формальных языков и грамматик. Рассматриваются классы регулярных и контекстно-свободных языков и их связь с конечными и магазинными автоматами. Обсуждаются фундаментальные вопросы сложности решения задач дискретной математики.
Для студентов вузов, обучающихся по специальности "математика, "прикладная математика и ’’информатика. Содержание:
Цепочки, языки и грамматики.
Множества цепочек.
Грамматики составляющих.
Грамматики с ограничениями на правила.
Регулярные множества, их распознавание и порождение.
Регулярные множества и регулярные выражения.
Конечные автоматы.
Свойства регулярных множеств.
Контекстно-свободные языки и магазинные автоматы.
Деревья выводов и однозначность грамматик.
Преобразование КС-грамматик.
Автоматы с магазинной памятью.
Свойства класса КС-языков.
Сложность алгоритмов и языков.
Машины Тьюринга.
Классы P и NP.
Полиномиальная сводимость и NP-полнота.
Методы доказательства NP-полноты.