II. МИКРОПОДХОД (до 90 минут)

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

канонической схемы построения автоматов; при этом элементы делят на две группы – функциональные элементы (автоматы с одним состоянием) и элементы памяти. Каноническая схема

состоит из двух функциональных блоков f и g с присоединенными к ним элементами памяти, в качестве которых используются автоматы Мура U_i, i=1…L. Блоки f и g построены из функциональных элементов. При данном способе задания структуру этих блоков не описывают, а задают (например, таблично) реализуемые ими вектор-функции.

f=< f₁(a₁, …, a_m, u₁, …, u_L), …, f_k(a₁, …, a_m, u₁, …, u_L) >:
Q₁´…´Q_L´A ® Z₁´…´Z_L;

g=< g₁(a₁, …, a_m, u₁, …, u_L), …, g_L(a₁, …, a_m, u₁, …, u_L) >:
Q₁´…´Q_L´A ® B,
где А и В -, соответственно, входной и выходной алфавиты канонической схемы. Эта схема задает структурный автомат <A, Q, B, d,l >.

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

q₁(1)=q₀,

q_L(1)=q₀,

q₁(t+1)= f₁(q₁(t), …, q_L(t), a₁(t), …, a_m(t)),

.............................................................

q_L(t+1)= f_L(q₁(t), …, q_L(t), a₁(t), …, a_m(t)),

b₁(t)= g₁(u₁(t), …, u_L(t), a₁(t), …, a_m(t)),

.............................................................

y_k(t+1)= g_k(u₁(t), …, u_L(t), a₁(t), …, a_m(t)),

где t=1, 2, 3… - целочисленный параметр, q₀ÎQ, а функции f_i, (i=1…L), g_j, (i=1…k) реализуются подавтоматами с одним состоянием. Приведенной системе соответствует каноническая схема, в которой все элементы памяти совпадают.

Пример: Пусть U=<A, Q, B, d,l > имеет Q={ q₀ , q₁}, A={ a₀ , a₁, a₂ , a₃}, B={ b₀ , b₁}, а функции d и l определены графом

Каноническую систему уравнений рассматриваемый автомат получает, если закодировать его алфавиты следующим образом:

a₀Þ<0, 0>, a₁Þ<0, 1>, a₂Þ<1, 0>, a₃Þ<1, 1>; q₀Þ<0>, q₁Þ<1>; b₀Þ<0>, b₁Þ<1>,

и построим таблицы соответствий для d и l:

ai	qj(t)	q(t+1)	b(t)	aj	qj(t)	q(t+1)	b(t)
x1	x2

Используя СДНФ имеем следующую систему канонических уравнений:

q(t+1)= `x<sub>1</sub>(t) x<sub>2</sub>(t)q(t) Ú x<sub>1</sub>(t)` x₂(t)q(t) Ú x₁(t) x₂(t)

q(t) Ú x₁(t) x₂(t)q(t); b(t)= x₁(t) x₂(t)q(t)

Упрощая, имеем систему:

q(t+1)= x₁(t)x₂(t) Ú (x₁(t)Ú x₂(t)) q(t); b(t)= x₁(t) x₂(t)q(t),

а соответствующую ей схему

Пример: Каноническая схема логического автомата описывается следующей системой канонических уравнений:

Поведение этого автомата следующее:

Лекция №8.

Анализ КА

Продолжительность: 2 часа (90) минут

Ключевые (основные) вопросы (моменты)

Текст лекции

Дата добавления: 2015-12-01