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

Если динамическая система дискретна по множеству времен Т и по множествам входов U и выходов Y, то для моделирования таких систем используются конечные автоматы.

Простейший элемент дискретной системы – это реле. Реле – это элемент, входная и выходная величина которого могут принимать лишь конечное число значений (как правило, два или три).

Типичный релейный элемент – это электромеханическое реле, контакты которого могут принимать два устойчивых состояния – замкнутое и разомкнутое.

Все релейные устройства можно разделить на два основных класса: однотактные и многотактные. В однотактных устройствах – выходные сигналы зависят только от входных сигналов в тот же момент времени. Эти устройства называются также устройства без памяти.

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

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

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

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

Конечные автоматы можно представить в виде “черного ящика”, на вход которого подается конечное множество входных сигналов, а с выхода снимается конечное множество выходных сигналов.

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

Конечный автомат представляет собой объект, функционирующий в моменты автоматного времени T = { t ₀ < t ₁ < t ₂ < …}; в каждый момент t_j,·из этой совокупности он находится в одном из возможных состояний , где X – конечноемножество состояний автомата. Моменты автоматного времени t_j называются тактами.

У классического конечного автомата имеется 1 вход и 1 выход. В начальный момент времени t ₀ автомат находится в состоянии x ₀= x (t ₀).

В каждый момент , начиная с t ₀ на вход автомата поступает входной сигнал – одна из букв u входного алфавита U.

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

Автомат без памяти реализует только функцию выхода:

.

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

Автоматы с памятью имеют более одного состояния. Текущее состояние характеризует память системы – т.е. историю его поведения.

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

Во-вторых, в каждый момент автоматного времени на выходе автомата появляется выходной сигнал у (t) – буква выходного алфавита Y, определяемый функцией выходов

Рассматриваемый конечный автомат называется автоматом Мили.

Для автоматов Мура функция выходов имеет другой вид

и называется сдвинутой функцией выходов.

Выход автомата Мура зависит только от внутреннего состояния системы.

Конечный автомат может быть задан при помощи таблиц переходов и выходов.

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

Если в автомат, находящийся в состоянии x ₀, поступает входной сигнал u ₁, то выходной сигнал будет y ₁,а состояние изменится на x ₂.

На пересечениях строк и столбцов таблица переходов находятся значения функции переходов, а на пересечении строк и столбцов матрицы выходов – значения функции выходов.

Автомат может быть описан при помощи ориентированного графа: состояниям автомата соответствуют вершины графа, а стрелки (i, j) показывают переход из состояния x_i всостояние x_{j ,}под влиянием входного сигнала u. Соответствующие сигналы (входные и выходные) записываются вдоль стрелок графа.

На следующем рисунке представлен граф для автомата, заданного выше таблицами переходов и выходов.

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

Пример 1. Рассмотрим работу турникета на входе в метро В первом, «грубом» приближении множество значении входа этой системы имеет два элемента: человек с жетоном (и ₁)и человек без жетона (и ₂),т. е. U= { и ₁, и ₂}. После небольшого размышления становится ясно, что следует включить еще отсутствие пассажира (и ₀), т. е. U= { и ₀, и ₁, и ₂}.Множество значений выхода содержит элементы «открыто» (y ₀) и «закрыто» (y ₁). Таким образом, Y= { y ₁, y ₂}и система является дискретной. В простейшем случае можно пренебречь памятью системы и описывать ее статической моделью, имеющей вид таблицы или графа:

Пример 2. Если нас интересует более детально устройство самого турникета (т.е. системой является турникет), то придется учесть, что входными воздействиями (сигналами) для него являются опускание пятака и прохождение человека через турникет. Таким образом, система имеет два входа, каждый из которых может принимать два значения («есть» или «нет»). Пренебрегая возможностью одновременного опускания жетона и прохождения, вводим три значения входа: и ₀– «нет воздействия», и ₁– «опускание жетона», и ₂–«прохождение». Множество Y можно задать так же, как и в примере 1. Однако теперь значение выхода y (t)не определяется только значением входа u (t), а зависит еще и оттого, был ли опущен жетон раньше, т. е. от значений u (s)при s < t. Система имеет «память». Простейший тип ММ для описания дискретных систем с памятью – это конечный автомат. Для его построения вводится конечное множество внутренних состояний системы X, определяющее «память». В данном случае в X достаточно включить два элемента: Х ₀– «жетон не был брошен», Х ₁– «жетон был брошен». Значения состояния системы в следующий момент времени и выхода в текущий момент зависят от текущих значений состояния и входа, т. е.

x (k+ 1) =F (x (k), u (k)), y (k) =G (x (k), u (k)),

где k –номер момента времени такта. Функцию переходов F (х,и)и функцию выходов G (x, и)можно задать таблично:

Можно также построить графы переходов и выходов: