Недетерминированный автомат

При проектировании автоматов часто возникают ситуации, когда для некоторых символов входного алфавита не заданы значения функций выходов и/или переходов. Это приводит к тому, что в таблицах выхода и/или переходов не определены отдельные позиции. В такую позицию можно поместить любой символ выходного алфавита или алфавита состояний. Пусть таблицами 6.21 и 6.22 дано описание недетерминированного автомата.

 

Таблица 6.21.

Таблица 6.22.

текущее состояние

xÎX

текущее состояние

xÎX

x1

x2

…

xn

x1

x2

…

xn

…

…

…

…

…

…

…

…

…

…

qp

ys

*

…

yt

qp

qr

*

…

qt

qr

yi

yj

…

yp

qr

qp

qt

…

qr

qs

yi

*

…

yp

qs

*

qp

…

*

qt

ys

yp

…

yt

qt

qs

qr

…

qp

qu

*

yj

…

yp

qu

qp

qv

…

qt

qv

ys

yj

…

*

qv

*

qv

…

qp

…

…

…

…

…

…

…

…

…

…

 

Эквивалентность состояний автомата определяют по реакции автомата на входную последовательность a=(x₁x_2...x_p).

Если существуют q_i и q_j, для которых значения функций выходов j(q_i;x_k) и j(q_j; x_k) определены для некоторых x_kÎX и они совпадают, или значение одной из функций покрывает безразличную позицию другой или значения обеих функций не определены для некоторых x_kÎX, то состояния q_i и q_j называются неотличимыми. Например, такими парами по таблице 6.21 являются (q_p; q_t), (q_p; q_v), (q_r; q_u), (q_r; q_s), (q_s; q_u), (q_u;q_v).

Если существуют состояния q_i и q_j, значения функции выходов которых различны хотя бы для одного x_kÎX, т. е. j(q_i; x_k)¹j(q_j;x_k), то такие состояния называются отличимыми. Например, такими парами являются (q_p; q_r), (q_p; q_s), (q_p; q_u), (q_r; q_t), (q_r; q_v), (q_s; q_t), (q_s; q_v), (q_t; q_u) и (q_t; q_v).

Если множеству неотличимых пар принадлежат (q_i; q_j), (q_j; q_k) и (q_i; q_k), то {q_i; q_j; q_k} формирует класс неотличимых состояний Q'_i (условие транзитивности). Например, Q'₁={q_r; q_s; q_u}.

Если множеству неотличимых пар принадлежат (q_i; q_j), (q_j; q_k), но не принадлежит (q_i; q_k), то формируются два класса неотличимых состояний {q_i; q_j} и {q_j; q_k}. При этом одно состояние q_j принадлежит двум классам неотличимости. Например, Q'₂={q_p; q_t}, Q'₃={q_p; q_v} и Q'₄={q_u; q_v}.

Выходные последовательности b_i и b_j с неопределенными символами считаются неотличимыми, если в каждой позиции, где выходные символы определены, они совпадают.

Например, неотличимыми являются b₁=(0*1*1*), b₂=(011***), b₃=(*1*01*) и b₄=(***011).

Выходная последовательность b_i=(y₁y₂... y_p) покрывает выходную последовательность b_j=(y₁*...*y_p), в которой могут быть неопределенные символы, если всякий определенный символ в последовательности b_j равен соответствующему символу в слове b_i.

Например, bi=(100100) покрывает bj=(1*0**0) или bk=(**0*0*).

Это условие записывают так: bi³bj.

Если функция переходов определена для всех символов слова a=(x₁x₂...x_p), кроме, возможно, последнего - x_n, то есть q_p= y(...(y(y (q₀;x₁);x₂);...x_p-1), то последовательность a=(x₁x₂...x_p) называется допустимой для автомата, находящегося в состоянии q₀.

Например, для q₀=q_p последовательность a=(x₁x_nx₂x₁x₂x₁) является допустимой, т. к. q_p[1]q_r[2]q_r[3]q_t[4]q_s[5]*[6], а последовательность a=(x₁x_nx₂x₂x_nx₁) - недопустимой, т. к. q_p[1]q_r[2]q_r[3]*[4].

Состояния q_i и q_j называют совместимыми для допустимой последовательности a, если j(q_i; a) неотличима от j(q_j; a).

Если автомат, начав работу в состоянии q_i или q_j, формирует на выходе одинаковые последовательности, то состояния q_i и q_j можно заменить эквивалентным состоянием q.

Например, состояния q_p и qt (см. таблицы) являются совместимыми для входной последовательности a= (x₁x₂x_nx₁x₁x₁):

вход: x₁- x₂- x_n- x₁- x₁- x₁; вход: x₁- x₂- x_n- x₁- x₁- x₁;

q: q_p- q_r- q_t- q_p- q_r- q_p; q: q_t- q_s- q_p- q_t- q_s- *;

выход: y_s- y_j- y_t- y_s- y_i- y_s, выход: y_s- *- y_t- y_s- y_i - *,

то есть b₁=(y_sy_jy_ty_sy_iy_s). то есть b₂=(y_s*y_t y_s y_i*).

При этом последовательность b₁ покрывает последовательность b₂, т. е. b₁>b₂.

Состояния q_r и q_u (cм. таблицы) не являются совместимыми для входной последовательности a= (x₂x₂x₂x_nx₁x₂), так как

вход: x₂- x₂- x₂- x_n- x₁- x₂; вход: x₂ - x₂- x₂ - x_n- x₁- x₂;

q: q_r- q_t- q_r- q_t- q_p- q_r; q: q_u - q_v- q_v - q_v- q_p- q_r;

выход: y_j- y_p- y_j- y_t- y_s- y_j; выход: y_j - yi- y_i - _* - y_s- y_j.

то есть b₁=(y_jy_py_jy_ty_sy_j). то есть b_=(y_jy_iy_i*y_sy_i).

Следовательно, состояния q_r и q_u не эквивалентны.

Для поиска совместимых состояний следует использовать таблицу переходов пар неотличимых состояний. Левый столбец этой таблицы предназначен для указания пар неотличимых состояний. Позициями этой таблицы являются пары состояний, которые определяются по таблице переходов при приеме символа x_kÎX, т.е. (y(q_i; x_k); y(q_j; x_k)). Если одна или обе функции переходов имеют неопределенное значение для x_kÎX, то в соответствующей позиции ставится знак "*".

Пусть таблица переходов пар неотличимых состояний представлена таблицей 6.23.

Таблица 6.23.
неотличимые состояния (qi;qj)	xÎX
x1	x2	…	xn
(qp; qt)ÎQ'2	(qr; qs)	*	...	(qp; qt)
(qp; qv)ÎQ'3	*	*	...	(qp; qt)
(qr; qu)ÎQ'1	(qp; qp)	(qt; qv)	...	(qr; qt)
(qr; qs)ÎQ'1	*	(qp; qt)	...	*
(qs; qu)ÎQ'1	*	(qp; qv)	...	*
(qu; qv)ÎQ'4	*	(qv; qv)	...	(qp; qt)

 

Анализ таблицы показывает, что

· состояния q_p и q_v совместимы, так как при приеме символа x_n переходят в неотличимую пару состояний (q_p; q_t);

· состояния q_r и q_s совместимы, так как. при приеме символа x₂ переходят в неотличимую пару состояний (q_p; q_t);

· состояния q_s и q_u совместимы, так как при приеме символа x₂ переходят в неотличимую пару состояний (q_p; qv);

· состояния q_p и q_t совместимы, так как при приеме символа x₁ переходят в неотличимую пару состояний (q_r; q_s);

· состояния q_u и q_v совместимы, так как при приеме символа x₂ переходят в одно состояние q_v, а при приеме символа x_n переходят в неотличимую пару состояний (q_p; q_t);

· состояния q_r и q_u не совместимы, так как при приеме символа x_n переходят в пару отличимых состояний (q_r; q_t), а при приеме символа x₂ - в пару отличимых состояний (q_t; q_v); следовательно, класс Q'₁ следует разложить на два класса совместимых состояний Q'₅={q_r; q_s} и Q'₆={q_s; q_u}.

Если есть совместимые пары (q_i; q_j), (q_j; q_k) и (q_i; q_k), то по условию транзитивности формируется класс совместимых состояний Q'_i={q_i; q_j; q_k..}. Таких пар в данном примере нет.

Если множеству совместимых пар принадлежат пары (q_i; q_j),

(q_j; q_k) и не принадлежит пара (q_i; q_k), то есть не выполняется условие транзитивности, то формируются два класса совместимых состояний Q'_i= {q_i; q_j..} и Q'_j={q_j; q_k..}. Таких пар в данном примере четыре. Поэтому должно быть сформировано пять классов совместимости: Q'₂={q_p;q_t}, Q'₃={q_p;q_v}, Q'₄={q_u;q_v}, Q'₅={q_r;q_s} и Q'₆=(q_s;q_u}.

Множество совместимых классов называется согласованным, если для любого класса из этого множества и любых его элементов q_i и q_j значения функций переходов y(q_i; x_k) и y(q_j; x_k) принадлежат только одному совместимому классу или одному состоянию для любого символа x_k. В данном примере это условие выполняется (см. таблицу 6.24).

Таблица 6.24.
Совместимые классы Q'i	xÎX
x1	x2	…	xn
Q'2	Q'5	*	...	Q'2
Q'3	*	*	...	Q'2
Q'4	*	Q'7	...	Q'2
Q'5	*	Q'2	*	...
Q'6	*	Q'3	...	*

 

Множество совместимых и согласованных классов называется замкнутым, если любое состояние автомата принадлежит хотя бы одному из этих классов. В данном примере это условие также выполняется.

Замкнутое множество совместимых и согласованных классов называется минимальным, если все внутренние состояния автомата принадлежат минимальному числу согласованных классов. В данном примере минимальный автомат могут представлять три согласованных класса: Q'₂={q_p; q_t}, Q'₄={q_u; qv} и Q'₅={q_r; q_s}. Состояния каждого класса можно представить эквивалентным состоянием.

Пусть q'₁«{q_p; q_t}, q'₂«{q_u; q_v}, q'₃«{q_r; q_s}.

Поведение минимального автомата описано таблицами 6.25 и 6.26.

Таблица 6.25 Таблица 6.26

текущее состояние q'i	xÎX		текущее состояние q'i	xÎX
x1	x2	...	xn		x1	x2	...	xn
q'1	ys	yp	...	yt		q'1	q'3	q'3	...	q'1
q'2	ys	yj	...	yp		q'2	q'3	q'2	...	q'1
q'3	yi	yj	...	yp		q'3	q'1	q'1	...	q'3

 

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

Для проверки эквивалентности заданного недетерминированного и минимального детерминированного автоматов следует рассмотреть их реакцию на допустимую входную последовательность.

Пусть a=(x₁x₂x₁x₂x_nx₁x₂x₁).

Для недетерминированного автомата имеем

вход: x₁ - x₂ - x₁ - x₂ - x_n - x₁ - x₂ - x₁;

q: q_p - q_r - q_t - q_s - q_p - q_t - q_s - q_p;

выход: y_s - y_j - y_s - * - y_t - y_s - * - y_s.

Для минимального автомата имеем:

вход: x₁ - x₂ - x₁ - x₂ - x_n - x₁ - x₂ - x₁;

q: q₁ - q₃ - q₁ - q₃ - q₁ - q₁ - q₃ - q₁;

выход: y_s - y_j - y_s - y_j - y_t - y_s - y_j - y_s.

Так найден минимальный автомат, который покрывает исходный недетерминированный автомат.

Алгоритм минимизации числа внутренних состояний недетерминированного автомата:

шаг 1: выделить в таблице выходов автомата множества неотличимых и отличимых пар по правилу:

"а) если среди множества пар состояний автомата (q_i; q_j)Î(QÄQ) найти такие q_i и q_j, для которых значения функций выходов j(q_i;x_k) и j(q_j;x_k) определены и они совпадают, или значение одной из функций покрывает безразличную позицию другой или значения обеих функций не определены, то пару (q_i; q_j) считать неотличимой;

b) если среди множества пар (q_i; q_j)Î(QÄQ) найти такие q_i и q_j, для которых значения функции выходов j(q_i; x_k) и j(q_j;_xk) различны хотя бы для одного x_kÎX, то пару (q_i; q_j) считать отличимой ";

