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