Презентация на тему: Конечные автоматы

Конечные автоматы
Конечные автоматы
Определение
Классификация
Конечные автоматы
Классификация
Классификация
Теория автоматов Абстрактный автомат
Теория автоматов Абстрактный автомат
Теория автоматов
Теория автоматов
Теория автоматов
Теория автоматов
Теория автоматов Автомат Мили
Теория автоматов Автомат Мура
Пример
Зададим множества, входящие в описание модели.
Граф-схема алгоритма
Разметка схемы алгоритма для модели Мили
Результат абстрактного синтеза автомата Мили:
Разметка схемы алгоритма для случая КА Мура
Условия переходов КА Мура
Результат абстрактного синтеза автомата Мура
Теория автоматов Абстрактный синтез автоматов
Теория автоматов Абстрактный синтез автоматов
Абстрактный синтез автоматов
Абстрактный синтез автоматов
Теория автоматов Абстрактный синтез автоматов
Метод треугольной матрицы
Результат
Теория автоматов Автомат Мура  Автомат Мили
Теория автоматов Автомат Мили  Автомат Мура
Переход от автомата Мура к автомату Мили
Теория автоматов Алгоритм синтеза конечных автоматов
Функциональные схемы
Теория автоматов С интез конечных автоматов (v.1)
Теория автоматов С интез конечных автоматов (v.1)
Теория автоматов С интез конечных автоматов (v.1)
Теория автоматов С интез конечных автоматов (v.1)
Теория автоматов С интез конечных автоматов (v.1)
Теория автоматов С интез конечных автоматов (v.1)
Теория автоматов С интез конечных автоматов (v.1)
Теория автоматов Таблица переходов С интез конечных автоматов (v.1)
Теория автоматов С интез конечных автоматов (v.1)
Теория автоматов С интез конечных автоматов (v.1)
Микропрограммное управление в АЛУ
Операционное устройство
Алгоритм умножения
Микропрограмма автомата
Микрооперации
Реализация с программируемой логикой
Содержимое ПЗУ
1/52
Средняя оценка: 4.8/5 (всего оценок: 12)
Код скопирован в буфер обмена
Скачать (1136 Кб)
1

Первый слайд презентации: Конечные автоматы

Абстрактные автоматы. Структурные автоматы. Синтез конечных автоматов. Синтез МПА.

Изображение слайда
2

Слайд 2

Разделы курса Алгебра и исчисление высказываний. Логика предикатов Дискретная математика Элементы теории автоматов Элементы теории алгоритмов Анализ и разработка алгоритмов Литература: Агарова О.Ю., Селиванов Ю.В. Математическая логика и теория алгоритмов. Уч. пособие. Гуренко В.В. Введение в теорию автоматов. Уч. пособие. Поляков В.И., Скорубский В.И. Основы теории алгоритмов. Уч. пособие. Сергиевская И.М. Математическая логика и теория алгоритмов. Уч. пособие. Левитин А. Алгоритмы. Введение в разработку и анализ. М. 2006. Ерош И. Л., Сергеев М. Б., Соловьев Н. В. Дискретная математика: Учеб. пособие СПб., 2005

Изображение слайда
3

Слайд 3: Определение

Абстрактным автоматом называют модель, описываемую пятиместным кортежем: А = (X, Y, S, fy, fs), где первые три компонента – непустые множества: X – множество входных сигналов АА, Y – множество выходных сигналов АА, S – множество состояний АА. Два последних компонента кортежа – характеристические функции: fy – функция выходов; fs – функция переходов АА из одного состояния в другое. Если множества X, Y, S – конечные, то такой АА называют конечным автоматом (КА).

Изображение слайда
4

Слайд 4: Классификация

I. По определенности характеристических функций. В автоматах полностью определенных областью определения функций fs и fy является множество всех пар (si, xk) S ϵ X, где si ϵ S, xk ϵ X. В автоматах частично определенных либо обе характеристические функции определены не для всех пар (si, xk). II. По однозначности функции переходов. В детерминированных автоматах выполняется условие однозначности переходов: если АА находится в некотором состоянии si ϵ S, то под воздействием произвольного входного сигнала xk ϵ X автомат может перейти в одно и только одно состояние sj ϵ S, причем ситуация si = sj вовсе не исключается. В автоматах вероятностных при воздействии одного и того же входного сигнала возможны переходы из состояния si в различные состояния из множества S с заданной вероятностью.