в результате анализа таблицы 6.21 пары неотличимых состояний есть (q_p; q_t), (q_p; q_v), (q_r; q_u), (q_r; q_s), (q_s; q_u), а пары отличимых состояний - (q_p; q_r), (q_p; q_s), (q_p; q_u), (q_r; q_t), (q_r; q_v), (q_s; q_t), (q_s; q_v), (q_t; q_u), (q_t; q_v).

шаг 2: на множестве пар неотличимых состояний определить классы неотличимых состояний по правилу:

"а) если среди множества пар неотличимых состояний существуют пары (q_i; q_j), (q_j; q_k) и (q_i; q_k), то по условию транзитивности формируют класс неотличимых состояний Q'_i ={q_i; q_j; q_k };

b) если среди множества пар неотличимых состояний существуют пары (q_i; q_j), (q_j; q_k) и не существует пара (q_i; q_k), то формируют два класса неотличимых состояний Q'_l={q_i; q_j} и Q'_k={q_j; q_k}, при этом состояние q_j принадлежит двум классам";

в результате анализа множества неотличимых пар сформированы классы неотличимых состояний Q'₁={q_r; q_s; q_u}, Q'₂={q_p; q_t} и Q'₃={q_p; q_v}; при этом Q'₁ÈQ'₂ÈQ'₃=Q, Q'₁ÇQ'₂=Æ, Q'₁ÆQ'₃=Æ, но Q'₂ÇQ'₃¹Æ;

