Основы теории конечных автоматов

Определение конечного автомата
Конечный автомат – это система, имеющая входные, выходные сигналы и имеющая конечное число внутренних состояний, а также функции переходов между состояниями.

Определение конечного автомата
Входной алфавит S – это конечное множество возможных входных сигналов.
Выходной алфавит R – это множество возможных выходных сигналов.
Алфавит состояний K – это множество возможных внутренних состояний автомата.
В любой момент времени автомат находится только в одном состоянии
Переход состояний – это изменение текущего состояния, вызванное внешним событием (Входным сигналом)

Определение конечного автомата
На этих множествах задают два логических оператора:
Функция переходов g – определяющая переход автомат из одного состояния в другое под действием входных сигналов (т.е. имеется состояние, подается вход и автомат переходит в другое состояние)
Функция выходов p – определяющая зависимость выходного сигнала автомата от состояния автомата и входного сигнала.

Определение конечного автомата
Пример 1, автомат с памятью
Пример 2, автомат без памяти

Определение конечного автомата
Конечным автоматом, называется система с конечным входным алфавитом S, конечным выходным алфавитом R, конечным множеством состояний K и двумя характерическими функциям
и gиp.
M = {S, R, K, g, p}
Конечность множества состояний говорит о том, что автомат (именно поэтому он называется конечным) обладает ограниченной памятью.

Критерий применимости автоматного подхода
С простым поведением Со сложным поведением

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

Способы задания конечных автоматов.
Пример 2, совмещенная таблица переходов и выходов
Состояния (К): Идет, стоит
Входные сигналы (S): Свет зеленый, свет зеленым мигающий, Свет красный.
Выходные сигналы (R): Начало движения, продолжение движения, ожидание и остановка.

Способы задания конечных автоматов.
Граф переходов – состоят из вершин и ориентированных дуг.
Пример 3, граф переходов

Способы задания конечных автоматов
Каждую форму представления можно задать двумя классами автоматов :
Автоматы Мура (Moore) – выходные сигналы зависят только от текущего состояния.
Автоматы Мили (Mealy) Мили - выходные сигналы зависят как от текущего состояния, так и от текущих значений входных сигналов.

Области применения конечного автомата
Пример 1, применение метода конечных автоматов при моделировании работы электронного сейфа - открытие двери с кодовым замком.
Состояниями автомата будут являться:
Закрыт
Проверка кода
Открыт
Входные сигналы, которые должен принимать автомат, будут следующие:
Верный код
Неверный код

Области применения конечного автомата
Составим таблицу переходов системы:

Области применения конечного автомата
Составим граф переходов:

Области применения конечного автомата
Пример 2, система климат – контроля в автомобиле.
Состояния системы:
системы выкл., когда система находится ни в одном их состояний, они находится в покое;
охлаждение, система охлаждает воздух до установленной температуры;
обогрев, система осуществляет нагрев воздуха в салоне до нужной температуры.
Входными сигналами будем считать:
холодно, человек, находящийся в автомобиле замерз;
жарко, человеку, находящемуся в автомобиле стало жарко;
климат-контроль выключен, систему выключили за ненадобностью.

Области применения конечного автомата
Составим таблицу переходов системы:

Области применения конечного автомата
Граф переходов выглядит следующим образом:

Области применения конечного автомата
Пример 3, проверка состояния счета в банке
Система имеет состояния:
Хороший свет
Превышены расходы по счету
Входные сигналы:
Разрешенное снятие денег
Неразрешенное снятие денег
Погашение долга
Обычное снятие денег
Вклад

Области применения конечного автомата
Таблица переходов имеет вид:

Области применения конечного автомата
Граф переходов: