Конечный автомат: теория и реализация. Типы конечных автоматов Практическое применение автоматов

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

По входному каналу в каждый момент времени t =1, 2, ... в устройство М поступают входные сигналы (из некоторого конечного множества сигналов). Задается закон изменения состояния к следующему моменту времени в зависимости от входного сигнала и состояния устройства в текущий момент времени. Выходной сигнал зависит от состояния и входного сигнала в текущий момент времени (рис. 1).

Конечный автомат является математической моделью реальных дискретных устройств по переработке информации.

Конечным автоматом называется система А= (X , Q , Y ,  ,  ), где X , Q , Y - произвольные непустые конечные множества, а  и   функции, из которых:

множество X ={a 1 , ..., a m } называется входным алфавитом , а его элементы - входными сигналами , их последовательности - входными словами ;

множество Q ={q 1 , ..., q n } называется множеством состояний автомата, а его элементы - состояниями ;

множество Y ={b 1 , ..., b p } называется выходным алфавитом , его элементы - выходными сигналами , их последовательности - выходными словами ;

функция  : X Q Q называется функцией переходов ;

функция  :X Q Y называется функцией выходов .

Таким образом,  (x , q )Q ,  (x , q )Y для x X , q Q .

С конечным автоматом ассоциируется воображаемое устройство, ко­торое работает следующим образом. Оно может находиться в состоянии из множества Q , воспринимать сигналы из множества X и выдавать сигналы из множества Y .

2. Способы задания конечного автомата

Существует несколько эквивалентных способов задания абстрактных автоматов, среди которых можно назвать три: табличный , геометрический и функциональный .

2.1.Табличное задание автомата

Из определения автомата следует, что его всегда можно задать табли­цей с двумя входами, содержащей т строк и п столбцов, где на пересечении столбца q и строки а стоят значения функций  (a i , q j ),  (a i , q j ).

2.2. Задание автомата диаграммой Мура

Другой способ задания конечного автомата - графический, то есть с помощью графа. Автомат изображается в виде помеченного ориентированного графа Г (Q , D ) с множеством вершин Q и множеством дуг D ={(q j ,  (a i , q j ))| q j Q , a i X }, при этом дуга (q j ,  (a i , q j )) помечается парой (a i ,  (a i , q j )). Таким образом, при этом способе состояния автомата изображают кружками, в которые вписывают символы состояний q j (j = 1, …, n ). Из каждого кружка проводится т стрелок (ориентированных ребер) взаимно-однозначно соответствующих символам входного алфавита X ={a 1 , ..., a m }. Стрелке, соответствующей букве a i X и выходящей из кружка q j Q , приписывается пара (a i ,  (a i , q j )), причем эта стрелка ведет в кружок, соответствующий  (a i , q j ).

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

Конечный автомат - это некоторая абстрактная модель, содержащая конечное число состояний чего-либо. Используется для представления и управления потоком выполнения каких-либо команд. Конечный автомат идеально подходит для реализации искусственного интеллекта в играх, получая аккуратное решение без написания громоздкого и сложного кода. В данной статье мы рассмотрим теорию, а также узнаем, как использовать простой и основанный на стеке конечный автомат.

Мы уже публиковали серию статей по написанию искусственного интеллекта при помощи конечного автомата. Если вы еще не читали эту серию, то можете сделать это сейчас:

Что такое конечный автомат?

Конечный автомат (или попросту FSM - Finite-state machine) это модель вычислений, основанная на гипотетической машине состояний. В один момент времени только одно состояние может быть активным. Следовательно, для выполнения каких-либо действий машина должна менять свое состояние.

Конечные автоматы обычно используются для организации и представления потока выполнения чего-либо. Это особенно полезно при реализации ИИ в играх. Например, для написания «мозга» врага: каждое состояние представляет собой какое-то действие (напасть, уклониться и т. д.).

