Модели конечных автоматов Мили и Мура.
Две модели:
Модель Мили:
X = { 1, 2,… k } - входной алфавит;
Z = { 1, 2,… p } - выходной алфавит;
S = { 1, 2,… l } - алфавит множества промежуточных состояний;
Z v = fZ ( xv , Sv ) - функция реакции;
S v+1 = fS ( xv , Sv ) - функция изменения состояния.
Модель Мура:
X = { 1, 2,… k } - входной алфавит;
Z = { 1, 2,… p } - выходной алфавит;
S = { 1, 2,… l } - алфавит множества промежуточных состояний;
Z v = fZ ( S`v ) - функция реакции;
S v+1 = fS ( xv + 1 , S`v ) - функция изменения состояния.
Переходный процесс считается законченным.
Автомат Мура на один такт обгоняет автомат Мили.
Модели Мили и Мура эквивалентны друг другу:
( xv , S v ) ( S`v ) Мили Мура
( S`v ) ( S v + 1 ) Мура Мили
Мили Мура
Доказательство:
Мили Мура:
( xv , S v ) ( S`v )
Z v = fZ ( xv , Sv ) = fZ``( S`v)
S v + 2 = fS ( xv + 1 , Sv + 1 ) = fS ( xv + 1 , fS( xv , Sv )) = fS ( xv + 1 , S`v)
Мура Мили:
S`v – 1 Sv
Z v = fZ ( S`v ) = fZ ( Sv + 1 ) = fZ ( fS ( xv , Sv )) = fZ`` ( xv , Sv )
S v + 1 = S`v = fS ( xv, Sv – 1 ) = fS`` (xv, Sv )
Теорема:
для предсказания поведения конечного автомата необходимо и достаточно указать входной, выходной алфавиты и алфавит состояний (X, Z, S), характеристические функции ( Zv, Sv+1 ), входную последовательность E0 и начальное состояние автомата 0
Таблица переходов: