🗊Презентация Способы задания автоматов

Категория: Математика
Нажмите для полного просмотра!
Способы задания автоматов, слайд №1Способы задания автоматов, слайд №2Способы задания автоматов, слайд №3Способы задания автоматов, слайд №4Способы задания автоматов, слайд №5Способы задания автоматов, слайд №6Способы задания автоматов, слайд №7Способы задания автоматов, слайд №8Способы задания автоматов, слайд №9Способы задания автоматов, слайд №10Способы задания автоматов, слайд №11Способы задания автоматов, слайд №12Способы задания автоматов, слайд №13Способы задания автоматов, слайд №14Способы задания автоматов, слайд №15Способы задания автоматов, слайд №16Способы задания автоматов, слайд №17Способы задания автоматов, слайд №18Способы задания автоматов, слайд №19Способы задания автоматов, слайд №20

Содержание

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

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


Слайд 1






Способы задания автоматов
Описание слайда:
Способы задания автоматов

Слайд 2





Табличный способ задания автомата Мили
Описание слайда:
Табличный способ задания автомата Мили

Слайд 3





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

Слайд 4





Пример
X={x1, x2}, Y={y1, y2}, S={s1, s2, s3}
Описание слайда:
Пример X={x1, x2}, Y={y1, y2}, S={s1, s2, s3}

Слайд 5





Пример автомата
X = {положительный стимул (1), отрицательный стимул (0)}
Y = {есть реакция(1), нет реакции (0)}
S = {есть реакция на последний положительный стимул (1), нет реакции на последний положительный стимул (0)}.
Функция λ: XS Y 
0,00
0,10
1,01
1,10
Функция δ: XS S 
0,00
0,11
1,01
1,10
Описание слайда:
Пример автомата X = {положительный стимул (1), отрицательный стимул (0)} Y = {есть реакция(1), нет реакции (0)} S = {есть реакция на последний положительный стимул (1), нет реакции на последний положительный стимул (0)}. Функция λ: XS Y 0,00 0,10 1,01 1,10 Функция δ: XS S 0,00 0,11 1,01 1,10

Слайд 6





Пример
Описание слайда:
Пример

Слайд 7





Табличный способ задания автомата Мура
Описание слайда:
Табличный способ задания автомата Мура

Слайд 8





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

Слайд 9





Пример
X={x1, x2}, Y={y1, y2, y3}, S={s1, s2, s3 ,s4, s5}
Описание слайда:
Пример X={x1, x2}, Y={y1, y2, y3}, S={s1, s2, s3 ,s4, s5}

Слайд 10





Автомат для задержки двоичного сигнала на один такт
Описание слайда:
Автомат для задержки двоичного сигнала на один такт

Слайд 11





Автомат для проверки двоичной последовательности на четность
Описание слайда:
Автомат для проверки двоичной последовательности на четность

Слайд 12





Автомат для задержки сигнала на два такта
Автомат имеет четыре состояния, закодированных двумя двоичными разрядами:
s0 = 00; 
s1 = 01; 
s2 = 10; 
s3 = 11.
Первая цифра кода состояния показывает, какой сигнал выдает автомат
Вторая цифра кода показывает, под действием какого сигнала автомат приходит в данное состояние.
Описание слайда:
Автомат для задержки сигнала на два такта Автомат имеет четыре состояния, закодированных двумя двоичными разрядами: s0 = 00; s1 = 01; s2 = 10; s3 = 11. Первая цифра кода состояния показывает, какой сигнал выдает автомат Вторая цифра кода показывает, под действием какого сигнала автомат приходит в данное состояние.

Слайд 13





Конечный детерминированный автомат (КДА)
КДА – конечный автомат, в котором имеется полная определенность переходов из всех состояний в зависимости от входных сигналов 
Иными словами, под действием одного и того же сигнала КДА не может переходить из любого рассматриваемого состояния в различные состояния.
Описание слайда:
Конечный детерминированный автомат (КДА) КДА – конечный автомат, в котором имеется полная определенность переходов из всех состояний в зависимости от входных сигналов Иными словами, под действием одного и того же сигнала КДА не может переходить из любого рассматриваемого состояния в различные состояния.

Слайд 14





Устойчивость состояния
Состояние автомата  si  называется устойчивым, если для любого входного сигнала  хк , такого, что δ(sj , xk) = si , справедливо соотношение: δ(si , xk) = si , где  sj – состояние, предшествующее si. 
Иными словами, автомат не изменяет своего состояния при повторении на следующем такте сигнала, приведшего его в состояние  si .
Описание слайда:
Устойчивость состояния Состояние автомата si называется устойчивым, если для любого входного сигнала хк , такого, что δ(sj , xk) = si , справедливо соотношение: δ(si , xk) = si , где sj – состояние, предшествующее si. Иными словами, автомат не изменяет своего состояния при повторении на следующем такте сигнала, приведшего его в состояние si .

