🗊 Презентация Конечный автомат и его описание

Категория: Образование
Нажмите для полного просмотра!
Конечный автомат и его описание, слайд №1 Конечный автомат и его описание, слайд №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 Конечный автомат и его описание, слайд №49 Конечный автомат и его описание, слайд №50 Конечный автомат и его описание, слайд №51 Конечный автомат и его описание, слайд №52 Конечный автомат и его описание, слайд №53 Конечный автомат и его описание, слайд №54 Конечный автомат и его описание, слайд №55 Конечный автомат и его описание, слайд №56 Конечный автомат и его описание, слайд №57 Конечный автомат и его описание, слайд №58 Конечный автомат и его описание, слайд №59 Конечный автомат и его описание, слайд №60 Конечный автомат и его описание, слайд №61 Конечный автомат и его описание, слайд №62 Конечный автомат и его описание, слайд №63 Конечный автомат и его описание, слайд №64 Конечный автомат и его описание, слайд №65 Конечный автомат и его описание, слайд №66 Конечный автомат и его описание, слайд №67 Конечный автомат и его описание, слайд №68 Конечный автомат и его описание, слайд №69
Скачать

Содержание ▲

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

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

Слайд 1


Тема 7. Конечный автомат и его описание
Описание слайда:
Тема 7. Конечный автомат и его описание

Слайд 2


7.1 Автомат с памятью До сих пор рассматривались устройства, не обладающие памятью. Такие устройства в любой момент времени на любую комбинацию...
Описание слайда:
7.1 Автомат с памятью До сих пор рассматривались устройства, не обладающие памятью. Такие устройства в любой момент времени на любую комбинацию входных двоичных сигналов реагируют однозначно, т. е. каждой комбинации двоичных сигналов на входе устройства соответствует определенная комбинация двоичных сигналов на выходе независимо от того, какие сигналы приходили на вход раньше. Отсюда происходят названия «комбинационный автомат» или «комбинационная схема».

Слайд 3


Общепринятой моделью поведения такого устройства является система булевых функций. Комбинации двоичных сигналов иногда удобно обозначать абстрактными...
Описание слайда:
Общепринятой моделью поведения такого устройства является система булевых функций. Комбинации двоичных сигналов иногда удобно обозначать абстрактными символами или буквами некоторого заданного алфавита. Пусть имеется входной алфавит А = {a1, a2, … , a} и выходной алфавит В = {b1, b2, … , b}. Тогда общий вид описания поведения комбина-ционного автомата можно представить таблицей. Эта таблица является аналогом таблицы истинности. Она полностью определяет алгоритм функционирования заданного устройства. Общепринятой моделью поведения такого устройства является система булевых функций. Комбинации двоичных сигналов иногда удобно обозначать абстрактными символами или буквами некоторого заданного алфавита. Пусть имеется входной алфавит А = {a1, a2, … , a} и выходной алфавит В = {b1, b2, … , b}. Тогда общий вид описания поведения комбина-ционного автомата можно представить таблицей. Эта таблица является аналогом таблицы истинности. Она полностью определяет алгоритм функционирования заданного устройства.

Слайд 4


Пример задания комбинационного автомата ,где bij В
Описание слайда:
Пример задания комбинационного автомата ,где bij В

Слайд 5


Часто алгоритм функционирования устройства бывает таким, что простым соответствием вида таблицы его задать невозможно. Для его описания необходимо...
Описание слайда:
Часто алгоритм функционирования устройства бывает таким, что простым соответствием вида таблицы его задать невозможно. Для его описания необходимо ввести время, и работа устройства рассматривается во времени. Время носит дискретный характер, т. е. течение времени представляется как последовательность моментов. В любой момент времени устройство принимает сигнал на входе и выдает сигнал на выходе. В различные моменты устройство может реагировать на один и тот же входной сигнал по-разному. Часто алгоритм функционирования устройства бывает таким, что простым соответствием вида таблицы его задать невозможно. Для его описания необходимо ввести время, и работа устройства рассматривается во времени. Время носит дискретный характер, т. е. течение времени представляется как последовательность моментов. В любой момент времени устройство принимает сигнал на входе и выдает сигнал на выходе. В различные моменты устройство может реагировать на один и тот же входной сигнал по-разному.

