Спирина, М.С. Дискретная математика

Г л а в а 7 КОНЕЧНЫЕ АВТОМАТЫ Алгебраическая теория автоматов является разделом теорети­ ческой кибернетики, который изучает дискретные автоматы с абстрактной алгебраической точки зрения. Общая теория автоматов содержит различные подразделы. В за ­ висимости от предмета изучения она делится на абстрактную тео­ рию автоматов и структурную теорию автоматов. Абстрактная теория автоматов изучает переходы, совершае­ мые автоматом, на который воздействуют входные сигналы, а также выходные сигналы как результат этих переходов. Предметом изучения структурной теории автоматов является структура автомата, а также структура входных и выходных сигна­ лов, например, способы кодирования входных и выходных сиг­ налов и др. 7.1. Определение конечных автоматов В принципе, автоматы могут обла­ дать всеми основными свойствами са­ мых сложных систем, и даже челове­ ческого мозга. А. Н. Колмогоров Под автоматом (от греч. avmpazog — самодействующий) при­ нято понимать абстрактную модель устройства, функционирую­ щего в дискретном времени, которая перерабатывает последова­ тельность входных сигналов (стимулов) и превращает их в после­ довательность выходных сигналов (реакций). В процессе работы автомата происходит последовательная смена его внутренних со ­ стояний, причем состояние автомата в определенный момент вре­ мени однозначно определяется входным и выходным сигналами. Такие автоматы представляют собой основу всей современной вы ­ числительной техники и всевозможных дискретных систем авто­ матического контроля и управления. 341