Столбоушкин А.П., Тайцлин М.А. Математичесике основания информатики

Учебное пособие. - Тверь: ТвГУ. - 364 с. Пособие посвящено теории конечных автоматов и регулярных языков, изложены способы задания языков при помощи порождающих грамматик. Детально разобраны вопросы исчисления предикатов, неразрешимые проблемы и неполнота арифметики, понятия вычислительной сложности алгоритмов и полиномиально вычислимых глобальных предикатов.