Канонические уравнения автомата

 

Если в момент времени t =1, 2,... на вход автомата А=(X, Q, Y, j, y) последовательно подаются входные символы x(t)ÎX и при этом автомат находится в состоянии q(t)ÎQ, то под воздействием символа x(t) автомат перейдет в новое состояние q(t+1)ÎQ и выдаст выходной сигнал y(t).

Величины x(t), y(t), q(t), q(t+1) связаны между собой следующими уравнениями:

  t =1, 2, …, n, …

Эти уравнения называются каноническими уравнениями автомата А. При задании автомата системой булевых функций эти уравнения запи­сываются в координатной форме:

z ₁(t+1)= j ₁(x₁(t), …, x_k(t), z₁(t), …, z_r(t))

…

z_r (t+1)= j _r (x₁(t), …, x_k(t), z₁(t), …, z_r(t))

y ₁(t)= y ₁(x₁(t), …, x_k(t), z₁(t), …, z_r(t))

…

y_s (t)= y _s (x₁(t), …, x_k(t), z₁(t), …, z_r(t))

t =1, 2, …

Для построения канонических уравнений автомата A необходимо для данной булевой функции найти минимальную ДНФ (дизъюнктивную нормальную форму), которая, вообще говоря, определяется неоднозначно. Аналитический алгоритм построения этой ДНФ следующий:

1. Для данной функции f(x₁, …, x_n) строим свершенную конъюнктивную нормальную форму (СКНФ).

2. В построенной СКНФ раскрываем скобки, используя правило:

(А Ú В)Ù(С ÚD)=AÙCÚBÙ C Ú A Ù D ÚВÙD.

3. Полученное выражение упрощаем, применяя тождества вида:

K₁ÙK₂ÚK₁=K₁, KÚK=K, KÚ0=K, KÙ =0,

KÚ1=1, KÙ1=K, KÙK=K, KÚ =1.

В результате получим сокращенную ДНФ, являющуюся дизъюнкцией всех простых импликат данной функции f(x₁, …, x_n).

Для рассмотренных выше примеров автоматов канонические уравнения задаются следующими формулами:

пример 1:   t =1, 2, …

пример 2:   t =1, 2, …

пример 3:   t =1, 2, …

пример 4:   t =1, 2, …

В качестве иллюстрации изложенного выше алгоритма рассмотрим пример 3.

Таблица истинности системы булевых функций следующая:

x1	x2	z	j	y
0	0	0	0	0
0	0	1	1	1
0	1	0	1	1
0	1	1	1	1
1	0	0	1	1
1	0	1	1	1
1	1	0	0	0
1	1	1	1	1

 

1. Строим СКНФ функции j (x₁, x₂, z). Так как эта функция задана набором своих значений =01111101, то ее СКНФ будет иметь вид (x₁Úx₂Úz)Ù( Ú Úz).

2. Раскрываем скобки: (x₁Úx₂Úz)Ù Ú(x₁Úx₂Úz)Ù Ú(x₁Úx₂Úz)Ùz=

=x₁Ù Úx₂Ù ÚzÙ Úx₁Ù Úx₂Ù ÚzÙ Úx₁ÙzÚx₂ÙzÚzÙz.

Упрощаем последнее выражение:

0Ú Ùx₂Ù ÙzÚ Ù Ú0Ú ÙzÚx₁ÙzÚx₂ÙzÚz=

= Ùx₂Úx₁Ù Ú z ( Úx₂)Ú z ( Úx₁)Úz= Ùx₂Úx₁Ù Ú z.

Таким образом, получим z(t+1)= (t)Ùx₂(t)Úx₁(t)Ù (t)Ú z (t).

Аналогично строится функция y(t). При этом из таблицы истинности выписываем набор значений функции y (x₁, x₂, z): =01111101, который совпадает с набором значений функции j (x₁, x₂,

ЗАДАНИЕ № 02-18 НА РАЗРАБОТКУ ПРОЕКТА  КА

СИСТЕМЫ ТРАНСПОРТИРОВАНИЯ

 СЫПУЧЕГО МАТЕРИАЛА

ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ

Разработать проект конечного автомата (КА) системы транспортирования сыпучего материала из бункеров «А» в бункера «Б» с помощью транспортеров-конвейеров Тк. Из бункеров А на транспортер выгрузка осуществляется  через шиберные заслонки Ш.