Слайд 6


Пусть, например, на вход устройства с входным и выходным алфавитами А = {a1, a2, а3, a4} и В = {b1, b2, b3} пришла последовательность сигналов Пусть,...
Описание слайда:
Пусть, например, на вход устройства с входным и выходным алфавитами А = {a1, a2, а3, a4} и В = {b1, b2, b3} пришла последовательность сигналов Пусть, например, на вход устройства с входным и выходным алфавитами А = {a1, a2, а3, a4} и В = {b1, b2, b3} пришла последовательность сигналов a1 a1 а3 a2 a2 а4 a3, а на выходе наблюдается последователь-ность сигналов b2 b3 b2 b1 b3 b2 b1.

Слайд 7


В первый момент времени устройство на входной сигнал а1 реагировало выходным сигналом b2, а во второй момент на тот же сигнал – сигналом b3. На...
Описание слайда:
В первый момент времени устройство на входной сигнал а1 реагировало выходным сигналом b2, а во второй момент на тот же сигнал – сигналом b3. На сигналы а2 и а3 в разные моменты оно реагировало также по-разному, т. е. поведение устройства нельзя описать тем же способом, что использовался для описания поведения комбинационного автомата. В первый момент времени устройство на входной сигнал а1 реагировало выходным сигналом b2, а во второй момент на тот же сигнал – сигналом b3. На сигналы а2 и а3 в разные моменты оно реагировало также по-разному, т. е. поведение устройства нельзя описать тем же способом, что использовался для описания поведения комбинационного автомата.

Слайд 8


Эта неоднозначность устраняется, если ввести понятие внутреннего состояния или просто состояния. Тогда то, что устройство реагирует на один и тот же...
Описание слайда:
Эта неоднозначность устраняется, если ввести понятие внутреннего состояния или просто состояния. Тогда то, что устройство реагирует на один и тот же сигнал в разные моменты по-разному, можно объяснить так, что оно находится при этом в разных состояниях. Приняв входной сигнал, устройство выдает выходной сигнал и может перейти в другое состояние. Эта неоднозначность устраняется, если ввести понятие внутреннего состояния или просто состояния. Тогда то, что устройство реагирует на один и тот же сигнал в разные моменты по-разному, можно объяснить так, что оно находится при этом в разных состояниях. Приняв входной сигнал, устройство выдает выходной сигнал и может перейти в другое состояние.

Слайд 9


Состояния образуют множество Q  {q1, q2, … , q}. Тогда алгоритм функционирования устройства можно представить совокупностью строк вида Состояния...
Описание слайда:
Состояния образуют множество Q  {q1, q2, … , q}. Тогда алгоритм функционирования устройства можно представить совокупностью строк вида Состояния образуют множество Q  {q1, q2, … , q}. Тогда алгоритм функционирования устройства можно представить совокупностью строк вида (ai, qj)  (qs, bt), где ai  А, bt  В, qj, qs  Q. Устройство, поведение которого можно задать в таком виде, носит название «автомат с памятью» или «последовательностный автомат». Последний термин заключает в себе смысл отображения входной последовательности в другую.

Слайд 10


Соответствие (ai, qj)  (qs, bt) можно задать таблицей, где фактически представлены две функции, определенные на множестве A  Q. Областью значений...
Описание слайда:
Соответствие (ai, qj)  (qs, bt) можно задать таблицей, где фактически представлены две функции, определенные на множестве A  Q. Областью значений одной функции является множество Q, другой функции – множество В. Соответствие (ai, qj)  (qs, bt) можно задать таблицей, где фактически представлены две функции, определенные на множестве A  Q. Областью значений одной функции является множество Q, другой функции – множество В.

Слайд 11


Моделью описанного устройства является конечный автомат, представляющий собой совокупность следующих объектов: Моделью описанного устройства является...
Описание слайда:
Моделью описанного устройства является конечный автомат, представляющий собой совокупность следующих объектов: Моделью описанного устройства является конечный автомат, представляющий собой совокупность следующих объектов: А = {a1, a2, … , a} – множество входных символов, или входной алфавит; В = {b1, b2, … , b} – множество выходных символов, или выходной алфавит; Q  {q1, q2, … , q} – множество состояний, или внутренний алфавит;  : A  Q  Q – функция переходов;  : A  Q  В – функция выходов.