Конечный автомат можно представить в виде графа, вершины которого являются состояниями, а ребра - переходы между ними. Каждое ребро имеет метку, информирующую о том, когда должен произойти переход. Например, на изображении выше видно, что автомат сменит состояние «wander» на состояние «attack» при условии, что игрок находится рядом.

Планирование состояний и их переходов

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

Отправной точкой является состояние «find leaf», которое остается активным до тех пор, пока муравей не найдет лист. Когда это произойдет, то состояние сменится на «go home». Это же состояние останется активным, пока наш муравей не доберется до муравейника. После этого состояние вновь меняется на «find leaf».

Если состояние «find leaf» активно, но курсор мыши находится рядом с муравьем, то состояние меняется на «run away». Как только муравей будет в достаточно безопасном расстоянии от курсора мыши, состояние вновь сменится на «find leaf».

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

Реализация простого конечного автомата

Конечный автомат можно реализовать при помощи одного класса. Назовем его FSM. Идея состоит в том, чтобы реализовать каждое состояние как метод или функцию. Также будем использовать свойство activeState для определения активного состояния.

Public class FSM { private var activeState:Function; // указатель на активное состояние автомата public function FSM() { } public function setState(state:Function) :void { activeState = state; } public function update() :void { if (activeState != null) { activeState(); } } }

Всякое состояние есть функция. Причем такая, что она будет вызываться при каждом обновлении кадра игры. Как уже говорилось, в activeState будет храниться указатель на функцию активного состояния.

Метод update() класса FSM должен вызываться каждый кадр игры. А он, в свою очередь, будет вызывать функцию того состояния, которое в данный момент является активным.

Метод setState() будет задавать новое активное состояние. Более того, каждая функция, определяющая какое-то состояние автомата, не обязательно должна принадлежать классу FSM - это делает наш класс более универсальным.

Использование конечного автомата

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

Наш муравей представлен классом Ant , в котором есть поле brain . Это как раз экземпляр класса FSM .

Public class Ant { public var position:Vector3D; public var velocity:Vector3D; public var brain:FSM; public function Ant(posX:Number, posY:Number) { position = new Vector3D(posX, posY); velocity = new Vector3D(-1, -1); brain = new FSM(); // Начинаем с поиска листка. brain.setState(findLeaf); } /** * Состояние "findLeaf". * Заставляет муравья искать листья. */ public function findLeaf() :void { } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { } public function update():void { // Обновление конечного автомата. Эта функция будет вызывать // функцию активного состояния: findLeaf(), goHome() или runAway(). brain.update(); // Применение скорости для движения муравья. moveBasedOnVelocity(); } (...) }

Класс Ant также содержит свойства velocity и position . Эти переменные будут использоваться для расчета движения с помощью метода Эйлера . Функция update() вызывается при каждом обновлении кадра игры.

Ниже приводится реализация каждого из методов, начиная с findLeaf() - состояния, ответственного за поиск листьев.

Public function findLeaf() :void { // Перемещает муравья к листу. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this) <= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }

Состояние goHome() - используется для того, чтобы муравей отправился домой.

Public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }

И, наконец, состояние runAway() - используется при уворачивании от курсора мыши.

Public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) { // Нет, уже далеко. Пора возвращаться к поискам листочек. brain.setState(findLeaf); } }

Улучшение FSM: автомат, основанный на стеке

Представьте себе, что муравью на пути домой также нужно убегать от курсора мыши. Вот так будут выглядеть состояния FSM:

Кажется, что изменение тривиальное. Нет, такое изменение создает нам проблему. Представьте, что текущее состояние это «run away». Если курсор мыши отдаляется от муравья, что он должен делать: идти домой или искать лист?

Решением такой проблемы является конечный автомат, основанный на стеке. В отличие от простого FSM, который мы реализовали выше, данный вид FSM использует стек для управления состояниями. В верхней части стека находится активное состояние, а переходы возникают при добавлении/удалении состояний из стека.

А вот и наглядная демонстрация работы конечного автомата, основанного на стеке:

Реализация FSM, основанного на стеке

Такой конечный автомат может быть реализован так же, как и простой. Отличием будет использование массива указателей на необходимые состояния. Свойство activeState нам уже не понадобится, т.к. вершина стека уже будет указывать на активное состояние.

Public class StackFSM { private var stack:Array; public function StackFSM() { this.stack = new Array(); } public function update() :void { var currentStateFunction:Function = getCurrentState(); if (currentStateFunction != null) { currentStateFunction(); } } public function popState() :Function { return stack.pop(); } public function pushState(state:Function) :void { if (getCurrentState() != state) { stack.push(state); } } public function getCurrentState() :Function { return stack.length > 0 ? stack : null; } }

Обратите внимание, что метод setState() был заменен на pushState() (добавление нового состояния в вершину стека) и popState() (удаление состояния на вершине стека).

Использование FSM, основанного на стеке

Важно отметить, что при использовании конечного автомата на основе стека каждое состояние несет ответственность за свое удаление из стека при отсутствии необходимости в нем. Например, состояние attack() само должно удалять себя из стека в том случае, если враг был уже уничтожен.

Public class Ant { (...) public var brain:StackFSM; public function Ant(posX:Number, posY:Number) { (...) brain = new StackFSM(); // Начинаем с поиска листка brain.pushState(findLeaf); (...) } /** * Состояние "findLeaf". * Заставляет муравья искать листья. */ public function findLeaf() :void { // Перемещает муравья к листу. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this) <= 10) { //Муравей только что подобрал листок, время // возвращаться домой! brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "findLeaf", что означает, // что состояние "findLeaf" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "goHome", что означает, // что состояние "goHome" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) { // Нет, уже далеко. Пора возвращаться к поискам листочков. brain.popState(); } } (...) }

Вывод

Конечные автоматы, безусловно, полезны для реализации логики искусственного интеллекта в играх. Они могут быть легко представлены в виде графа, что позволяет разработчику увидеть все возможные варианты.

Реализация конечного автомата с функциями-состояниями является простым, но в то же время мощным методом. Даже более сложные переплетения состояний могут быть реализованы при помощи FSM.

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

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

Приведём несколько примеров конечных автоматов.

Пример 1. Элемент задержки (элемент памяти).

Элементы задержки представляют собой устройство, имеющее один вход и один выход. Причем значение выходного сигнала в момент времени t совпадает со значением сигнала в предыдущий момент. Схематично элемент задержки можно изобразить следующим образом (рис. 2).

Предположим, что входной и, следовательно, выходной алфавит есть X ={0, 1}, Y ={0, 1}. Тогда Q ={0, 1}. Под состоянием элемента задержки в момент времени t понимается содержание элемента памяти в данный момент. Таким образом q (t )= X (t 1), a Y (t )= q (t )=X (t 1).

Зададим элемент задержки таблицей, где а 1 =0, а 2 =1, q 1 =0, q 2 =1,

(a 1 , q 1)= (0, 0)=0,  (a 1 , q 1)= (0, 0)=0;

(a 1 , q 2)= (0, 1)=0,  (a 1 , q 2)= (0, 1)=1;

(a 2 , q 1)= (1, 0)=1,  (a 2 , q 1)= (1, 0)=0;

(a 2 , q 2)= (1, 1)=1,  (a 2 , q 2)= (1, 1)=1;

Диаграмма Мура изображена на рис. 3

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

Обратим внимание на то, что т=п=р =2. Тогда k =r =s =1, и поэтому элемент задержки задается двумя функциями  и  . Таблица истинности этих функций содержит 2 k + r =2 2 =4 строки и k +r +r +s =4 столбца:

Пример 2. Двоичный сумматор последовательного действия.

Данный сумматор последовательного действия представляет собой устройство, осуществляющее сложение двух чисел в двоичной системе исчисления. На входы сумматора подаются числа х 1 и x 2 , начиная с младших разрядов. На выходе формируется последовательность, соответствующая записи числа х 1 +x 2 в двоичной системе исчисления (рис. 4).

Входной и выходной алфавиты определены однозначно: X ={00; 01; 10; 11}, Y ={0,1}. Множество состояний определяется значением пере­носа при сложении соответствующих разрядов чисел х 1 и x 2 . Если при сложении некоторых разрядов образовался перенос, то будем считать, что сумматор перешел в состояние q 1 . При отсутствии переноса будем считать, что сумматор находится в состоянии q 0 .

Сумматор задается таблицей.

Диаграмма Мура сумматора последовательного действия изображена на рис. 5.

Заметим, что входные и выходные символы уже закодированы. Состояния закодируем следующим образом:  (q 0)=0,  (q 1)=1. Поэтому сумматор последовательного действия задается двумя булевыми функциями, таблица истинности которых следующая:

Пример 3. Схема сравнения на равенство.

Схема сравнения на равенств представляет собой устройство, срав­нивающее два числа х 1 и x 2 , заданное в двоичной системе исчисления. Это устройство работает следующим образом. На вход устройства после­довательно, начиная со старших, подаются разряды чисел х 1 и x 2 . Эти разряды сравниваются. При совпадении разрядов на выходе схемы формируется выходной сигнал 0, в противном случае на выходе появляется сигнал 1. Ясно, что появление 1 в выходной последовательности означает, что сравниваемые числа х 1 и x 2 различны. Если же выходная последовательность является нулевой и ее длина совпадает с числом разрядов сравниваемых чисел, то х 1 и x 2 .

Для этого автомата X ={00, 01, 10, 11}; Y ={0,1}.

Функционирование схемы определяется двумя состояниями. Состояние q 0 соответствует равенству сравниваемых в данный момент разрядов. При этом автомат остается в этом же состоянии. Если в следующий момент сравниваемые разряды будут различны, то автомат перейдет в новое состояние q 1 и в нем остается, так как это означает, что числа различны. Таким образом, схему сравнения можно задать таблицей:

Диаграмма Мура схемы сравнения на равенство изображена на рис. 6.

Кодирование состояний произведем следующим образом:  (q 0)=0,  (q 1)=1. Автомат будет задаваться двумя функциями.

Пример 4. Схема сравнения на неравенство.

Схема сравнения на неравенство представляет собой устройство, позволяющее выяснить, равны ли сравниваемые х 1 и x 2 , и если они не равны, выяснить, какое из них больше другого. Это устройство имеет два входа и два выхода. Выходные сигналы y 1 (t ) и y 2 (t )определяются по следующим правилам:

y 1 (t )=y 2 (t )=0, если x 1 (t )=x 2 (t );

y 1 (t )=1, y 2 (t )=0, если x 1 (t )>x 2 (t ), то есть x 1 (t )=1, x 2 (t )=0;

y 1 (t )=0, y 2 (t )=1, если x 1 (t )<x 2 (t ), то есть x 1 (t )=0, x 2 (t )=1.

Таким образом, при подаче на вход схемы сравнения на неравенство чисел x 1 =x 1 (l)…x 1 (t ) и x 2 =x 2 (l)…x 2 (t )последовательно сравниваются разряды этих чисел, начиная со старших. Выходные сигналы формулируются согласно вышеуказанным правилам. При этом, если выходная последовательность состоит из нулевых пар, то x 1 =x 2 . Если первая, отличная от нулевой, пара имеет вид , () то x 1 >x 2 (x 1 <x 2).

Из описания схемы следует, что

X ={00, 01, 10, 11}, Y ={00, 01, 10}.

Состояние схемы определяется следующим образом. Предположим, что в начальный момент времени t =1 автомат находится в состоянии q 1 . Если сравниваемые разряды чисел х 1 и х 2 совпадают, то автомат остается в этом состоянии. Заметим, что на выходе при этом появится сигнал 00. Если же разряд числа х 1 будет меньше (больше) соответствующего разряда числа х 2 , то автомат перейдет в состояние q 2 (q 3). При этом на выходе появится сигнал 01 (10). В дальнейшем при подаче оставшихся разрядов чисел х 1 и х 2 на входы автомата автомат будет оставаться в состоянии q 2 (q 3) и вырабатывать выходной символ 10 (01). Из вышеизложенного следует, что схему сравнения на неравенство можно задать таблицей:

Соответствующая диаграмма Мура изображена на рис. 7.

Входной и выходной алфавиты здесь уже закодированы. Состояния q 1 , q 2 и q 3 закодируем:  1 (q 1)=00,  (q 2)=01,  (q 3)=10.

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

В таблице символами * отмечены наборы переменных x 1 , x 2 , z 1 , z 2 , на которых функции  1 ,  2 ,  1 ,  2 не определены. Положим значения функций  1 ,  2 ,  1 ,  2 на этих наборах равными 1.

Теория конечных автоматов

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

· конечный автомат может решать ряд легких задач компиляции. Лексический блок почти всегда строится на основе конечного автомата.

· работа конечного автомата отличается высоким быстродействием.

· моделирование конечного автомата требует фиксированного объема памяти, что упрощает управление памятью.

· существует ряд теорем и алгоритмов, позволяющих конструировать и упрощать конечные автоматы.

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

Определение: Конечный автомат - это формальная система, которая задается с помощью следующих объектов :

· конечным множеством входных символов;

· конечным множеством состояний;

· функцией переходов, которая каждой паре (текущее состояние, входной символ) ставит в соответствие новое состояние;

· начальным состоянием;

· подмножеством состояний, выделенных в качестве допускающих или заключительных.

Пример. Разберем работу контроллера, проверяющего четно или нечетно число единиц в произвольной цепочке, состоящей из нулей и единиц. Допустим, что соответствующий конечный автомат должен « допускать» все цепочки, содержащие нечетное число единиц и « отвергать » цепочки с четным их числом. Назовем этот автомат « контроллером четности ». Считаем, что символы, отличные от 0 и 1 нельзя подавать на вход автомата. Итак, входной алфавит контроллера есть множество {0, 1} . Считаем, что в конкретный момент времени конечный автомат имеет дело лишь с одним входным символом, а информацию о предыдущих символах входной цепочки сохраняет с помощью конечного множества состояний. В качестве множества состояний будем рассматривать множество { чет, нечет }, одно из этих состояний должно быть выбрано в качестве начального. Пусть им будет состояние {чет}, поскольку на первом шаге число прочитанных единиц равно нулю, а нуль есть четное число. При чтении очередного входного символа состояние автомата либо меняется, либо сохраняется прежним причем новое его состояние зависит от входного символа и текущего состояния. Такое изменение состояния называется переходом.

Работа автомата может описываться математически функцией переходов вида d(Sтек., x) = Sнов. Иначе это можно записать следующим образом:

d (чет., 0) = чет. d (чет., 1) = нечет.

d (нечет., 0) = нечет. d (нечет., 1) = чет.

Контроллер имеет единственное допускающее состояние НЕЧЕТ, а ЧЕТ есть « отвергающее » состояние. Отразим последовательность переходов автомата при подаче на его вход цепочки 1101.

ЧЕТ ® НЕЧЕТ ® ЧЕТ® ЧЕТ® НЕЧЕТ

Таблица переходов такого автомата имеет вид:

Определение. Конечный автомат - это формальная система

S = { A, Q, d, l,V },

объекты которой следующие:

* A - конечное множество входных символов (множество

терминалов);

* Q - конечное множество внутренних состояний автомата

(множество нетерминалов);

* V - конечное множество выходных символов (выходной алфавит);

* d - функция переходов, для которой характерно A ´ Q ® Q;

* l - функция выходов, определяющая отображение вида.

Теория автоматов

Определение автомата и его разновидности. Таблицы и графы переходов и выходов. Подавтоматы. Теорема о приведенном автомате

Операции с автоматами

Преобразование автомата Мили в автомат Мура и автомата Мура в автомат Мили. Эквивалентность автоматов. Различимость состояний автоматов. Минимизация автоматов. Синтез автоматов. Распознающие автоматы

Автомат - система механизмов, устройств, в которой полностью автоматизированы процессы получения, преобразования, передачи энергии, материалов, информации Термин "автомат" используется в двух аспектах:

1) техническом,

2) математическом.

При математическом подходе под автоматом понимается математическая модель технического устройства, у которого должны быть входы, внутренние состояния и выходы. Относительно деталей структуры устройства сведений не должно быть.

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

Частным и важным случаем автомата выступает цифровой автомат (ЦА), в котором полностью автоматизированы процессы приема, преобразования, хранения и выдачи цифровой информации.

С точки зрения сигналов ЦА полезно определить как систему, которая может принимать входные сигналы, под их воздействием переходить из одного состояния в другое, сохранять его до прихода следующего входного сигнала, выдавать выходные сигналы.

ЦА считается конечным, если конечны множества входных сигналов X, состояний S и выходных сигналов Y. Конечный автомат можно поставить в соответствие такому устройству, как компьютер. Компьютер перерабатывает поступающие входные данные в выходные данные (результат), но этот результат соответствует не только входным данным, но и текущему состоянию компьютера, т.е. тем данным, которые хранятся в памяти компьютера, например, результаты предыдущих вычислений, программы вычислений.

Работа ЦА осуществляется в автоматном времени, определяемом числом периодов поступления входных сигналов.

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

Слова входного языка можно представить символами множества X={x 1 ,x 2 ,...x n }, который называют входным алфавитом , а слова выходного языка - символами множества Y={y 1 ,y 2 ,...y p }, который называют выходным алфавитом . Множество состояний автомата S={s 1 ,s 2 ,...s m } называют алфавитом состояний .

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

Работу абстрактного автомата следует рассматривать применительно к конкретным интервалам времени, т.к. каждому интервалу дискретности t будет соответствовать свой выходной сигнал y(t). Следовательно, функционирование автомата рассматривается через дискретные интервалы времени конечной продолжительности. В абстрактной теории цифровых автоматов считается, что входные сигналы воздействуют на синхронный автомат в момент начала каждого i -того интервала (кванта) времени, выделенного соответствующим синхроимпульсом (тактом), а изменение внутренних состояний автомата происходит в интервалы времени между смежными синхроимпульсами, когда нет воздействия входных сигналов.

Понятие «состояние» используют для того, чтобы установить функциональную зависимость генерируемых автоматом символов и/или слов выходного языка от символов и/или слов входного языка при реализации автоматом заданного алгоритма. Для каждого состояния автомата sÎS и для каждого символа xÎX в момент дискретного времени [t] на выходе устройства генерируется символ yÎY. Эту зависимость определяет функция выходов автомата j. Для каждого текущего состояния автомата sÎS и для каждого символа xÎX в момент дискретного времени [t] автомат переходит в очередное состояние sÎS. Эту зависимость определяет функция переходов автомата y. Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата (s 1[ s 2 s 3 ...) и последовательности выходных символов (y 1 y 2 y 3 ...), которые для последовательности символов (x 1 x 2 x 3 ...) разворачиваются в моменты дискретного времени t = 1,2,3,.... В прямоугольных скобках указывают моменты дискретного времени, которые называют иначе тактами, в круглых скобках - последовательности символов алфавитов X, Y и S.

Итак, математическая модель конечного автомата есть трехосновная алгебра, носителями которой являются три множества X, Y и S, а операциями - две функции j и y.