Типы конечных автоматов
1) по закону функционирования ЦА делятся на автоматы 1-го рода (автоматы Мили) и ЦА 2-го рода. Последние автоматы в случае, когда нет явной зависимости от входных сигналов x(t), являются автоматами Мура. Видимо, целесообразнее по первому критерию автоматы делить на автоматы Мили и Мура;
В автомате Мили функция выходов j определяет значение выходного символа по классической схеме абстрактного автомата. Математическая модель автомата Мили и схема рекуррентных соотношений не отличаются от математической модели и схемы рекуррентных соотношений абстрактного автомата, т.е.
(1.12)
(1.13)
Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y[t] обнаруживается только при наличии символа во входном канале x[t].
Рис. 1.3. Функциональная схема автомата Мили.
В автомате Мура функция j определяет значение выходного символа только по одному аргументу - состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе. Математическая модель и схема рекуррентных соотношений автомата Мура имеют вид:
(1.14)
(1.15)
Особенностью автомата Мура является то, что символ y[t] в выходном канале существует все время пока автомат находится в состоянии q[t].
Минимальный автомат - это автомат, имеющий наименьшее возможное количество состояний и реализующий заданную функцию выходов.
Два состояния автомата называются 1-эквивалентными, если, находясь в любом из этих состояний, автомат на один и тот же входной сигнал (входное слово длиной в 1) выдает один и тот же выходной сигнал. Два состояния автомата называются К- эквивалентными, если, начиная с любого из этих состояний, автомат на любые одинаковые слова длины К выдает одинаковые выходные слова (также длины К). Если два состояния К- эквивалентны для любых К, то их называют (просто) эквивалентными. Множество попарно эквивалентных состояний образует класс эквивалентности.
Смысл минимизации состоит в выявлении классов эквивалентности и замене каждого класса одним состоянием. Процедура минимизации состоит в следующем:
1. По таблице выходов автомата Мили (или по первой строке отмеченной таблице переходов автомата Мура) находятся состояния, имеющие одинаковые столбцы (отмеченные одинаковыми выходными сигналами) – это 1-эквивалентные состояния.
2. Далее используется таблица переходов. Все состояния, входящие в 1-эквивалентный класс, которые под воздействием первого сигнала перешли в состояния, принадлежащие в свою очередь 1-эквивалентному классу, образуют 2-эквивалентный касс.
3. Процедура разбиения на классы эквивалентности продолжается до тех пор, пока при очередном шаге К- эквивалентные классы не совпадут с (К-1)-эквивалентными, т.е. получатся эквивалентные классы.
4. Все состояния, входящие в один класс эквивалентности, заменяются одним состоянием
