АВТОМАТЫ КАК ДИНАМИЧЕСКИЕ СИСТЕМЫ

Примером конкретной динамической системы является логический автомат [2,20,26]:

А = [X; Y; S; d; l],

X - множество входных слов; Y - множество выходных слов; S - множество слов, характеризующих внутреннее состоя­ние автомата; d, l - характеристические функции: d - функция переходов, l - функция выходов.

Время здесь вводится как система тактовых импульсов, по­даваемых извне: t_n+1 = t_n + Dt, Dt - межтактовый интервал; n - обозначение те­кущего такта; n + 1 - последующего.

Автомат - это с одной стороны устройство, а с другой - ма­тематическая модель поведения логического объекта с памятью или без нее. Как устройство автомат способен выполнять определенные функции без вмешательства человека или при ограниченном его участии. Как математическая модель автомат отражает физические или абстрактные явления самой разнообразной природы ( в тех­нике, психологии, лингвистике, управлении ...).

Поведение логического автомата определяется двумя функ­циями:

d: X ´ S ® S - функцией переходов (по типу отображения j в общей динамической системе);

l : X ´ S ® Y - функцией выходов (аналог h).

Работа конечных логических автоматов определяется тремя множествами : Х;S;Y.

Мощности этих множеств определяют понятие (p,q,r) - ав­томата: p = ½Х½; q = ½Y½; r = ½S½.

Варианты схем, описывающих логический автомат, пред­ставлены в литературе [2,20].

Если длина слов соответственно n, m, k, то имеем p = p_iⁿ, q = q_i^m, r = r_i^k .

Здесь p_i , q_i , r_i - число символов алфавита [2].

Размерность таблиц функций d и l одинакова и равна
½Х½ ´ ½S½ = р ´ q = р_iⁿ ´ q_i^m , т.е. определяется длиной слова (n ´ m) и набора символов в алфавите (р_i и q_i).

Упражнения

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

2. На множествах X = {0, 1, 2, 3}, Y = {0, 1} и S = {0, 1, 2, 3} задайте по своему усмотрению таблицы d и l, как алгебраические операции.

а. Определите длину слов n, m и k при переходе к двузнач­ной системе исчисления слов.

б. Определите параметры (p, q, r) - автомата в данном кон­кретном случае.

в. Постройте карту Карно для логической схемы автомата и определите необходимое число элементов задержки.

2. Создайте схему устройства, поведение которого анало­гично математическому описанию автомата.