шаг 3: составить таблицу переходов для пар неотличимых состояний:

"левый столбец таблицы представить парами неотличимых состояний, которые сгруппированы по классам неотличимости; позиции таблицы заполнить по таблице переходов для каждой неотличимой пары (q_i; q_j) и для каждого символа x_kÎX парами значений (y(q_i; x_k);y(q_j; x_k)); если хотя бы одно из значений функции переходов y(q_i;x_k) или y(q_j;x_k) имеет значение "*", то паре (y(q_i;x_k);y(q_j;x_k)) присвоить значение "*"";

шаг 4: на множестве пар неотличимых состояний по таблице переходов определить пары совместимых состояний:

"если для пары неотличимых состояний (q_i; q_j) значения функции переходов (y(q_i; x_k);y(q_j; x_k)) для x_kÎX принадлежат также множеству пар неотличимых состояний (левому столбцу таблицы), то состояния q_i и q_j совместимы, иначе пару (q_i; q_j) удалить из множества пар неотличимых состояний (из левого столбца таблицы)";

в результате анализа можно установить, что совместимыми парами являются (q_p; q_v), (q_r; q_s), (q_s; q_u), (q_p; q_t) и (q_r; q_u).

шаг 5: на множестве пар совместимых состояний найти классы совместимых состояний:

"а) если множеству совместимых пар принадлежат пары (q_i; q_j), (q_j; q_k) и (q_i; q_k), то по условию транзитивности формируют класс совместимых состояний Q'_i={q_i; q_j; qk..};

b) если множеству совместимых пар принадлежат (q_i; q_j), (q_j; q_k) и не принадлежит (q_i; q_k), т.е. не выполняется условие транзитивности, то формируют два класса совместимых состояний Q_'i= {q_i; q_j;...} и Q'_j={q_j; q_k;...}";

в результате анализа множества совместимых пар выявлены классы совместимости Q'₂={q_p; q_t}, Q'3={q_p; q_v}, Q'₄={q_u; q_v},Q'₅={q_r; q_s} и Q'₆=(q_s; q_u}.

шаг 6: найти наименьшее множество совместимых классов, покрывающих все исходные состояния автомата: (Q'₂ÈQ'₄ÈQ'₅) = {q_p; q_r; q_s; q_t; q_u; q_v}.

шаг 7: на множестве классов совместимых состояний, выбранных на шаге 6, найти согласованные состояния:

"если для любого класса наименьшего множества совместимых состояний и любых его элементов q_i и q_j значения функций переходов y(q_i; x_k) и y(q_j; x_k) принадлежат одному совместимому классу для всех символов x_kÎX, то такие классы являются согласованными и следует перейти к шагу 8, иначе перейти к шагу 6 и найти другое наименьшее множество классов совместимых состояний, покрывающее все исходные состояния автомата";

в результате анализа таблицы 6.23 установлено, что все состояния согласованы в минимальном наборе классов совместимых состояний Q'₂, Q'₄, Q'₅;

шаг 8: состояния каждого класса согласованных состояний заместить эквивалентным состоянием: q'₁«{q_p; q_t}, q'₂«{q_p; q_v}, q'₃«{q_u; q_v}, q'₄«{q_r; q_s} и q'₅«{q_s; q_u}; отличимые состояния сохраняют свое значение в описании минимального автомат; составить таблицы переходов и выходов.

Пример: дан недетерминированный автомат M = <X; Y; Q; y; j>, где X={x₁; x₂; x₃; x₄}, Y={0; 1}, Q={q₁; q₂; q₃; q₄; q₅}, функции y и j заданы таблицей. Найти минимальный автомат.

Множество неотличимых пар: (q1; q2), (q1; q3), (q1; q4)), (q1; q5), (q2; q3), (q2; q4), (q3; q4), (q3; q5), (q4; q5). Классы неотличимых состояний:Q’1={q1; q2; q3; q4} и Q’2={q1; q3; q4; q5}.		текущие сост-я	xÎX
	x1	x2	x3	x4
	q1	q2; 0	*; *	q3; *	q2; *
	q2	q3; 0	q5; 1	q2; 0	*; *
	q3	q3; 0	q4; 1	*; *	q5; 0
	q4	*; *	q1; 1	q2; *	*; *
	q5	*; *	*; *	q1;1	*; *

.

Анализ таблицы а) пока- зывает, что для символа "x4" пара неотличимых состояний (q1; q3) перехо- дит в пару отличимых состояний (q2; q5); следовательно, пара (q1; q3) не претен- дует на совместимость, ее следует удалить и составить новую таблицу b).		Таблица а)
	Неотл-е сост-я	xÎX
	x1	x2	x3	x4
	(q1; q2)	(q2; q3)	*	(q2; q3)	*
	(q1; q3)	(q2; q3)	*	*	(q2; q5)
	(q1; q4)	*	*	(q2; q3)	*
	(q1; q5)	*	*	(q1; q3)	*
	(q2; q3)	(q3; q3)	(q4; q5)	*	*
	(q2; q4)	*	(q1; q5)	(q2; q2)	*
	(q3; q4)	*	(q1; q4)	*	*
	(q3; q5)	*	*	*	*
	(q4; q5)	*	*	(q1; q2)	*

 

		Таблица b)
