|
Читайте также: |
На практике наибольшее распространение получили два класса автоматов - автоматы Мили и Мура. Закон функционирования автомата Мили задаётся уравнениями:
Автоматами Мура называют автоматы, у которых выход зависит только от состояния, и не зависит от значения входа:
Теорема: Для любого автомата Мура существует эквивалентный автомат Мили и наоборот.
Доказательство теоремы построим на преобразовании автомата одного типа в автомат другого типа, на примере конкретных автоматов, описанных с помощью графов.
Необходимость: Докажем, что для любого (полностью определённого) автомата Мура существует эквивалентный ему автомат Мили.
Рассмотрим автомат Мура, описанный в виде графа
Перенесём выходы автомата с вершин графа на входящие ветви графа.
Достаточность: Докажем, что для любого полностью определённого автомата Мили существует эквивалентный ему автомат Мура. Рассмотрим автомат Мили, с заданными алфавитами, описанный в виде графа
Таким образом получим граф, который описывает автомат
Докажем, что автоматы 
и 
эквивалентны. Для этого докажем, что для любого состояния 
автомата существует эквивалентное ему состояние 
автомата и наоборот. Покажем, что для любого состояния множества 
существует эквивалентное из множества 
.
; 
; 
; 
покажем обратное утверждение
; 
; 
; 
; 
; 
; 
В связи с синтезом схем практический интерес представляет задача построения автомата, выполняющего заданный набор преобразований при минимальном числе внутренних состояний.
Дата добавления: 2015-10-28; просмотров: 67 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Тема 18.3. Эквивалентные автоматы | | | Тема 18.5. Примеры синтеза автоматов |