Similar presentations:
Конечные автоматы
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
Все, что можно узнать путем исследования "черного ящика" можно
узнать путем перекодирования протокола – все это и нечего больше.