Шпаргалка по "Схемотехнике управляющих систем"

a₁

a₂

a₃

z₁

a₂

a₃

a₃

z₂

a₃

a₁

a₁

a₁

a₂

a₃

z₁

w₂

w₁

w₂

z₂

w₂

w₁

w₁

a₁

a₂

a₃

z₁

a₂/w₁

a₃/w₁

a₃/w₂

z₂

a₃/w₂

a₁/w₁

a₁/w₁

41.Конечные  автоматы.

Конечный автомат (КА) можно представить в виде шестикомпонентного кортежа - ? вектора для описания системы состоящей из n независимых признаков S=(A,Z,W,δ,λ,a₁),

Где A=множество состояний автомата {a₁,a₂…a_M} или алфавит состояний,

Z=представляет собой множество входных сигналов {z₁,z₂…z_K} или входной алфавит,

W={w₁,w₂…w_G} множество выходных сигналов или выходной алфавит,

δ- функция перехода КА из состояния a_i  в a_j под действием входного сигнала z_f,

λ- функция выхода, она определяет значение выходного сигнала w_g находящегося в состоянии a_i , под действием входного сигнала z_k,

a₁- начальное состояние автомата.

Автоматы являются конечными.

Классификация КА.

1.Автомат называют  Инициальным, если определено  начальное состояние автомата.

2.Автомат может быть  Детерминированным  (ДА) и Не Детерминированным  (НДА).

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

НДА - является вероятным  автоматом, у которого задается вероятность  перехода из состояния a_i  в a_j и выдаст с приходом z_f выходной сигнал.

Пример: регистры и счетчики (mod=10)

Все конечные автоматы делятся  на два типа:

Абстрактные – используются для описания и анализа работы автомата.

Структурные – для  проектирования на основе модели конечного  автомата некого цифрового устройства.

42.Понятие абстрактного  автомата. Особенности его функционирования.

Система рассматривается как черный ящик, который находиться в некотором состоянии a^t_m в текущий момент времени t, такой автомат имеет 1 эквивалентный вход и 1 эквивалентный выход. На вход автомата поступает буква алфавита z^t_f в момент t и в соответствии с функцией выхода λ, данный автомат выдаст букву выходного алфавита w^t_b=[a^t_m,z^t_f].

При этом сам автомат  переходит из состояния a_i в a_j , это состояние определяет функциональный переход автомата a^t+1_j=δ[a^t_m,z^t_f]. В зависимости от особенности функционирования автоматов различают две различные модели:

1.Автомат Мили,

2.Автомат Мура.

Автомат Мили.

Функционирует: выходной сигнал такого автомата определяется текущим состоянием автомата и входным  сигналом, поступившим на вход автомата  в данный момент времени w(t)=λ[a_m(t),z_f(t)]. Последующее состояние автомата будет определяться функцией перехода и значением входного сигнала a(t+1)=δ[a_m(t),z_f(t)]. Автомат функционирует в дискретный момент времени (такты, целыми цифрами)

Автомат Мили – инициальный  у него всегда известно начальное состояние a(0)=a₁

Автомат Мура.

Входной сигнал автомата Мура определяется состоянием автомата и не зависит от значения входного сигнала. Поэтому выходной сигнал будет  определяться от текущего состояния  автомата w(t)=λ[a_m(t)], последующим состоянием функционального перехода a(t+1)=δ[a_m(t),z₁(t)], t=0,1,2,3. Автомат Мура – инициальный, т.к. начальное состояние всегда определено.

43.Автоматы Мили и  Мура.

Автомат Мили.

Функционирует: выходной сигнал такого автомата определяется текущим состоянием автомата и входным сигналом, поступившим на вход автомата  в данный момент времени w(t)=λ[a_m(t),z_f(t)]. Последующее состояние автомата будет определяться функцией перехода и значением входного сигнала a(t+1)=δ[a_m(t),z_f(t)]. Автомат функционирует в дискретный момент времени (такты, целыми цифрами)

Автомат Мили – инициальный  у него всегда известно начальное  состояние a(0)=a₁

Автомат Мура.

Входной сигнал автомата Мура определяется состоянием автомата и не зависит от значения входного сигнала. Поэтому выходной сигнал будет определяться от текущего состояния автомата w(t)=λ[a_m(t)], последующим состоянием функционального перехода a(t+1)=δ[a_m(t),z₁(t)], t=0,1,2,3. Автомат Мура – инициальный, т.к. начальное состояние всегда определено.

44.Способы задания  автоматов Мили.

Для того, что бы описать  автомат, надо описать конечное множество A,Z,W,δ,λ,a₁. Другими словами требуется определить область функционального перехода  и выхода δ>λ. Описать входные сигналы, осуществляющие переход КА из a_i в a_j ,описать функцию выхода, которая будет выдавать букву алфавита в текущий момент t. Поскольку алфавит входных и выходных сигналов является конечным, то  функция перехода λ и функция выхода всегда можно представить в виде таблицы или графа.

1.Табличный способ:

Автомат Мили задается таблицей переходов и выходов. В таблице  переходов и выходов каждый столбец  соответствует определенному состоянию  автомата, каждая строка определенному  входному сигналу. В таблице переходов  на пересечении строки и столбца записывается новое состояние автомата в которое он перешел из состояние a_i под действием входного сигнала z_k. В таблице выходов, на пересечении строки и столбца записываются значения выходного сигнала автомата, которое он выдает, находясь в состоянии a_i под действием входного сигнала z_k.

Пример: Задан автомат, описывающий 3 состояния

A={a₁,a₂,a₃}Z_вх={z₁,z₂}W_вых={w₁,w₂}

Таблица перехода автомата (δ(a,z)).                Таблица выходов (λ(a,z)).

Совмещенная таблица  переходов и выходов.

2.С помощью  графа:

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

Граф автомата Мили: