Слайд 2
![Автомат – дискретный преобразователь информации, который на основе входных сигналов,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-1.jpg)
Автомат – дискретный преобразователь информации, который на основе входных сигналов, поступающих
в дискретные моменты времени, и с учетом своего состояния вырабатывает выходные сигналы и изменяет свое состояние.
Слайд 3
![Под автоматом будем понимать некоторую математическую модель. Вопросы практической реализации](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-2.jpg)
Под автоматом будем понимать некоторую математическую модель. Вопросы практической реализации не
рассматриваются. В связи с этим при построении автоматов будем иметь в виду, что:
Автомат функционирует в абстрактном времени.
Все переходы происходят мгновенно.
Слайд 4
![Автомат представляет собой кортеж: где X – множество входных сигналов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-3.jpg)
Автомат представляет собой кортеж:
где X – множество входных сигналов (входной алфавит),
Y
– множество выходных сигналов (выходной алфавит),
A – множество внутренних состояний,
– функция перехода,
– функция выхода,
- начальное состояние автомата.
Слайд 5
![Законы функционирования автоматов. В зависимости от законов функционирования различают 3](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-4.jpg)
Законы функционирования автоматов.
В зависимости от законов функционирования различают 3 вида автоматов:
1.
Автоматы первого рода, или автоматы Мили:
Слайд 6
![2. Автоматы второго рода](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-5.jpg)
Слайд 7
![Правильные автоматы второго рода, или автоматы Мура: На практике наибольшее](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-6.jpg)
Правильные автоматы второго рода, или автоматы Мура:
На практике наибольшее распространение получили
автоматы Мили и автоматы Мура.
Слайд 8
![Задание автоматов Автоматы могут быть заданы следующими способами: 1. В виде графа Рис. 1 Автомат Мили](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-7.jpg)
Задание автоматов
Автоматы могут быть заданы следующими способами:
1. В виде графа
Рис. 1
Автомат Мили
Слайд 9
![Рис.2 Автомат Мура](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-8.jpg)
Рис.2 Автомат Мура
Слайд 10
![При построении автомата Мили каждая дуга, соединяющая вершины и ,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-9.jpg)
При построении автомата Мили каждая дуга, соединяющая вершины и , имеет
обозначение . Это означает следующее: находясь, в состоянии автомат, отрабатывая входной сигнал , выдает выходной сигнал и переходит в состояние .
Слайд 11
![Так как в автомате Мура выходной сигнал зависит только от](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-10.jpg)
Так как в автомате Мура выходной сигнал зависит только от текущего
состояния , то каждая дуга, соединяющая вершины и , имеет обозначение .
Слайд 12
![2 способ. В виде таблиц перехода и выхода (автомат Мили);](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-11.jpg)
2 способ. В виде таблиц перехода и выхода (автомат Мили); отмеченной
таблицы перехода (автомат Мура).
Автомат Мили описывается с помощью двух таблиц: таблицы перехода и таблицы выхода:
Таблица переходов (ТП) Таблица выходов (ТВ)
Слайд 13
![Автомат Мура описывается с помощью отмеченной таблицы перехода: Таблица переходов (ТП)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-12.jpg)
Автомат Мура описывается с помощью отмеченной таблицы перехода:
Таблица переходов (ТП)
Слайд 14
![ПРИМЕР. Синтезировать автомат, на вход которого подаются монеты номинальной стоимостью](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-13.jpg)
ПРИМЕР.
Синтезировать автомат, на вход которого подаются монеты номинальной стоимостью 1, 2
и 3 копейки, а на выходе автомат выдает билет, если сумма набранных монет составляет 3 копейки, если сумма меньше 3 копеек, то автомат ничего не выдает, если сумма больше 3 копеек, то автомат возвращает деньги.
Слайд 15
![Определим входной, выходной алфавиты и множество внутренних состояний: входной алфавит](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-14.jpg)
Определим входной, выходной алфавиты и множество внутренних состояний:
входной алфавит - монеты
номинальной стоимостью 1, 2 и 3 копейки
выходной алфавит - на выходе возможны выходные символы: Н - ничего; Б - билет; В - возврат.
множество внутренних состояний ,
где - начальное состояние автомата « в автомате ничего нет»;
Слайд 16
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-15.jpg)
Слайд 17
![Граф автомата Мили имеет вид: Рис. 2](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-16.jpg)
Граф автомата Мили имеет вид:
Рис. 2
Слайд 18
![Таблицы перехода и выхода представлены в виде: Таблица переходов (ТП) Таблица выходов (ТВ)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-17.jpg)
Таблицы перехода и выхода представлены в виде:
Таблица переходов (ТП) Таблица выходов (ТВ)
Слайд 19
![3. Автоматная матрица](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-18.jpg)
Слайд 20
![Неопределенным состоянием называется несуществующее состояние. Частичным автоматом называется автомат, в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-19.jpg)
Неопределенным состоянием называется несуществующее состояние.
Частичным автоматом называется автомат, в котором
некоторые состояния в таблице перехода не определены. Для дальнейшего исследования неопределенное состояние некоторым образом доопределяют.
Слайд 21
![Минимизация автоматов Входным словом называется совокупность сигналов, поступающих на вход.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-20.jpg)
Минимизация автоматов
Входным словом называется совокупность сигналов, поступающих на вход.
Выходным словом называются
совокупность сигналов на выходе.
Два автомата называются эквивалентными, если они имеют одинаковый входной и выходной алфавит, и на одинаковые входные слова выдают одинаковые выходные слова.
Слайд 22
![Два состояния одноэквивалентными , если на одинаковое входное слово выдается](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-21.jpg)
Два состояния одноэквивалентными , если на одинаковое входное слово выдается одинаковый
выходной сигнал.
Два состояния k-эквивалентными, если на одинаковое входное слово длиной в k-единиц выдается одинаковый выходной сигнал длиной в k-единиц.
Эквивалентными состояниями называются k-эквивалентные состояния для любых k.
Слайд 23
![Эквивалентные состояния объединяются в класс эквивалентности. Минимальный автомат – это](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-22.jpg)
Эквивалентные состояния объединяются в класс эквивалентности.
Минимальный автомат – это автомат, состоящий
из наименьшего числа состояний, каждое из которых является классом эквивалентности исходного автомата.
Слайд 24
![Алгоритм минимизации автомата Мили 1. По таблице выхода находятся состояния](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-23.jpg)
Алгоритм минимизации автомата Мили
1. По таблице выхода находятся состояния с одинаковыми
выходными сигналами. Данные состояния объединяются в класс одноэквивалентных состояний. Проводится перекодировка.
Слайд 25
![2. По таблице перехода определяются классы двухэквивалентных состояний: для любого](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-24.jpg)
2. По таблице перехода определяются классы двухэквивалентных состояний: для любого класса
выделяется состояние, которое на одинаковый входной сигнал переходит в одинаковое состояние. Объединяем двухэквивалентные состояния в классы двухэквивалентных состояний. Проводится перекодировка.
Слайд 26
![3. Алгоритм выполняется, пока в классах k-эквивалентных состояний не находятся](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-25.jpg)
3. Алгоритм выполняется, пока в классах k-эквивалентных состояний не находятся одинаковые
состояния.
4. Вводятся новые состояния, соответствующие классам эквивалентных состояний.
5. С учетом новых состояний переписываются таблицы перехода и выхода.
Слайд 27
![ПРИМЕР Пусть задан автомат Мили Таблица выходов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-26.jpg)
ПРИМЕР
Пусть задан автомат Мили
Таблица выходов
Слайд 28
![Таблица переходов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-27.jpg)
Слайд 29
![Определяем класс одноэквивалентных состояний по таблице выхода Таблица выходов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-28.jpg)
Определяем класс одноэквивалентных состояний по таблице выхода
Таблица выходов
Слайд 30
![Таблица переходов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-29.jpg)
Слайд 31
![Перекодируем состояния по полученным классам Таблица переходов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-30.jpg)
Перекодируем состояния по полученным классам
Таблица переходов
Слайд 32
![Выделяем внутри каждого из классов одинаковые состояния, тем самым определяя классы двухэквивалентных состояний Таблица переходов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-31.jpg)
Выделяем внутри каждого из классов одинаковые состояния, тем самым определяя классы
двухэквивалентных состояний
Таблица переходов
Слайд 33
![Таблица переходов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-32.jpg)
Слайд 34
![Таблица переходов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-33.jpg)
Слайд 35
![Таблица переходов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-34.jpg)
Слайд 36
![Минимизированный автомат Мили в новых состояниях имеет вид Таблица переходов Таблица выходов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-35.jpg)
Минимизированный автомат Мили в новых состояниях имеет вид
Таблица переходов
Таблица выходов
Слайд 37
![Особенности минимизации автомата Мура. Автомат Мура минимизируется аналогично минимизации автомата](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-36.jpg)
Особенности минимизации автомата Мура.
Автомат Мура минимизируется аналогично минимизации автомата Мили за
исключением первого шага. Выделение класса одноэквивалентных состояний осуществляется по строке выходов отмеченной таблицы переходов автомата Мура.
Слайд 38
![Минимизация частичных автоматов. Для того, чтобы провести минимизацию частичных автоматов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-37.jpg)
Минимизация частичных автоматов.
Для того, чтобы провести минимизацию частичных автоматов неопределенное состояние
доопределяется самостоятельно. Далее минимизация автоматов осуществляется по вышеизложенному алгоритму.
Слайд 39
![Переход от автомата Мили к автомату Мура Автоматы Мили и](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-38.jpg)
Переход от автомата Мили к автомату Мура
Автоматы Мили и автоматы Мура
отличаются функцией выхода.
Автомат Мили:
Автомат Мура:
Слайд 40
![То есть произвольному состоянию автомата Мили и входному сигналу соответствует](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-39.jpg)
То есть произвольному состоянию автомата Мили и входному сигналу соответствует состояние
автомата Мура:
При этом начальные состояния автоматов Мили и Мура совпадают:
Слайд 41
![Таким образом, можно перекодировать таблицу перехода автомата Мили и составить отмеченную таблицу переходов автомата Мура.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-40.jpg)
Таким образом, можно перекодировать таблицу перехода автомата Мили и составить отмеченную
таблицу переходов автомата Мура.
Слайд 42
![Перекодируем матрицу перехода автомата Мили:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-41.jpg)
Перекодируем матрицу перехода автомата Мили:
Слайд 43
![Составляем таблицу перехода автомата Мура.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-42.jpg)
Составляем таблицу перехода автомата Мура.
Слайд 44
![При составлении таблицы перехода автомата Мили рассуждаем следующим образом: состояние](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-43.jpg)
При составлении таблицы перехода автомата Мили рассуждаем следующим образом: состояние автомата
Мура соответствует состоянию автомата Мили , следовательно, столбец состояния автомата Мура совпадает со столбцом состояния автомата Мили .
Слайд 45
![Так как в автомате Мура произвольному состоянию соответствует некоторый выходной](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-44.jpg)
Так как в автомате Мура произвольному состоянию соответствует некоторый выходной сигнал,
то строка выхода отмеченной таблицы перехода автомата Мура однозначно определяется таблицей выхода автомата Мили (состоянию соответствует
выходной сигнал ; - )
Слайд 46
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-45.jpg)
Слайд 47
![Выходной сигнал, соответствующий состоянию , выбирается произвольно.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-46.jpg)
Выходной сигнал, соответствующий состоянию , выбирается произвольно.
Слайд 48
![Если автомат Мили содержит m-состояний и n входных символов, то](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-47.jpg)
Если автомат Мили содержит m-состояний и n входных символов, то количество
состояний автомата Мура определяется по формуле:
Слайд 49
![Переход от автомата Мура к автомату Мили Переход от автомата](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-48.jpg)
Переход от автомата Мура к автомату Мили
Переход от автомата Мура к
автомату Мили заключается в построении таблицы выходов. Построение состоит в подстановке выходных сигналов, отмечающих состояния в отмеченной таблице переходов, вместо состояний, в которые автомат переходит.
Слайд 50
![Тем самым, если говорить в терминах графов, выходные сигналы от](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-49.jpg)
Тем самым, если говорить в терминах графов, выходные сигналы от состояний
переносятся на дуги, которые в эти состояния заходят.
А таблица переходов автомата Мили получается из отмеченной таблицы переходов автомата Мура отбрасыванием строки выходов.
Слайд 51
![ПРИМЕР Пусть задан автомат Мура в виде отмеченной таблицы перехода](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-50.jpg)
ПРИМЕР
Пусть задан автомат Мура в виде отмеченной таблицы перехода
Слайд 52
![Данный автомат может быть представлен в виде графа:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-51.jpg)
Данный автомат может быть представлен в виде графа:
Слайд 53
![Автомат Мили будет иметь вид: в виде таблиц перехода и выхода Таблица переходов Таблица выходов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-52.jpg)
Автомат Мили будет иметь вид:
в виде таблиц перехода и выхода
Таблица
переходов Таблица выходов
Слайд 54
![в виде графа](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349659/slide-53.jpg)