2014-02-09
662
Теория автоматов — это раздел теоретической кибернетики, в котором система представляется в виде устройства, перерабатывающего дискретную информацию и меняющего свои внутренние состояния лишь в допустимые моменты времени.
Конечный автомат ‑ автомат, у которого множество внутренних состояний и входных сигналов (а следовательно, и множество выходных сигналов) являются конечными множествами.
Абстрактный конечный автомат (Finite automata).
Автомат задаётся F- схемой:
F=< x, y, z, j, y, z0>,
где x,y, z- соответственно конечные множества входных, выходных сигналов (алфавитов) и конечное множество внутренних состояний (алфавита).
z0ÎZ - начальное состояние;
j(z,x) - функция переходов;
y(z,x) - функция выхода.
Автомат 1-ого рода (Мили)
В момент t, будучи в состоянии z(t), автомат способен воспринять сигнал x(t) и выдать сигнал y(t)=y[z(t),x(t)],
переходя в состояние
z(t+1)=j[x(t),z(t)],
z(t)ÎZ; y(t)ÎY; x(t)ÎX. t= 0, 1, …
Автомат 2-ого рода:
z(t+1)= j[x(t),z(t)], t=0,1,2
y(t)=y[z(t),x(t-1)], t=1,2,3
автомат Мура ‑ автомат, для которого
y(t)=y[z(t)], t=0,1,2,…
По числу состояний конечные автоматы бывают с памятью и без памяти.
Автоматы с памятью имеют более одного состояния, а автоматы без памяти (комбинационные или логические схемы) обладают лишь одним состоянием
Комбинационная схема ставит в соответствие каждому входному сигналу x(t) определённый выходной сигнал y(t), т.е. реализует логическую функцию вида:
y(t)=y[x(t)], t=0,1,2,…
Способы задания
Для задания F- автомата необходимо описать все элементы множества F=< x, z, y, j, y, z0>,
т.е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов.
Для задания работы F- автоматов используются табличный, графический и матричный способ.
В табличном способе задания используется таблицы переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы - его состояниям.
Таблица 1 (автомат Мили)
| xj | zk | |||
| z0 | z1 | … | zk | |
| Переходы | ||||
| x1 | j(z0,x1) | j(z1,x1) | … | j(zk,x1) |
| … | ||||
| xL | j(z0 xL) | j(z1, xL) | … | j(zk, xL) |
| Выходы | ||||
| x1 | y(z0,x1) | y(z1,x1) | … | y(zk,x1) |
| … | ||||
| xL | y(z0, xL) | y(z1, xL) | … | y(zk, xL) |
Таблица 2 (автомат Мура)
| xj | zk | |||
| z0 | z1 | … | zk | |
| Переходы | ||||
| x1 | j(z0,x1) | j(z1,x1) | … | j(zk,x1) |
| … | ||||
| xL | j(z0 xL) | j(z1, xL) | … | j(zk, xL) |
| Выходы | ||||
| y(z0) | y(z1) | … | y(zk) |
Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершин дуг графа, соответствующих тем или иным переходам автомата.
Графы автоматов Мили (а) и Мура (б).
Матричное задание конечного автомата.
При этом матрица соединений автомата есть квадратная матрица С=||сij||, строки которой соответствуют исходным состояниям, а столбцы — состояниям перехода. Элемент cij=xk/ys, стоящий на пересечении i-й строки и j-го столбца, в случае автомата Мили соответствует входному сигналу хk, вызывающему переход из состояния zi в состояние zj, и выходному сигналу ys, выдаваемому при этом переходе.
Для F-автомата Мура элемент сij равен входному сигналу хk, вызывающему переход из состояния zi в состояние zj, а выход описывается вектором выходов i- я компонента которого — выходной сигнал, отмечающий состояние zi.
С помощью F-схем описываются узлы и элементы ЭВМ, устройства контроля, регулирования и управления, системы временной и пространственной коммутации в технике обмена информацией.
o Пример 1. Триггерная ячейка
o Пример 2. модель управления часами с цифровой индикацией и 2-мя кнопками.
При разработке информационных систем для бизнес-приложений многие объекты, такие как банковский счет, заказ, поставка могут быть представлены конечным автоматом, с некоторым множеством состояний.
Например:
Входной алфавит - некоторый набор событий, который может произойти с объектом (счет может быть открыт, заблокирован, закрыт, переведен в другой банк и пр.)
Stateflow — пакет моделирования событийно-управляемых систем, основанный на теории конечных автоматов. Предназначен для использования вместе с пакетом моделирования динамических систем Simulink. (компонент системы математического моделирования MATLAB)
В любую Simulink-модель можно вставить Stateflow-диаграмму (SF-диаграмму), которая будет отражать поведение компонентов объекта (или системы) моделирования.
SF-диаграмма является анимационной. По ее выделяющимся цветом блокам и связям можно проследить все стадии работы моделируемой системы или устройства и поставить ее работу в зависимость от тех или иных событий.
