Теоретическое введение. Моделирование с использованием конечных автоматов

Конечные автоматы и такие тесно связанные с ними конструк­ции, как, например, линейные грамматики и регулярные выраже­ния, относятся к важнейшим основным понятиям информатики. Различные варианты конечных автоматов и близкие им матема­тические объекты служат для описания и анализа технических уст­ройств, различных систем и процессов, программ и алгоритмов. Многие сложные концепции теоретической информатики — и при­том относящиеся не только к более общим моделям автоматов, таким как автоматы с магазинной памятью и машины Тьюрин­га, — были выработаны на базе теории конечных автоматов. Тео­рия автоматов порождает ряд легко формулируемых, но далеко не тривиальных проблем. Они приводят к весьма сложным алго­ритмам и отчасти проясняют причины, по которым необходимо систематическое развитие математического программирования и теории алгоритмов, сопровождаемое подробным анализом коррект­ности и сложности. Теория конечных автоматов имеет многочис­ленные приложения в технической и практической информатике и составляет существенную часть теоретической информатики. Это делает знание методов моделирования на основе теории автоматов необходимым каждому спе­циалисту по информатике.