РАЗДЕЛ 2
ЭЛЕМЕНТЫ ТЕОРИИ АБСТРАКТНЫХ КОМПОЗИЦИОННЫХ АВТОМАТОВ И ИХ СТРУКТУРНАЯ
РЕАЛИЗАЦИЯ
Поскольку известные модели дискретных устройств, используемые в САПР ЦУУ, не
позволяют адекватно описывать поведение объекта проектирования в части,
динамического введения / устранения задержки в его реакции, предлагаются две
низкоуровневые модели, наделенные этой способностью:
совмещающая свойства автоматов Мили и Мура во времени, и проявляющая те или
иные из них на разных этапах функционирования на одном абстрактном выходе –
CT-автомат [3, 4];
совмещающая свойства автоматов Мили и Мура, и проявляющая те или иные из них,
независимо, в пространстве координат векторного выхода автомата и во времени –
CST-автомат [3, 4].
2.1. Абстрактный CT-автомат
Абстрактный конечный CT-автомат с одним выходом определяется как
пятикомпонентный кортеж
SCT = , (2.1)
где A= A1ИA2 – множество (алфавит) внутренних состояний автомата (A1ЗA2=Ж);
A1 = {a11, a12,…, a1n} – множество (алфавит) состояний типа 1 (A1№Ж), в
состоянии aОA1 автомат SCT ведет себя как автомат Мили;
A2 = {a21, a22,…, a2m} – множество (алфавит) состояний типа 2 (A2№Ж), в
состоянии aОA2 автомат SCT ведет себя как автомат Мура;
X = {x1, x2,…, xf} – множество состояний входа (входной алфавит);
Y={y1,y2,…,yg} – множество состояний выхода (выходной алфавит);
d – функция переходов, реализующая отображение некоторого множества Dd НAґX в
A;
– функция выходов;
l1 – функция выхода, реализующая отображение некоторого множества в ;
l2 – функция выхода, реализующая отображение некоторого множества в .
Закон функционирования CT-автомата определяется системой уравнений
где xОX; yОY; aОA; tОN0 – момент шкалы дискретного времени.
Поскольку СТ-автомат в состоянии aОA1 ведет себя как автомат Мили, а в
состоянии aОA2 – как автомат Мура (это следует из определений функций l и d),
то A1 и A2 будут называться множествами состояний автомата Мили и автомата
Мура, соответственно.
Для полностью определенного абстрактного конечного CT–автомата Dd =AґX, , .
Далее будут рассматриваться только конечные автоматы, поэтому термин “конечный”
будет опущен.
Чтобы задать абстрактный CT–автомат SCT, следует определить все компоненты в
(2.1), т.е. задать множества символов его алфавитов, множество состояний и
описать функции переходов и выходов. Для определения поведения автомата SCT на
интервале дискретного времени [0, tk], tkОN0, 0 ? t ? tk, необходимо задать
начальное состояние автомата a(0) в момент времени t=0. Им может быть любое
состояние из первой проекции области определения функции переходов, т.е.
a(0)ОПр1Dd .
Функции переходов и выходов CT-автомата можно описывать табличным, матричным
способом или графом CT-автомата подобно тому, как описывают функции автоматов
Мили и Мура.
Пример полностью определенного CT-автомата представлен в виде графа (рис. 2.1).
Граф состоит из подграфов I (вершины которого – состояния автомата Мили) и II
(вершины которого – состояния автомата Мура), связанных мостами. Мосты – это
дуги графа, которые соединяют вершины, принадлежащие разным подграфам (I и II).
Такие подграфы будут называться подграфом, соответственно, автомата Мили и
автомата Мура. Дуги, исходящие из вершин подграфа I, отмечены символами
входного и выходного алфавитов, а исходящие из вершин подграфа II – только
входного. Вершины подграфа I отмечены только символами алфавита состояний A1, а
подграфа II – символами алфавита состояний A2 и выхода.
Рис. 2.1. Пример графа CT-автомата
I – подграф автомата Мили, II – подграф автомата Мура,
A={a11, a12, a21, a22}; A1={a11, a12}; A2={a21, a22}; X = {x1, x2, x3}; Y =
{y1, y2, y3}.
Поведение представленного CT-автомата (далее автомата) рассмотрено нами для
последовательности состояний входа x(t)ОX (табл. 2.1). В момент времени t=0
задано начальное состояние автомата a(0)=a11; под воздействием состояния его
входа x(0)=x2: формируется реакция автомата – состояние выхода
y(0)=л(a11, x2)=y3; в момент времени t=1 автомат оказывается в состоянии
a(1)=a12=д(a11, x2). Под воздействием состояния входа автомата x(1)=x1: в
момент времени t=1 формируется реакция автомата – состояние выхода
y(1)=л(a12, x1)=y2; в момент времени t=2 автомат оказывается в состоянии
a(2)=a11=д(a12, x1).
Таблица 2.1
Поведение CT-автомата
6
x(t)
x2
x1
x1
x2
x3
x3
x2
a(t)
a11
a12
a11
a21
a22
a21
a11
y(t)
y3
y2
y1
y2
y3
y2
y3
Под воздействием состояния входа автомата x(2)=x1: в этот момент времени t=2
формируется состояние выхода y(2)=л(a11, x1)=y1; в момент времени t=3 в
результате перехода по мосту, отмеченному символами x1/y1, автомат оказывается
в состоянии a(3)=a21=д(a11, x1) (рис. 2.1). В момент времени t=3 состояние
входа автомата x(3)=x2, однако в силу того, что состояние выхода, определяемое
функцией л2=л(a(3)), зависит только от текущего состояния и не зависит от
состояния входа, реакция на текущее состояние входа x(3)=x2 в данный момент
времени отсутствует. Состояние выхода y(3)=л(a21)=y2 – вторая реакция автомата
на состояние входа x(2)=x1, т.к. a21=д(a11, x1), y2=л(a21), следовательно,
y2=л(д(a11, x1)), то есть y(3)=л(д(a(2), x(2))). Под воздействием состояния
входа автомата x(3)=x2 в момент времени t=4 автомат оказывается в состоянии
a(4)=a22=д(a21, x2). В момент времени t=4 состояние выхода автомата y(4)=y3
является реакцией на его состояние входа x(3)=x2, т.к. a22=д(a21, x2),
y3=л(a22), следовательно y3=л(д(a21, x2)), то есть y(4)=л(д(a(3), x(3))), а
реакция на текущее состояние входа x(4)=x3 в данный момент времени отсутствует.
По
- Киев+380960830922