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

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

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

jq(t + l) = (p(x(i); q(t)), ,_ло

\y(t) = V(*(f);g(f)), * ’

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

Zx(t + 1) = ф1 (*!(*), ...,x_k{t),zx(t),...,z_r(t))

Zr(t "Ь 1) фг (Xl(f), —»^l(Oj —9 ^г(О)

yi(t) = Vi (*l(*)> ...,X_k(t), Zl(t), ...,z_r(t))

Vs (^l(i)> ■■•9 ^l(0» —9 Z_r{t))

t = 1,2,...

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

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

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

(AV В) Л (С V D) = А Л С V В Л С V А Л D V В Л D.

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

К_г Л К₂ УК_Х =Кх; KVK = K; KVO = K; К ЛК = 0; КА1 = 1;

К Л1 = К; КлК = К\ K\JK= 1.

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

Гг(/ + 1) = x(t),

!«/(*) = z(t),

Г2(£ + 1) = JCi(t) Л Х2(£) V Хх(£) Л z(t) V X₂(f) Л 2(f), \y{t) = Xi(t) © X₂(f) © 2(0,

z(£ + 1) = Xi(t) Л x₂(f) V Xi(0 A x₂(0 v z(t), y(t) = Щ0 A x₂(0 V хДО Л Хг(£) V 2(f),

Д

£ = 1,2,...

t= 1,2,...

пример 3:

пример 2:

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

Z

Пример 1:

x(£ + 1) = 2x(f) V xi(f) Л хг(0 A 22(f),

• * = 1,2,...

  пример 4:

  2i(f + 1) = z₂(f) V xftf) A x₂(0 a z7(£),

• yi(0 = Zi(t) V Xx(£) Л хДО A 22(f), ,Уг(£) = z₂(0 V Xl(0 A x₂(0 A zi(0,

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

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

Х\	х2	г	ф	¥
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. Строим СКНФ функции ф(хх,х₂, z). Так как эта функция задана набором своих значений ф = 01111101, то ее СКНФ будет иметь вид

(xi V х₂ V z) Л (хТ V Х2 V z).

2. Раскрываем скобки

(Хх V Х₂ V 2) Л XI V (Хх V Х₂ V 2) Л х₂ V (хх V Х₂ V 2) Л 2 =

= XxAXxVx₂AXxV2AxxVXiAX₂VX₂Ax₂'VZAX₂VXxA2Vx₂A2V2A2. Упрощаем последнее выражение: 0 V Хх Л Х₂ Л Хх Л 2 V Хх Л х₂ V 0 V Х₂ Л 2 V Хх Л 2 V Х₂ Л 2 V 2 =

= Хх Л Х₂ V Хх Л Х2 V 2(х2 V Х₂) V 2(хх V Хх) V 2 = Хх Л Х₂ V Хх Л Х₂ V 2.

Таким образом, получим z(t + 1) = jcj(f) Л x₂(f) V хх(0 Л х7(£) V z(t). Аналогично строится функция y(t). При этом из таблицы истинности выписываем набор значений функции \j/(xx, x₂,z)\j7 = 01111101, который совпадает с набором значений функции ф(хх, х₂, z).

*

В таблице символами * отмечены наборы переменных х\, xz, Z\, Z2, на ко­торых функции (pi, фг, Vi, ф2 не определены. Положим значения функций фъ ф2> фъ ¥2» на этих наборах равными 1.

МАТРИЦЫ

50. Основные понятия

51. Действия над матрицами

ОПРЕДЕЛИТЕЛИ

52. Основные понятия

53. Свойства определителей

НЕВЫРОЖДЕННЫЕ МАТРИЦЫ

54. Основные понятия

55. Обратная матрица

56. Ранг матрицы

СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ

57. Основные понятия

58. Решение систем линейных уравнений.

59. Теорема Кронекера-Капелли

СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ

60. Основные понятия

61. Решение невырожденных линейных систем. Формулы Крамера

СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ

62. Основные понятия

63. Решение систем линейных уравнений методом Гаусса

64. СИСТЕМЫ ЛИНЕЙНЫХ ОДНОРОДНЫХ УРАВНЕНИЙ