Автоматы и алгоритмы. Комбинационные схемы и конечные автоматы

Лекция 1
Комбинационные схемы и конечные автоматы

Комбинационная схема (КС) –это функциональная схема, комбинация сигналов на выходе которой однозначно определяется комбинацией сигналов на ее входе.
Такой способ обработки сигналов называют комбинационным.
На практике выходные сигналы зависят от сигналов, поступивших в предыдущие моменты времени.
Возникает необходимость хранить поступившие сигналы с специальном устройстве – блоке памяти.
Автоматы с памятью

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

Автомат, моделирующий родителя,
имеет четыре состояния {s0, ... ,s3}, и два входных сигнала - оценки, полученные сыном в школе: {2, 5}. Начиная с начального состояния s0 (оно помечено входной стрелкой), автомат под воздействием входных сигналов переходит из одного состояния в другое и выдает выходные сигналы - реакции на входы.
Выходы автомата {y0, ..., y5} будем интерпретировать как действия родителя так:
у0: - брать ремень;
у1: - ругать сына;
у2: - успокаивать сына;
у3: - надеяться;
у4: - радоваться;
у5: - ликовать.
Сына, получившего одну и ту же оценку - двойку, ожидает дома совершенно различная реакция в зависимости от предыстории его учебы. Например, после третьей двойки в истории 2,2,2 сына встретят ремнем, а в истории 2,2,5,2 - будут успокаивать. Каждая предыстория определяет текущее состояние автомата. Таким образом, текущее состояние представляет все то, что автомат знает о прошлом с точки зрения его будущего поведения - реакций на последующие входы.

§2. Определение конечного автомата

S
Входной
канал
Выходной
канал
Все множества конечны –
Конечный автомат.
Описание работы автомата
X(1)
Входная лента
x(1)
Входная лента
Выходная лента
q(0)
q(1)

Функции перехода и выхода:

Принципиальная модель структуры конечного автомата
- комбинационная часть
- контур
обратной
связи
?
?
память

Способы задания автоматов. Логические автоматы.

2. Способ задания в виде диаграммы Мура (ДМ) .
ДМ- это орграф, в котором каждая вершина помечена одним из состояний (количество вершин равно количеству состояний). Из каждой вершины выходит столько стрелок, сколько символов в алфавите X.
qk
xl/ym
. . .
. . .
qp

Пример. Автомат задан в виде АТ

Зададим автомат с помощью ДМ:

3. Задание автомата с помощью системы канонических уравнений (СКУ)

0
1
0
1
1
АТ для
логического
Автомата ⤳
Таблица
истинности
⤶

§2. Определение логического автомата.

§3. Примеры автоматов
1. Элемент единичной задержки (З).
X={0,1}=Y=Q
x(t) y(t)=x(t-1)
З

2. Последовательный арифметический сумматор.
a и b – двоичные –n- разрядные двоичные числа.
a+b=y?
X={00,01,10,11}; Y=Q={0,1}

0
1
01/0
11/1
10/1
01/0
00/0