Способы задания автомата Миля

P,W,S,s₀– задается аналогично автомату Мура.

Функции выхода задаются тремя способами :

1. перечисление

φ :

S_{1 =} φ(S₀,P₁) – предыдущее воздействие – новое состояние

S_{2 =} φ( S₁ , P₂ )

…

S_{m-1 =} φ( S_m-2 , P₀ )

ψ :

W₁ = ψ (S₀ , P₁)

W₂ = ψ (S₁ , P₂)

…

W_l-1 = ψ (S_m-1 , P₀)

2. Табличный способ

Pj	P0	P1	…	Pn-1
Si
S0	S1	S2	…	S3
S1	S2	S3	…	…
…	…	…	…	…
Sm-1	S0	…	…	…

Таблица выходов для ψ

Pj	P0	P1	…	Pn-1
Si
S0	W0	W1	…	Wl-1
S1	W1	W2	…	…
…	…	…	…	…
Sm-1	W0	…	…	…

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

Pj	P0	P1	…	Pn-1
Si
S0	S1/W0	S2/W1	…	S3/Wl-1
S1	S3/W1	S2/W2	…	…
…	…	…	…	…
Sm-1	S0/W0	…	…	…

3. Графический способ

Так как выходной сигнал зависит и от состояния и от входного сигнала, то выходной сигнал приводят на ребре графа.

S_i

S_j

P_k/W_l

Пример (автомат)

P = {P₁ , P₂}

W = {W₀ , W₁}

S = {S_{0 ,} S₁ , S₂}

s₀

1. перечисление

φ :

S_{0 =} φ(S₀,P₁)

S_{0 =} φ( S₂ , P₂ )

S_{1 =} φ( S₀ , P₂ )

S_{1 =} φ( S₁ , P₁ )

S_{2 =} φ( S₁ , P₂ )

S_{2 =} φ( S₂ , P₁ )

ψ :

W₀ = ψ (S₀ , P₁)

W₁ = ψ (S₀ , P₂)

W₀ = ψ (S₁ , P₁)

W₀ = ψ (S₀ , P₂)

W₀ = ψ (S₂ , P₁)

W₀ = ψ (S₂ , P₂)

2. Таблица (совмещение переходов и выходов)

Pj	P1	P2
Si
S0	S0/W0	S1/W1
S1	S1/W0	S2/W0
S2	S2/W0	S0/W0

3. Г

   P₁/W₀

   рафический способ

S_i

S_i

S_i

P₂/W₀

P₂/W₀

P₂/W₁

P₁/W₀

P₁/W₀

Тест :

ti	t0	t1	t2	t3	t4
si	s0	s0	s1	s2	s2	s0
Pi	P1	P2	P2	P1	P2
Wi		W0	W1	W0	W0	W0

В автомате Мура выходной сигнал определяется только состоянием автомата, следовательно сколь угодно долго автомат будет находиться в некотором состоянии, сколько можно считывать его выходной сигнал соответствующий данному состоянию.

В автомате Миля выходной сигнал зависит не только от состояния, но и от входного сигнала, а следовательно значение выходного сигнала можно считывать лишь в короткие интервалы времени при переходах из одного состояния в другое.

Преобразование автоматов из Миля в Мура и обратно Понятие эквивалентности автоматов

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