Анализ таблицы b) показы- вает, что для символа "x2" пара неотличимых состоя- ний (q2; q4) переходит в пару отличимых состояний (q1; q5); следовательно, (q2; q4) не претендует на совместимость, ее следует удалить и составить таблицу c).		Неотл-е сост-я	xÎX
	x1	x2	x3	x4
	(q1;q2)	(q2;q3)	*	(q2;q3)	*
	(q1;q4)	*	*	(q2;q3)	*
	(q2;q3)	(q3;q3)	(q4;q5)	*	*
	(q2;q4)	*	(q1;q5)	(q2;q2)	*
	(q3;q4)	*	(q1;q4)	*	*
	(q3;q5)	*	*	*	*
	(q4;q5)	*	*	(q1;q2)	*

 

		Таблица c)
Анализ таблицы c) пока- зывает, что для символа "x2" пара неотличимых состояний (q2; q4) перехо- дит в удаленную пару (q1; q5); следовательно, пару (q2; q4) следует удалить и составить таблицу d).		Неотл-е сост-я	xÎX
	x1	x2	x3	x4
	(q1;q2)	(q2;q3)	*	(q2;q3)	*
	(q1;q4)	*	*	(q2;q3)	*
	(q2;q3)	(q3;q3)	(q4;q5)	*	*
	(q3;q4)	*	(q1;q4)	*	*
	(q3;q5)	*	*	*	*
	(q4;q5)	*	*	(q1;q2)	*

 

		Таблица d)
Анализ таблицы d) показы- вает, что для всех символов входного алфавита пары неотличимых состояний переходят в пары неотли- чимых состояний; cледова- тельно, в левом столбце остались пары совмести- мых состояний..		Неотл-е сост-я	xÎX
	x1	x2	x3	x4
	(q1; q2)	(q2; q3)	*	(q2; q3)	*
	(q1; q4)	*	*	(q2; q3)	*
	(q2; q3)	(q3; q3)	(q4; q5)	*	*
	(q3; q4)	*	(q1; q4)	*	*
	(q3; q5)	*	*	*	*
	(q4; q5)	*	*	(q1; q2)	*

Проверим согласование на различных наборах классов совместимых состояний:

а) пусть Q''₁={q₁; q₂} и Q''₄={q₃; q₄; q₅}.

Таблица е).
Классы состояний	xÎX
x1	x2	x3	x4
Q''1	Q''1; Q''4	*	Q''1; Q''4	*
Q''4	*	Q''1; Q''4	Q''1	*

 

Анализ показывает, что выбранные классы не согласованы, так как для x₁ и x₃ класс совместимых состояний Q''₁ переходит в различные классы Q''₁ и Q''₄.

b) пусть Q''₁={q₁; q₂}, Q''₂={q₁; q₄} и Q''₄₁={q₃;q₅}.

Таблица f)
Классы состояний	xÎX
x1	x2	x3	x4
Q''1	Q''1;Q''41	*	Q''1;Q''41	*
Q''2	*	*	Q''1;Q''41	*
Q''41	*	*	*	*

Анализ показывает, что выбранные классы также не согласованы, так как для x₁ и x₃ класс совместимых состояний Q''₁ переходит в различные классы Q''₁ и Q''₄₁.

c) пусть Q''₁={q₁; q₂}, Q''₃={q₂; q₃} и Q''₄₂={q₄; q₅}.

Таблица g)
Классы состояний	xÎX
x1	x2	x3	x4
Q''1	Q''3	*	Q''3	*
Q''3	Q''3	Q''42	*	*
Q''42	*	*	Q''1	*

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

Введем обозначения состояний, замещающих согласованные классы: q'₁«{q₁; q₂}, q'₂«{q₂; q₃}, q'₃«{q₄; q₅}.

Таблица h)
текущее состояние	xÎX
x1	x2	x3	x4
q'1	q'2; 0	q'3; 1	q'2; 0	q'1; *
q'2	q'2; 0	q'3; 1	q'1; 0	q'3;0
q'3	*; *	q'1; 1	q'1; 1	*; *

Для проверки эквивалентности автоматов подадим на вход каждого из них одинаковую последовательность символов:

а) пусть a= (x₁x₂x₃x₄)

для исходного автомата: для минимального автомата:

вход: x₁- x₂- x₃- x₄; вход: x₁- x₂- x₃- x₄;

q: q₁- q₂- q₅- q₁- q₂; q: q'₁-q'₂- q'₃- q'₁ - q'₁;

выход: 0- 1- 1- *; выход: 0- 1- 1- *;

то есть b=(011*). то есть b=(011*).

 

b) пусть a= (x₄x₃x₂x₁)

для исходного автомата: для минимального автомата:

вход: x₄- x₃- x₂- x₁; вход: x₄- x₃- x₂- x1;

q: q₁- q₂- q₂- q₅- *; q: q'₁- q'₁- q'₂- q'₃- *;

выход: *- 0- 1- *; выход: *- 0 -1- *;

то есть b= (*01*). то есть b= (*01*).

Так подтверждается эквивалентность исходного и минимального недетерминированных автоматов.

Структурный автомат

Если элементарный автомат представляет собой устройство, имеющее один вход и один выход, то последовательное и/или параллельное соединение нескольких автоматов формирует сеть. Под действием входных сигналов происходит изменение внутренних состояний автоматов, что порождает изменение состояния всей сети. При описании сети необходимо также вводить понятие дискретного времени t. Функция y каждого автомата реализует задержку на один такт изменения внутреннего состояния, что формирует задержку изменения состояния всей сети. Совокупность функций j автоматов, принадлежащих сети, формирует выходной сигнал всей сети.

Сеть автоматов, вход которой есть (x₁, x₂,..x_n)ÎXⁿ, а выход - (y₁, y₂, …y_p)ÎY^p, называют структурным автоматом. Структурный автомат содержит m элементарных автоматов с одним входом и одним выходом, множество состояний которых в момент времени t формируют состояние сети (q₁,q₂,..q_m)ÎQ^m.

Одновременное изменение внутренних состояний всех автоматов формирует синхронный режим работы сети. В этом случае состояние сети из m автоматов M₁, M₂,...M_m может быть представлено для каждого момента времени t вектором q[t]=(q₁[t];q₂[t];...q_m[t]). Каждая компонента этого вектора описывает внутреннее состояние соответствующего автомата, то есть q₁ÎQ₁, q₂ÎQ₂,...q_mÎQ_m. Число состояний сети равно произведению числа состояний составляющих его автоматов, так как Q=(Q₁ÄQ₂Ä...ÄQ_m). Поэтому синхронный режим работы сети часто называют произведением автоматов.

Разновременное и последовательное изменение внутренних состояний автоматов формирует асинхронный режим работы сети. Изменение состояния такой сети из m автоматов M₁, M₂,...M_m для каждого момента времени t может быть описано изменением внутреннего состояния только одного автомата, то есть q[t]=q_i[t] где q_iÎQ_i. Число состояний сети равно сумме числа внутренних состояний составляющих его автоматов, так как Q=(Q₁ÈQ₂È...ÈQ_m). Поэтому асинхронный режим работы сети часто называют суммой автоматов.

Все разнообразие соединений автоматов можно рассмотреть на примере двух простых автоматов М₁ и М₂, поведение которых представлено таблицами 6.27 и 6.28.

Таблица 6.27		Таблица 6.28
состояния М1	x1iÎX1		состояния М2	x2jÎX2
x11	x12		x21	x22	x23
q11	q12; y11	q11; y13		q21	q21; y21	q22; y21	q21; y22
q12	q13; y12	q12; y11		q22	q22; y21	q22; y21	q21; y22
q13	q13; y11	q11; y11

6.2.1. Произведение автоматов

При синхронном режиме работы состояния qÎQ автомата М определяются прямым произведение состояний автоматов M₁ и M₂,

т. е. q=(q_1i; q_2j)Î(Q₁ÄQ₂).

Таблица 6.29
q1	q2	q3	q4	q5	q6
(q11; q21)	(q11; q22)	(q12; q21)	(q12; q22)	(q13; q21)	(q13; q22)

⇐ Предыдущая25262728293031323334Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: