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