7. Автоматы

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

Конечный автомат

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

Нас же будут интересовать детерминированные конечные автоматы.

Детерминированный конечный автомат — это кортеж , где

  •  — конечный (входной) алфавит;

  •  — конечное множество состояний;

  •  — стартовое состояние ( );

  •  — множество финальных состояний ( );

  •  — функция переходов.

Если всюду определена, то автомат полный. Иногда может быть частично определённой функцией.

Можно сказать, что автомат начинает свою работу в начальном состоянии, читает очередной символ с входной ленты, переходит в новое состояние. Если в процессе работы автомат оказался в конечном состоянии и вод пуст, то работа завершилась успешно. Во всех остальных случаях работа завершилась с ошибкой.

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

Автомат удобно представлять в виде графа, где вершины — это состояния, а рёбра — переходы.

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

Детерминированный конечный автомат
Рисунок 1. Детерминированный конечный автомат: 0 — стартовое состояние, 2 — финальное состояние

Автомат Мили

"Простой" конечный автомат только читает вход. Иногда хочется, чтобы он что-то выдавал на выходную ленту. Одна из модификаций, которая умеет такое делать — автомат Мили.

Автомат Мили — это кортеж , где

  •  — конечный входной алфавит;

  •  — конечный выходной алфавит;

  •  — конечное множество состояний;

  •  — стартовое состояние ( );

  •  — функция переходов.

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

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

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

Автомат Мили
Рисунок 2. Автомат Мили: 0 — стартовое состояние, {a, b, c, d} — входной алфавит, {1, 2, 3, 4} — выходной алфавит

Автомат Мура

Ещё одна модель, которая позволяет "переводить" вход в выход — автомат Мура.

Автомат Мура — это кортеж , где

  •  — конечный входной алфавит;

  •  — конечный выходной алфавит;

  •  — конечное множество состояний;

  •  — стартовое состояние ( );

  •  — функция переходов;

  •  — функция, генерирующая выходное значение.

В нашем определении (как и во многих других) нету финальных состояний. То есть автомат Мура тоже работает до конца входа.

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

Автомат Мура
Рисунок 3. Автомат Мура: 0 — стартовое состояние, {a, b, c, d} — входной алфавит, {X, Y, Z} — выходной алфавит

Автоматы в HDL

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

Обязательно порешайте упражнения.