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

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 11Следующая ⇒

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

       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) табличный способ

φ, ψ

Данная таблица одна определяет две функции, так как 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₃)

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

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

* - эта ячейка пуста, т.к. 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) Табличный способ

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

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

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) Таблица (совмещение переходов и выходов)

3)

P1/W0

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

Тест:

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

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

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

Познавательные статьи:



Где возникла философия и почему?

Относительная высота сжатой зоны бетона

Сущность проекции Гаусса-Крюгера и использование ее в геодезии

Тарифы на перевозку пассажиров