Слайд 12


Для конечного автомата используется обозначение (A, B, Q,  ). Слово «конечный» подчеркивает, что все три множества, входящие в состав данной...
Описание слайда:
Для конечного автомата используется обозначение (A, B, Q,  ). Слово «конечный» подчеркивает, что все три множества, входящие в состав данной модели, конечны. В том виде, в каком эта модель здесь представлена, она носит название «автомат Мили». Другой разновидностью данной модели является автомат Мура, отличающийся от автомата Мили только тем, что функция выходов не зависит от входного символа, т. е. представляет собой отображение  : Q  В. Для конечного автомата используется обозначение (A, B, Q,  ). Слово «конечный» подчеркивает, что все три множества, входящие в состав данной модели, конечны. В том виде, в каком эта модель здесь представлена, она носит название «автомат Мили». Другой разновидностью данной модели является автомат Мура, отличающийся от автомата Мили только тем, что функция выходов не зависит от входного символа, т. е. представляет собой отображение  : Q  В.

Слайд 13


Значением функции (a, q) является состояние q+, в которое переходит автомат из состояния q, если на вход его подан символ а. Значением функции (a,...
Описание слайда:
Значением функции (a, q) является состояние q+, в которое переходит автомат из состояния q, если на вход его подан символ а. Значением функции (a, q) является выходной символ, выдаваемый автоматом в состоянии q при поступлении на его вход символа а, а значением функции (q) автомата Мура – выходной символ b, который выдает автомат, находясь в состоянии q. Если значения функций (a, q) и (a, q) определены для любой пары значений аргументов а и q, а в модели Мура функция (q) определена для всех значений q, то автомат является полностью определенным, или полным автоматом. Иногда приходится иметь дело с не полностью определенным, или частичным автоматом, у которого эти функции могут быть определены не везде. Значением функции (a, q) является состояние q+, в которое переходит автомат из состояния q, если на вход его подан символ а. Значением функции (a, q) является выходной символ, выдаваемый автоматом в состоянии q при поступлении на его вход символа а, а значением функции (q) автомата Мура – выходной символ b, который выдает автомат, находясь в состоянии q. Если значения функций (a, q) и (a, q) определены для любой пары значений аргументов а и q, а в модели Мура функция (q) определена для всех значений q, то автомат является полностью определенным, или полным автоматом. Иногда приходится иметь дело с не полностью определенным, или частичным автоматом, у которого эти функции могут быть определены не везде.

Слайд 14


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

Слайд 15


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

Слайд 16


В асинхронном автомате переход из состояния в состояние происходит за некоторый конечный промежуток времени, в течение которого не должен меняться...
Описание слайда:
В асинхронном автомате переход из состояния в состояние происходит за некоторый конечный промежуток времени, в течение которого не должен меняться входной сигнал. При действии любого входного сигнала автомат приходит в некоторое устойчивое состояние, из которого он не выходит до конца действия данного сигнала В асинхронном автомате переход из состояния в состояние происходит за некоторый конечный промежуток времени, в течение которого не должен меняться входной сигнал. При действии любого входного сигнала автомат приходит в некоторое устойчивое состояние, из которого он не выходит до конца действия данного сигнала

Слайд 17


При этом должно выполняться требование прямого перехода, которое формально выражается следующим образом: если (a, qi) = qj, то (a, qj) = qj. Иногда...
Описание слайда:
При этом должно выполняться требование прямого перехода, которое формально выражается следующим образом: если (a, qi) = qj, то (a, qj) = qj. Иногда допускается выполнение следующей цепочки переходов: При этом должно выполняться требование прямого перехода, которое формально выражается следующим образом: если (a, qi) = qj, то (a, qj) = qj. Иногда допускается выполнение следующей цепочки переходов: (a, qi) = qr, (a, qr) = qs, … , (a, qt) = qj, (a, qj) = qj.

Слайд 18


Конечный автомат и его описание, слайд №18
Описание слайда:

Слайд 19


Конечный автомат и его описание, слайд №19
Описание слайда:

Слайд 20


Конечный автомат и его описание, слайд №20
Описание слайда:

Слайд 21


Конечный автомат и его описание, слайд №21
Описание слайда:

Слайд 22


Конечный автомат и его описание, слайд №22
Описание слайда:

Слайд 23


Конечный автомат и его описание, слайд №23
Описание слайда:

Слайд 24


Конечный автомат и его описание, слайд №24
Описание слайда:

Слайд 25


Конечный автомат и его описание, слайд №25
Описание слайда:

Слайд 26


Конечный автомат и его описание, слайд №26
Описание слайда:

Слайд 27


Конечный автомат и его описание, слайд №27
Описание слайда:

Слайд 28


Конечный автомат и его описание, слайд №28
Описание слайда:

Слайд 29


Конечный автомат и его описание, слайд №29
Описание слайда:

Слайд 30


Конечный автомат и его описание, слайд №30
Описание слайда:

Слайд 31


Конечный автомат и его описание, слайд №31
Описание слайда:

Слайд 32


Конечный автомат и его описание, слайд №32
Описание слайда:

Слайд 33


Конечный автомат и его описание, слайд №33
Описание слайда:

Слайд 34


Конечный автомат и его описание, слайд №34
Описание слайда:

Слайд 35


Конечный автомат и его описание, слайд №35
Описание слайда:

Слайд 36


Конечный автомат и его описание, слайд №36
Описание слайда:

Слайд 37


Конечный автомат и его описание, слайд №37
Описание слайда:

Слайд 38


Конечный автомат и его описание, слайд №38
Описание слайда:

Слайд 39


Конечный автомат и его описание, слайд №39
Описание слайда:

Слайд 40


Конечный автомат и его описание, слайд №40
Описание слайда:

Слайд 41


Конечный автомат и его описание, слайд №41
Описание слайда:

Слайд 42


Конечный автомат и его описание, слайд №42
Описание слайда:

Слайд 43


Конечный автомат и его описание, слайд №43
Описание слайда:

Слайд 44


Конечный автомат и его описание, слайд №44
Описание слайда:

Слайд 45


Конечный автомат и его описание, слайд №45
Описание слайда:

Слайд 46


Конечный автомат и его описание, слайд №46
Описание слайда:

Слайд 47


Конечный автомат и его описание, слайд №47
Описание слайда:

Слайд 48


Конечный автомат и его описание, слайд №48
Описание слайда:

Слайд 49


Конечный автомат и его описание, слайд №49
Описание слайда:

Слайд 50


Конечный автомат и его описание, слайд №50
Описание слайда:

Слайд 51


Конечный автомат и его описание, слайд №51
Описание слайда:

Слайд 52


Конечный автомат и его описание, слайд №52
Описание слайда:

Слайд 53


Конечный автомат и его описание, слайд №53
Описание слайда:

Слайд 54


Конечный автомат и его описание, слайд №54
Описание слайда:

Слайд 55


Конечный автомат и его описание, слайд №55
Описание слайда:

Слайд 56


Конечный автомат и его описание, слайд №56
Описание слайда:

Слайд 57


Конечный автомат и его описание, слайд №57
Описание слайда:

Слайд 58


Конечный автомат и его описание, слайд №58
Описание слайда:

Слайд 59


Конечный автомат и его описание, слайд №59
Описание слайда:

Слайд 60


Конечный автомат и его описание, слайд №60
Описание слайда:

Слайд 61


Конечный автомат и его описание, слайд №61
Описание слайда:

Слайд 62


Конечный автомат и его описание, слайд №62
Описание слайда:

Слайд 63


Конечный автомат и его описание, слайд №63
Описание слайда:

Слайд 64


Конечный автомат и его описание, слайд №64
Описание слайда:

Слайд 65


Конечный автомат и его описание, слайд №65
Описание слайда:

Слайд 66


Конечный автомат и его описание, слайд №66
Описание слайда:

Слайд 67


Конечный автомат и его описание, слайд №67
Описание слайда:

Слайд 68


Конечный автомат и его описание, слайд №68
Описание слайда:

Слайд 69


Конечный автомат и его описание, слайд №69
Описание слайда:

Скачать

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