Автоматы ( с выходным преобразователем)

 

Они представляют собой совокупность следующих шести объектов

       A = <P, S, s₀, φ, W, ψ>

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

       ψ – функция выходов

Существует две математические модели автомата(автомат Мура и Миля) обе мобели можно представить виде двух частей – формулирователь предыстории и выходного преобразователя.

 

Автомат Мура:

В автомате Мура осуществляется отображение S -> W, т.е. каждой букве состояния ставится буква выходного алфавита.

W_i = ψ(s_i)

W_i (t+1)= ψ(s(t+1)) – новый выходной символ определяется новым состоянием.

 

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

 

 

осуществляется отображение P * S -> W. т.е.

 

W_k = ψ(P_i, S_j)

W(t+1) = ψ(P(t)_, S(t))

 

Новое выходное слово в автомате Миля определяется состоянием, в котором был автомат и выходным словом, который поступил на автомат.

Был в состоянии -> поступил в состояние.

 

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

 

Задание автомата Мура:

       A: <P, W, S, s₀, φ, ψ>

В автомате Мура ψ зависит только от состояний.

Автомат как Мура, так и Миля задается шестью параметрами.

P, W, S – задаются в виде множеств

s₀ – начальное состояние указывается как буква алфавита S

Функция φ – задается тремя способами (рассмотренными ранее): перечисление, табличный, графический.

Функция ψ – также может быть представлена теми же тремя способами.

 

Автомат Мура:

a) перечисление

φ: S_{1 =} φ(S_0, S₁)                                                ψ: W₁ = ψ (S₁)

φ: S_{2 =} φ(S_1, S₁)                                                ψ: W₂ = ψ (S₂)

  …..                                                                         …..

φ: S_{k =} φ(S_k, S_k-1)                                              ψ: W₀ = ψ (S₀)

 

b) табличный способ

φ, ψ

 

Wi	Pi	Pi	P0	P1	P2	…	Pn-1
	Si
W0	S0	Si	Sj	…	…	…	…
W1	S1	…	…	…	…	…	…
Wl-1	Sm-1	S0	Sk	..	…	…	…

 

Данная таблица одна определяет две функции, так как W_i зависит только от S_i

Таблица называется «отмеченной» таблицей.

Количество W и S может быть разное, т.к. разным состояниям может быть поставлено в соответствие одна и та же выходная буква.

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

 

 

 

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

P = {P_1, P₂} – входной алфавит

W = {W₀, W₁} – выходной алфавит

S = {s_0, s_1, s_2, s₃ } – алфавит состояний

s₀ – начальное состояние

 

Функция переходов:

             S₀ = φ (S_0, P₁)

             S₀ = φ (S_3, P₂)

             S₁ = φ (S_0, P₂)

             S₂ = φ (S_1, P₁)

             S₂ = φ (S_2, P₁)

             S₃ = φ (S_1, P₂)

             S₃ = φ (S_2, P₂)

             S₃ = φ (S_3, P₁)

Функция выходов:

             W₀ = ψ (S₀)

             W₁ = ψ (S₁)

             W₀ = ψ (S₂)

             W₀ = ψ (S₃)

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

Wi	Pi	P1	P2
	Si
W0	S0	S0	S1
W1	S1	S2	S3
W0	S2	S2	S3
W0	S3	S3	S0

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

 

 

ti	t0	t1	t2	t3	t4
si	s0	s0	s1	s3	s3	s0
Pi	P1	P2	P2	P1	P2
Ni	*	W0	W1	W0	W0	W0

 

* - эта ячейка пуста, т.к. W(t+1) = ψ(s(t+1)) – это не реакция на входной сигнал

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

На выходе автомата тем не менее будет значение W₀, т.к. выход однозначно определяется состоянием автомата Мура, а состояние = S₀.

Для полной проверки автомата необходимо послать такую последовательность P, чтобы автомат прошел по всем переходам при всех входных сигналах, желательно чтобы автомат оказался в начальном состоянии S₀, что позволит подавать новые входные последовательности без предварительной начальной установки.

 

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

 

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

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

a) перечисление

φ:

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₀)

 

b) Табличный способ

     

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	…	…	…

 

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

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

 

 

 

 

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

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)

P1/W0

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

     

 

 

 

                   

 

 

Тест:

 

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

 

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

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

 

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