Теория автоматов. 4.Математическая модель абстрактного автомата. А-ты Мура, Мили и связь между ними

Комбинационный автомат — это дискретный автомат, удовл. Условию, каждой комбинации значений входных переменных должен соответствовать вполне определённый набор значений выходных переменных. (это автомат без памяти)

Абстрактный автомат (А) — математическая модель дискретного устройства состоящая из 6 элементов:

S = {A,Z,W,δ,λ,a₁},где

A = {a₁, …, a_m} – множество внутренних состояний (a1 – начальное состояние)

Z — входной алфавит

W — выходной алфавит

δ — функция перехода (определяет новое состояние)

λ — функция выходов

Автомат Мили:

a(t+1) = δ (a(t), z(t));

w(t) = λ (a(t), z(t));

a(0) = a1, t= 0,1,2,...

Автоматы Мили и Мура (задаються) различаются способом определения выходного сигнала. В автомате Мили функция λ определяет выходной сигнал в зависимости от состояния автомата и входного сигнала в момент времени t, а в автомате Мура накладываются ограничения на функцию λ, заключающиеся в том, что выходной сигнал зависит только от состояния автомата и не зависит от значения входных сигналов. Выходные сигналы ЦА Мура отстают на один такт от выходных сигналов ЦА Мили, эквивалентного ему.

Автомат Мили задаётся таблицей переходов и таблицей выходов.

Автомат Мура задаётся таблицей модели Мура.

Абстрактным С-автомат - математическую модель цифрового устр-ва, определяемую 8-микомпонентным

вектором S = {A,Z,W,U,δ,λ₁, λ₂,a₁}, где

А - множество состояний (а₁ – начальное состояние)

Z - входной алфавит,

W - выходной алфавит автомата Мили, U - выходной алфавит автомата Мура,

δ - функция переходов автомата,

λ₁ - функция выходов автомата Мили, λ₂- функция выходов автомата Мура.

Отличие С-автомата в том, что он одновременно реализует две функции выходов λ₁ и λ₂, каждая из которых характерна для модели Мили и модели Мура в отдельности. От С-автомата легко перейти к автоматам Мили и Мура с учетом возможных сдвигов выходных сигналов на такт, аналогично тому, как возможен переход от автомата Мили к автомату Мура и наоборот. Много реальных автоматов работает по модели С-автомата.

Эквивалент-ть автоматов:

Два автомата S_A и S_B с одинаковыми входными и выходными алфавитами наз. эквивалентными, если после установления их в начальные состояния их реакции на любое входное слово совпадают.

Связь Мура и Мили.