Изображение слайда
5

Слайд 5

III. По устойчивости состояний: В устойчивых автоматах выполняется условие устойчивости: если автомат под воздействием входного сигнала xk ϵ X оказался в состоянии si ϵ S, то выход из него и переход в иное состояние возможен только при поступлении на вход автомата другого сигнала xz ϵ X, xz ≠ xk. Если условие устойчивости не выполняется хотя бы для одного состояния sj S, то такой автомат называют неустойчивым. Дальнейшее изложение будем вести, исходя из практических соображений, применительно к полностью определенным, детерминированным и устойчивым конечным автоматам.

Изображение слайда
6

Слайд 6: Классификация

Автоматы → удобный язык для описывания законов взаимодействия сложных систем → метаязык кибернетики (фон Нейман) Можно выделить два основных аспекта «работы» автомата: а) автоматы распознают входные слова, т.е. отвечают на вопрос, принадлежит ли поданное на вход слово данному множеству ( это автоматы- распознаватели ); б) автоматы преобразуют входные слова в выходные, т.е. реализуют автоматные отображения (это автоматы - преобразователи).

Изображение слайда
7

Слайд 7: Классификация

Детерминированные автоматы 1 тип Автоматы с неизменным внутренним состоянием. Комбинационные (логические схемы) 2 тип Автомат, выходной сигнал которого определяется поступившим входным сигналом и его внутренним состоянием. Последовательностные. 3 тип Автомат с внешней неограниченной памятью. Реализовать любой алгоритм преобразования информации Машина Тьюринга.

Изображение слайда
8

Слайд 8: Теория автоматов Абстрактный автомат

Абстрактный автомат – позволяет абстрагироваться от конкретной схемы, можно рассматривать как «черный ящик» Для построения УАЖЛ, используется теория абстрактных конечных автоматов (КА). Для построения используется две базовые модели КА, функционально аналогичные: автомат Мура и автомат Мили. Любой ЦА описывается следующем кортежем: М = {X, Y, A\ S, δ, λ, s 0 }, где X, Y, S – соответственно множества входных, выходных значений ЦА и внутренних состояний.

Изображение слайда
9

Слайд 9: Теория автоматов Абстрактный автомат

Абстрактный автомат – обобщенная схема.

Изображение слайда
10

Слайд 10: Теория автоматов

Автомат Мили. В автомате Мили функция выходов λ определяет значение выходного символа по классической схеме абстрактного автомата. Математическая модель автомата Мили и схема рекуррентных соотношений не отличаются от математической модели и схемы рекуррентных соотношений абстрактного автомата. Законы функционирования : a ( t + 1) = δ [ a ( t ), x ( t )] y ( t ) = λ [ a ( t ), x ( t )] Отображения δ и λ получили названия, соответственно, функции перехода и функции выхода автомата. Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y(t) обнаруживается только при наличии символа во входном канале x(t). Функциональная схема не отличается от схемы абстрактного автомата.

Изображение слайда
11

Слайд 11: Теория автоматов

Автомат Мили. a ( t + 1) = δ [ a ( t ), x ( t )] y ( t ) = λ [ a ( t ), x ( t )] 0 1 2 3 4 5 6 7 8 9

Изображение слайда
12

Слайд 12: Теория автоматов

Автомат Мура. Зависимость выходного сигнала только от состояния автомата представлена в автоматах Мура. В автомате Мура функция выходов определяет значение выходного символа только по одному аргументу — состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе. Законы функционирования : a ( t + 1) = δ [ a ( t ), x ( t )] y ( t ) = λ [ a ( t )] Пример автомата Мура: Очевидно, что автомат Мура можно рассматривать как частный случай автомата Мили.

Изображение слайда
13

Слайд 13: Теория автоматов

Автомат Мура. a ( t + 1) = δ [ a ( t ), x ( t )] y ( t ) = λ [ a ( t )]

Изображение слайда
14

Слайд 14: Теория автоматов Автомат Мили

