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

1.

КОНЕЧНЫЕ АВТОМАТЫ

2.

Существуют задачи выживания, решение которых не
может быть обеспечено вентильными схемами.
Например. Мышь, управляемая вентильной схемой
увидела кошку. В естественном ужасе она
поворачивается к ней хвостом чтобы убежать. Но!! Как
только кошка исчезает из поля зрения мышь начинает
спокойно пастись дальше. Чего-то мыши не хватает,
чтобы выжить. Чего?
Правильно! Памяти и умения ее использовать.
Это реализуется в системах называемых конечными
автоматами.

3.

Учебный пример задачи, не решаемой
вентильной схемой: выбор заданного
набора предметов из случайного потока.
П
Д
Т
П
Т
Д
Д
Допустим имеется линия автоматов, которые
занимаются упаковкой косметических наборов,
состоящих из туши, духов и помады. Эти
предметы в произвольном порядке двигаются
по конвейеру. Когда автомат видит нужный
предмет, он кладет его в коробку, и ожидает
поступления другого, требуемого для укладки.
В каждый набор предметы должны
укладываться в следующем порядке: духи,
тушь и помада.
Приведен граф конечного автомата,
решающего задачу формирования
косметического набора для случая
заданного порядка укладки предметов.
Т, П/0
q0
П/1
q2
Т, Д/0
Т/1
Д/1
q1
Д, П/0

4.

ГРАФ КОНЕЧНОГО АВТОМАТА, РЕШАЮЩЕГО ЗАДАЧУ ВЫБОРА
ЗАДАННОГО НАБОРА ПРЕДМЕТОВ (вариант 1)
(СЛУЧАЙ ПРОИЗВОЛЬНОГО ПОРЯДКА УКЛАДКИ)
q0
П
Д
Т
П
q1
q2
П
Т
Д
Т
q3
П
Д
Д
q4
Т
q6
q5
Т, П
Д
П, Д
Т
q0
П
Т, Д

5.

ГРАФ КОНЕЧНОГО АВТОМАТА, РЕШАЮЩЕГО ЗАДАЧУ ВЫБОРА
ЗАДАННОГО НАБОРА ПРЕДМЕТОВ (вариант 2)
(СЛУЧАЙ ПРОИЗВОЛЬНОГО ПОРЯДКА УКЛАДКИ)
П, Д
q5
П
Д
П
Т
q1
Т
q0
Т
Д
П
Т
q4
Д
П
Т, П
q3
Д
П
Д
q2
q6
Т, Д
Т

6.

ПРЕДСТАВЛЕНИЕ КОНЕЧНОГО АВТОМАТА В ВИДЕ
ТАБЛИЦЫ ПЕРЕХОДОВ.
Таблица состояний автомата
Т, П/0
q0
П/1
q2
Т, Д/0
Т/1
Д/1
q1
Д, П/0
q0
q1
q2
Д
q1
q1
q2
Т
q0
q2
q2
П
q0
q1
q0
Таблица выходов автомата
q0
q1
q2
Д
1
0
02
Т
0
1
0
П
0
0
1

7.

Конечным автоматом называется пятерка
S={ X, Y, Q, , },
где
X – конечное множество (множество входов, входной алфавит),
Y – конечное множество (множество выходов, выходной алфавит),
Q – конечное множество (множество внутренних состояний),
: Q X Q – функция перехода,
: Q X Y – функция выхода.
S работает в дискретной шкале времени так, что если в момент t он
находился в состоянии q и воспринимал вход x, то в момент t+1 он
перейдет в состояние (q, x), (q, x) будет его выходом.

8.

Реализация конечного
автомата. Триггеры
вход
1
1
1
1
1
t=0
xm
…
0
0
1
2
3
yk
Вентильная
схема
1
1
B1
B2
…
x1
x2
…
y1 y2
0
0
0
B
триггер
1
Bn
0
4
5
6
0
7
8

9.

КОНКРЕТНАЯ РЕАЛИЗАЦИЯ АВТОМАТА, ОТБИРАЮЩЕГО
НАБОРЫ КОСМЕТИКИ
Таблица предикатов
Кодировка состояний
B1
B2
a
b
B1
B2
Y
B1
B2
q0
0
0
0
1
0
0
1
0
1
q1
0
1
0
1
0
1
0
0
1
q2
1
0
0
1
1
0
0
0
1
1
0
0
0
0
0
0
1
0
0
1
1
1
0
1
0
1
0
0
1
0
1
1
0
0
0
0
0
1
1
0
1
0
0
1
1
1
1
0
1
0
0
Д
Т
Кодировка входного алфавита
a
b
Д
0
1
Т
1
0
П
1
1
П
Y a bB1 B2 ab B1 B2 abB1 B2
B1 ab B1 B2 ab B1 B2
B2 a bB2 bB1 B2

10.

ЧЕРНЫЙ ЯЩИК
g, j, f, f, f, f, h, h, h, j, f, h, j, f, h, j, f
f
g
h
j
fff
j
jjj
ff
hhh
.
hh
ff
f
g
h
j
f
j
j
f
h
.
h
f
Все, что можно узнать путем исследования "черного ящика" можно
узнать путем перекодирования протокола – все это и нечего больше.

11.

Продолжение следует…