Синтез конечных автоматов
1. Любое входное слово длинною l букв, преобразуется в выходное слово той же длины.
2. Если каждый раз перед подачей входных сигналов автомат находится в одном и том же состоянии, то при совпадении в двух входных словах первых l1 букв, в выходных словах первые l1 букв тоже совпадут.
Кроме детерминированных автоматов существуют вероятностные или стохастические автоматы, в которых переход из одного состояния в другое под воздействием случайных или детерминированных входных сигналов происходит случайно. Работа таких автоматов описывается уже матрицей переходов d, элементами которой являются вероятности переходов из одного состояния в другое.
Мы будем изучать детерминированные автоматы.
Применяемые на практике автоматы принято разделять на два класса: - это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать.
Закон функционирования автоматов Мили описывается следующей системой уравнений:
a(t + 1) = d[a(t),x(t)] ь
y(t) = l[a(t),x(t)] э .
t = 0,1,2,3… ю
Работа автоматов Мура задается следующими уравнениями:
a(t + 1) = d[a(t),x(t)] ь
э.
y(t) = l[a(t)] ю
Отличительной особенностью автоматов Мили является то, что их выходные сигналы зависят как от состояния автомата, так и от значения входного сигнала. В автоматах Мура выходные сигналы y(t) в каждый дискретный момент времени t однозначно определяются состоянием автомата в тот же момент времени и не зависят от значения входного сигнала.
предыдущаяследующая тема