Книга представляет собой учебник по курсу «Теория автоматов» — одному из важнейших компонентов федерального государственного образовательного стандарта бакалавров по направлению «Информатика и вычислительная техника». Этот курс является основной составной частью дисциплины «Теоретическая информатика», входящей в естественнонаучный цикл дисциплин российской высшей школы. Курс служит формированию знаний и умений, которые образуют теоретический фундамент, необходимый для корректной постановки и решения проблем в области информатики, для осознания целей и ограничений при создании вычислительных структур, алгоритмов и программ обработки информации.
Использование науки в инженерной практике при создании новых объектов состоит в построении и использовании математических моделей — абстракций, отражающих интересующие исследователя свойства реальности. Предмет данной книги составляет аппарат основных моделей в области информатики: булева алгебра, конечные автоматы, формальные языки, машины Тьюринга, классическая логика и т. д. Здесь изучаются их свойства, преимущества и ограничения, примеры применения. Следуя глубоко верной мысли о том, что нет ничего более практичного, чем хорошая теория, в данной книге эти модели рассматриваются не с точки зрения их абстрактных свойств как таковых; они изучаются как средство решения практических, инженерных задач.
Исследования в области теории автоматов начались в середине 50-х годов прошлого века. Несмотря на свою простоту, модель конечного автомата оказалась чрезвычайно удобной в огромном числе приложений не только в информатике, но и во многих других областях инженерной деятельности. Большой интерес к этой теории объясняется именно широкими возможностями ее применения. Без преувеличения можно сказать, что теория автоматов является одним из фундаментальных блоков современной теоретической и практической информатики. Наряду с классическими приложениями теории автоматов, такими как проектирование встроенных систем логического управления, обработка текстов и построение компиляторов искусственных языков, в последнее время появились новые, нетрадиционные области применения этой теории — спецификация и верификация
