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

Июль 31, 2022

Главная
Математика
Конечные автоматы

Содержание

2. Существуют задачи выживания, решение которых не может быть обеспечено вентильными схемами. Например. Мышь, управляемая вентильной схемой
3. Учебный пример задачи, не решаемой вентильной схемой: выбор заданного набора предметов из случайного потока. Приведен граф
4. ГРАФ КОНЕЧНОГО АВТОМАТА, РЕШАЮЩЕГО ЗАДАЧУ ВЫБОРА ЗАДАННОГО НАБОРА ПРЕДМЕТОВ (вариант 1) (СЛУЧАЙ ПРОИЗВОЛЬНОГО ПОРЯДКА УКЛАДКИ)
5. ГРАФ КОНЕЧНОГО АВТОМАТА, РЕШАЮЩЕГО ЗАДАЧУ ВЫБОРА ЗАДАННОГО НАБОРА ПРЕДМЕТОВ (вариант 2) (СЛУЧАЙ ПРОИЗВОЛЬНОГО ПОРЯДКА УКЛАДКИ)
6. ПРЕДСТАВЛЕНИЕ КОНЕЧНОГО АВТОМАТА В ВИДЕ ТАБЛИЦЫ ПЕРЕХОДОВ. Таблица состояний автомата Таблица выходов автомата
7. Конечным автоматом называется пятерка S={ X, Y, Q, λ, δ }, где X – конечное множество
8. Реализация конечного автомата. Триггеры
9. Кодировка входного алфавита Кодировка состояний Таблица предикатов КОНКРЕТНАЯ РЕАЛИЗАЦИЯ АВТОМАТА, ОТБИРАЮЩЕГО НАБОРЫ КОСМЕТИКИ
10. ЧЕРНЫЙ ЯЩИК αg, αj, αf, αf, αf, βf, βh, βh, αh, αj, βf, αh, βj, βf,
12. Скачать презентацию

Слайд 2

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

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

Правильно! Памяти и умения ее использовать.
Это реализуется в системах называемых конечными автоматами.

Слайд 3

Учебный пример задачи, не решаемой вентильной схемой: выбор заданного набора предметов

из случайного потока.

Приведен граф конечного автомата, решающего задачу формирования косметического набора для случая заданного порядка укладки предметов.

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

В каждый набор предметы должны укладываться в следующем порядке: духи, тушь и помада.

Слайд 4

ГРАФ КОНЕЧНОГО АВТОМАТА, РЕШАЮЩЕГО ЗАДАЧУ ВЫБОРА ЗАДАННОГО НАБОРА ПРЕДМЕТОВ (вариант 1)
(СЛУЧАЙ

ПРОИЗВОЛЬНОГО ПОРЯДКА УКЛАДКИ)

Слайд 5

ГРАФ КОНЕЧНОГО АВТОМАТА, РЕШАЮЩЕГО ЗАДАЧУ ВЫБОРА ЗАДАННОГО НАБОРА ПРЕДМЕТОВ (вариант 2)
(СЛУЧАЙ

ПРОИЗВОЛЬНОГО ПОРЯДКА УКЛАДКИ)

Слайд 6

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

Слайд 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

Реализация конечного автомата. Триггеры

Слайд 9

Кодировка входного алфавита
Кодировка состояний
Таблица предикатов
КОНКРЕТНАЯ РЕАЛИЗАЦИЯ АВТОМАТА, ОТБИРАЮЩЕГО НАБОРЫ КОСМЕТИКИ

Слайд 10

ЧЕРНЫЙ ЯЩИК
αg, αj, αf, αf, αf, βf, βh, βh, αh, αj,

βf, αh, βj, βf, αh, βj, αf

Все, что можно узнать путем исследования "черного ящика" можно узнать путем перекодирования протокола – все это и нечего больше.

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

Содержание

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

Учебный пример задачи, не решаемой вентильной схемой: выбор заданного набора предметов

ГРАФ КОНЕЧНОГО АВТОМАТА, РЕШАЮЩЕГО ЗАДАЧУ ВЫБОРА ЗАДАННОГО НАБОРА ПРЕДМЕТОВ (вариант 1)(СЛУЧАЙ

ГРАФ КОНЕЧНОГО АВТОМАТА, РЕШАЮЩЕГО ЗАДАЧУ ВЫБОРА ЗАДАННОГО НАБОРА ПРЕДМЕТОВ (вариант 2)(СЛУЧАЙ

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

Конечным автоматом называется пятерка S={ X, Y, Q, λ, δ },где