Слайд 15





Синхронные и асинхронные автоматы
Автомат называется асинхронным, если каждое его состояние  si  S (i = 1, … , n) устойчиво;
Устойчивость состояний в асинхронных автоматах достигается введением специальных сигналов синхронизации.
Если в автомате есть хотя бы одно неустойчивое состояние, он называется синхронным.
Описание слайда:
Синхронные и асинхронные автоматы Автомат называется асинхронным, если каждое его состояние si  S (i = 1, … , n) устойчиво; Устойчивость состояний в асинхронных автоматах достигается введением специальных сигналов синхронизации. Если в автомате есть хотя бы одно неустойчивое состояние, он называется синхронным.

Слайд 16





Изолированный синхронный автомат
Изолированный (автономный) автомат – автомат, на входе которого присутствует сигнал, имеющий постоянное значение, что эквивалентно "отключению" входа. 
Если изолированный КДА является синхронным, переходы из одного состояния в другое возможны, но при этом исключены разветвления путей. 
Следовательно, изолированный КДА неизбежно должен попасть в состояние, в котором уже находился ранее, и на диаграммах переходов обязательно будет присутствовать поглощающее состояние или цикл.
Описание слайда:
Изолированный синхронный автомат Изолированный (автономный) автомат – автомат, на входе которого присутствует сигнал, имеющий постоянное значение, что эквивалентно "отключению" входа. Если изолированный КДА является синхронным, переходы из одного состояния в другое возможны, но при этом исключены разветвления путей. Следовательно, изолированный КДА неизбежно должен попасть в состояние, в котором уже находился ранее, и на диаграммах переходов обязательно будет присутствовать поглощающее состояние или цикл.

Слайд 17





Примеры изолированного синхронного КДА
Описание слайда:
Примеры изолированного синхронного КДА

Слайд 18





Проблема умножения
Теорема. Никакой конечный автомат не может перемножать пары чисел с произвольно большим числом разрядов. 
Доказательство. 
Предположим противное: существует автомат A, перемножающий пары двоичных чисел с произвольно большим числом разрядов (система счисления может быть любой без ограничения общности).
Используем для опровержения последнего утверждения частный случай: оба сомножителя равны 2n . 
В этом случае каждый из сомножителей содержит единицу, за которой следуют n нулей;
Результат умножения (2n  2n = 22n) содержит единицу  и  2n  нулей.
Описание слайда:
Проблема умножения Теорема. Никакой конечный автомат не может перемножать пары чисел с произвольно большим числом разрядов. Доказательство. Предположим противное: существует автомат A, перемножающий пары двоичных чисел с произвольно большим числом разрядов (система счисления может быть любой без ограничения общности). Используем для опровержения последнего утверждения частный случай: оба сомножителя равны 2n . В этом случае каждый из сомножителей содержит единицу, за которой следуют n нулей; Результат умножения (2n  2n = 22n) содержит единицу и 2n нулей.

Слайд 19





Проблема умножения
Пусть пары разрядов сомножителей подаются последовательно, начиная с младших разрядов 
Чтобы автомат правильно работал, он должен после прекращения подачи сомножителей 
добавить к уже выработанным  n + 1 нулям еще  n – 1  нулей, 
добавить в заключение единицу.  
После прекращения подачи сомножителей автомат будет работать как изолированный.
Описание слайда:
Проблема умножения Пусть пары разрядов сомножителей подаются последовательно, начиная с младших разрядов Чтобы автомат правильно работал, он должен после прекращения подачи сомножителей добавить к уже выработанным n + 1 нулям еще n – 1 нулей, добавить в заключение единицу. После прекращения подачи сомножителей автомат будет работать как изолированный.

Слайд 20





Проблема умножения
Если изолированный автомат  A  имеет  k  состояний и способен выработать на выходе подряд  n  нулей, где n  k, то это означает, что он находится в поглощающем состоянии или вошел в цикл. 
Следовательно, он уже не сможет выработать единицу. 
Так как всегда возможно сделать значение  n  таким, что  n1k , правильный результат при выполнении указанного неравенства не будет получен и, следовательно, предположение о существовании автомата  A  приводит к противоречию. 
Теорема доказана.
Описание слайда:
Проблема умножения Если изолированный автомат A имеет k состояний и способен выработать на выходе подряд n нулей, где n  k, то это означает, что он находится в поглощающем состоянии или вошел в цикл. Следовательно, он уже не сможет выработать единицу. Так как всегда возможно сделать значение n таким, что n1k , правильный результат при выполнении указанного неравенства не будет получен и, следовательно, предположение о существовании автомата A приводит к противоречию. Теорема доказана.



Похожие презентации
Mypresentation.ru
Загрузить презентацию