Граф автомата, заданного приведенными таблицами, переходов и выходов будет иметь вид: δ λ X2/y2

Изображение слайда
15

Слайд 15: Теория автоматов Автомат Мура

Изображение слайда
16

Слайд 16: Пример

«Автомат имеет два входа x1, x2 и один выход y. В начальный момент времени y = 0. На вход подаются сигналы: (x1, x2) = (0,0), (0,1), (1,0) и (1,1). В случае входной комбинации (1,0) на выходе формируется значение 1; если (x1, x2) = (0,1), то выдается y = 2. В остальных случаях y = 0».

Изображение слайда
17

Слайд 17: Зададим множества, входящие в описание модели

X = {(0,0), (0,1), (1,0), (1,1)}, где первый элемент каждой пары соответствует x1, второй элемент – x2. Для краткости запишем: X = {00, 01, 10, 11}. Y = {0, 1, 2}. Множество состояний S видно наглядно, если алгоритм представить в виде граф-схемы алгоритма. Если каждый шаг алгоритма принять за микрокоманду, то схема алгоритма является наглядным изображением микропрограммы автомата как последовательности микрокоманд. Схема алгоритма заданного автомата представлена на рис.

Изображение слайда
18

Слайд 18: Граф-схема алгоритма

Изображение слайда
19

Слайд 19: Разметка схемы алгоритма для модели Мили

Изображение слайда
20

Слайд 20: Результат абстрактного синтеза автомата Мили:

Условие прохода по каждой из ветвей представим в дизъюнктивной нормальной форме (ДНФ):

Изображение слайда
21

Слайд 21: Разметка схемы алгоритма для случая КА Мура

Изображение слайда
22

Слайд 22: Условия переходов КА Мура

Изображение слайда
23

Слайд 23: Результат абстрактного синтеза автомата Мура

Изображение слайда
24

Слайд 24: Теория автоматов Абстрактный синтез автоматов

Задача структурного синтеза состоит в построении схемы автомата минимальной сложности. На первом этапе необходимо получить минимальную структуру абстрактного автомата. Минимизация Будем рассматривать в качестве примера следующий автомат: Входные сигналы: 0, 1. Таблица переходов: Выходные сигналы: 0, 1, 2. S 0 – начальное состояние. : а 8

Изображение слайда
25

Слайд 25: Теория автоматов Абстрактный синтез автоматов

8

Изображение слайда
26

Слайд 26: Абстрактный синтез автоматов

Для упрощения автомата в первую очередь необходимо выделить эквивалентные состояния. Условия эквивалентности Колдуэлла : 1. Условие совпадения выходов. Необходимое условие : внутренние состояния a i и a j называются эквивалентными, если при подаче произвольной входной последовательности с начальными состояниями a i и a j образуются одинаковые выходные последовательности. 2. Условие совпадения следующих состояний. Достаточное условие: если две одинаковые строки выходят в одно и то же следующее состояние, то эти состояния эквивалентны. Для нашего примера : G 1 = {(a 0,a l,a 3,a 5 ),(a 2,a 6,a 8 ),(a 4,a 7 )}

Изображение слайда
27

Слайд 27: Абстрактный синтез автоматов

Далее необходимо рассмотреть все возможные пары состояний для каждого из классов и отбросить те из них, которые переводятся по какому-либо символу входного алфавита за пределы этого класса. Эту процедуру нужно повторять до тех пор, пока следующее множество классов эквивалентности не совпадёт с предыдущем. В нашем примере окончательным будет уже второе разбиение: G 2 = {( a 0 ),( a l, a 5 )( a 3 ),( a 2, a 6, a 8 ),( a 4, a 7 )} Новая таблица переходов:

Изображение слайда
28

Слайд 28: Теория автоматов Абстрактный синтез автоматов

Граф минимизированного автомата:

Изображение слайда
29

Слайд 29: Метод треугольной матрицы

Изображение слайда
30

Слайд 30: Результат

Изображение слайда
31

Слайд 31: Теория автоматов Автомат Мура  Автомат Мили

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

Изображение слайда
32

Слайд 32: Теория автоматов Автомат Мили  Автомат Мура

Переход от автомата Мили к эквивалентному автомату Мура :

Изображение слайда
33

