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

Нажмите для полного просмотра!

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №2

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №3

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №4

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №5

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №6

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №7

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №8

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №9

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №10

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №11

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №12

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №13

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №14

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №15

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №16

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №17

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №18

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №19

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №20

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №21

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №22

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №23

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №24

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №25

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №26

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №27

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №28

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №29

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №30

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №31

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №32

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №33

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №34

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №35

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №36

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №37

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №38

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №39

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №40

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №41

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №42

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №43

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №44

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №45

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №46

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №47

Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА, слайд №48

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Конечные автоматы. Абстрактные и структурные автоматы. Синтез конечных автоматов и МПА. Доклад-сообщение содержит 48 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Классификация

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

Слайд 14

Описание слайда:

Слайд 15

Описание слайда:

Пример «Автомат имеет два входа 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».

Слайд 16

Описание слайда:

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