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

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

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

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

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

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

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

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

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

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

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

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

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

….. …..

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

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

φ , ψ

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

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

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

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

S_j / W_j

P_i

S_i / W_i

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

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

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

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

P₁

P₂

S₀ / W₀

S₁ / W₁

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

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

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

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