Слайд 33: Переход от автомата Мура к автомату Мили

Изображение слайда
34

Слайд 34: Теория автоматов Алгоритм синтеза конечных автоматов

1 шаг. Построение диаграммы состояний (ДС) ( графа конечного автомата). 2 шаг. Для заданной ДС составляем таблицы переходов и выходов. 3 шаг. Определяем количество Элементов Памяти (ЭП), количество входов и выходов. 4 шаг. Кодируем состояния, входы и выходы конечного автомата. 5 шаг. Составляем по таблице выходов - минимальные функции выходов. 6 шаг. Составляем таблицу возбуждения памяти и функции ВП ( миним.) 7 шаг. Составляем схему электрическую принципиальную для реализации всех полученных логических функций Автомат Мили

Изображение слайда
35

Слайд 35: Функциональные схемы

Изображение слайда
36

Слайд 36: Теория автоматов С интез конечных автоматов (v.1)

1 шаг. Построение диаграммы состояний. Автомат Мили

Изображение слайда
37

Слайд 37: Теория автоматов С интез конечных автоматов (v.1)

2 шаг. Таблицы переходов и выходов. Автомат Мили

Изображение слайда
38

Слайд 38: Теория автоматов С интез конечных автоматов (v.1)

3 шаг. Определение количества состояний, входов и выходов Автомат Мили

Изображение слайда
39

Слайд 39: Теория автоматов С интез конечных автоматов (v.1)

4 шаг. Кодируем состояния, входы и выходы. Автомат Мили

Изображение слайда
40

Слайд 40: Теория автоматов С интез конечных автоматов (v.1)

4 шаг. Кодируем переходы и выходы. Таблица переходов δ Таблица выходов λ Автомат Мили

Изображение слайда
41

Слайд 41: Теория автоматов С интез конечных автоматов (v.1)

5 шаг. Минимизация функций выходов картами Карно. Автомат Мили Х – безразличная переменная

Изображение слайда
42

Слайд 42: Теория автоматов С интез конечных автоматов (v.1)

6 шаг. Функции возбуждения памяти (ВП) строятся на основе таблицы переходов и таблицы истинности триггеров различных типов, которые являются основой элементов памяти (ЭП) конечного автомата. Автомат Мили RS- триггер JK- триггер D- триггер Переход Сигналы ВП

Изображение слайда
43

Слайд 43: Теория автоматов Таблица переходов С интез конечных автоматов (v.1)

6 шаг. Таблица сигналов ВП.

Изображение слайда
44

Слайд 44: Теория автоматов С интез конечных автоматов (v.1)

6 шаг. Минимизация функций ВП (карты Карно). Автомат Мили

Изображение слайда
45

Слайд 45: Теория автоматов С интез конечных автоматов (v.1)

7 шаг. Логическая структура КА

Изображение слайда
46

Слайд 46: Микропрограммное управление в АЛУ

Изображение слайда
47

Слайд 47: Операционное устройство

Умножение 101 R1 Х 011 R3 101 R2 + 101 000 01111 R2R3 СЧ= n = 3

Изображение слайда
48

Слайд 48: Алгоритм умножения

Изображение слайда
49

Слайд 49: Микропрограмма автомата

Изображение слайда
50

Слайд 50: Микрооперации

Изображение слайда
51

Слайд 51: Реализация с программируемой логикой

СС – схема сравнения РМК – регистр микрокоманд СЧА -счетчик адреса ПА – поле адреса ПП – поле признаков перехода ПМО- поле микро- операций

Изображение слайда
52

Последний слайд презентации: Конечные автоматы: Содержимое ПЗУ

Адрес ПЗУ Адрес перехода П – проверка условия перехода П Х 1 Х 2 Микроопера - ции y1y2y3y4y5y6y7 № опера- тора 0 0 0 0 0 - - 0 1 0 0 0 1 0 2 0 0 0 1 0 0 0 0 1 - 1 0 0 0 0 0 0 0 3 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 5 0 0 1 1 0 - - 1 0 0 0 0 0 0 6 0 1 0 0 0 - - 0 0 1 1 1 0 1 7 0 1 0 1 0 0 0 1 1 - - 0 0 0 0 0 0 0 безусловный переход

Изображение слайда