Автомат без выходного преобразователя

Автомат без выходного преобразователя – это следующая совокупность четырех объектов: A = <P, S, s0 , φ>, где :

P = {p1, p2, …, pn} – входной алфавит;

S = {s0, s1, s2, …, sk} – множество состояний, в которых может находиться автомат;

s0 – начальное состояние автомата, s0 Автомат без выходного преобразователя - student2.ru S;

φ – функция перехода автомата, которое представляет собой отображение декартова произведения множеств P и S на множество S, т.е. P × S Автомат без выходного преобразователя - student2.ru S .

Это значит что каждой паре: входной символ pi и состояние sj ставится в соответствие новое состояние sk. Функция перехода записывается следующим образом:

sk = φ(pi , sj), где:

pi – входной символ;

sj – текущее состояние автомата;

sk – новое состояние автомата.

Aбстрактный автомат называется конечным, если все его алфавиты конечны.

Автомат называется инициальным, если перед началом работы он должен быть установлен в начальное состояние s0.

Так как работа автомата рассматривается в дискретные моменты времени то функцию перехода можно представить в виде:

sk (t+1) = φ(pi(t) , sj(t)), где:

pi(t) и sj(t) – входной символ и состояние автомата в текущем автоматном такте (t);

sk (t+1) – новое состояние автомата в следующем автоматном такте (t+1).

Теория конечных автоматов не оперирует с такой величиной как время и символ t в приведенной формуле функции перехода обозначает текущий автоматный такт, а t+1 обозначает следующий автоматный такт.

Обычно в теории автоматов обозначения автоматных тактов при записи функций не указываются

Способы задания автомата без выходного преобразователя.

Пусть заданы: P – входной алфавит, S – множество состояний и s0 – начальное состояние автомата.

Существует три способа задания функций перехода:

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

2. табличный;

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

При перечислении приводятся все функции перехода:

s1 = φ(s0 , p1),

s2 = φ(s1 , p1),

. . . . . .

sk = φ(sk-1 , pn).

В табличном способе строится таблица переходов, столбцы которой помечаются входными символами, а строки – символами состояний из которых осуществляется переход. Внутри таблицы на пересечении i-той строки и j-того столбца указывается состояние, в которое переходит автомат из состояния si под воздействием входного символа pj.

Таблица 2.1

pj si p1 p2 ….. pn
s0 s1 s2 ….. s1
s1 s2 s2 ….. sk
….. ….. ….. ….. .…
sk     …..  

В графическом способе каждому состоянию автомата ставится в соответствие вершина графа, которая помечается символом этого состояния. Если из состояния si существует переход в состояние sj под воздействием входного символа pk, то вершины si и sj соединяются дугой, исходящей из si, а сама дуга помечается символом pk под воздействием которого осуществляется данный переход (рис.2.2). Направление дуги указывает направление перехода, поэтому граф автомата является ориентированным графом.




si
sj
pk

Рис. 2.2

Пример задания автомата без выходного преобразователя:

Пусть P = {p1, p2}, S = {s0, s1, s2}

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

Перечислением: s0 = φ(s0 , p1), s1 = φ(s0 , p2), s1 = φ(s1 , p1), s2 = φ(s1 , p2),

s2 = φ(s2 , p1), s0 = φ(s2 , p2).

Таблицей переходов: (табл. 2.2).

Таблица 2.2

pj si p1
p1
p1
p1

s0 s0

p2
s1

s1 s1
s1
s0
s2

s2 s2

p2
s0

p2
Графом переходов: (рис. 2.3).

s2
p1  

Рис. 2.3

В табл.2.3 приводится моделирование работы автомата, приведенного в примере, по переработке входного слова p1p2p2p1p2. В процессе работы происходит следующая смена состояний автомата: s0 Автомат без выходного преобразователя - student2.ru s0 Автомат без выходного преобразователя - student2.ru s1 Автомат без выходного преобразователя - student2.ru s2 Автомат без выходного преобразователя - student2.ru s2 Автомат без выходного преобразователя - student2.ru s0, т.е. работа автомата без выходного преобразователя состоит в получении последовательности состояний.

Таблица 2.3

Автоматный такт tk t0 t1 t2 t3 t4 t5
Состояние автомата si s0 s0 s1 s2 s2 s0
Входной символ pj p1 p2 p2 p1 p2  

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

Автомат с выходным преобразователем это есть совокупность следующих шести объектов:

A = <P , S , s0 , φ , W , ψ>, где:

P = {p1, p2, …, pn} – входной алфавит;

S = {s0, s1, s2, …, sk} – множество состояний;

s0 – начальное состояние автомата, s0 Автомат без выходного преобразователя - student2.ru S;

φ – функция перехода автомата;

W = {w1, w2, …, wm}– выходной алфавит;

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

Определение объектов P , S , s0 , φ совпадает с определением тех же объектов в автомате без выходного преобразователя.

Существует две математические модели автомата с выходным преобразователем: автомат Мура и автомат Мили. Определение функции выхода ψ различно в каждой из этих моделей. Оба автомата можно представить в виде композиции автомата без выходного преобразователя A* и выходного преобразователя L.

Автомат Мура приведен на рис. 2.4, где: Автомат без выходного преобразователя - student2.ru , Автомат без выходного преобразователя - student2.ru , Автомат без выходного преобразователя - student2.ru слова из соответствующих алфавитов.

Автомат без выходного преобразователя - student2.ru   Автомат без выходного преобразователя - student2.ru
Автомат без выходного преобразователя - student2.ru Автомат без выходного преобразователя - student2.ru   Автомат без выходного преобразователя - student2.ru   Автомат без выходного преобразователя - student2.ru  
Автомат без выходного преобразователя - student2.ru
A*   A*   A*   A*
L   L   L   L

Рис.2.4

В автомате Мура функция выхода ψ осуществляет отображение множества S на множество W, т.е. S Автомат без выходного преобразователя - student2.ru W. Это означает что каждому состоянию si ставится в соответствие выходной символ wi. Функция перехода записывается следующим образом:

wi = ψ(si), где:

si – текущее состояние автомата;

wi – выходной символ.

Существенным в определении функции выхода автомата Мура является то что новый выходной символ wi(t+1) в такте (t+1) определяется следующим состоянием si(t+1)) в которое переходит автомат. т.е. -

wi(t+1)= ψ(si(t+1)).

Автомат Мили приведен на рис. 2.5, где: A* автомат без выходного преобразователя, L – преобразователь, Автомат без выходного преобразователя - student2.ru , Автомат без выходного преобразователя - student2.ru , Автомат без выходного преобразователя - student2.ru , – слова из соответствующих алфавитов.

Автомат без выходного преобразователя - student2.ru  
Автомат без выходного преобразователя - student2.ru  
Автомат без выходного преобразователя - student2.ru  
A*  
L  

Рис.2.5

В автомате Мили функция выхода ψ осуществляет отображение декартова произведения множеств Pи S на множество W, т.е. P × S Автомат без выходного преобразователя - student2.ru W. Это значит что каждой паре: входной символ pi и состояние sj ставится в соответствие выходной символ wk. Функция выхода записывается следующим образом:

wk = ψ(pi , sj), ), где:

pi – входной символ;

sj– текущее состояние автомата;

wk – выходной символ.

В функции выхода автомата Мили новый выходной символ wk(t+1) в такте (t+1) определяется входным символом pi(t) и состоянием si(t) в текущем такте (t).

wk(t+1) = ψ(pi(t) , sj(t)).

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

Пусть заданы: P – входной алфавит, S – множество состояний, s0 – начальное состояние автомата и W – выходной алфавит.

Функции перехода и функции выхода могут быть представлены тремя способами:

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

2. табличный;

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

При перечислении приводятся все функции перехода и выхода:

s1 = φ (s0 , p1), w1 = ψ (s1),

s2 = φ (s1 , p1), w2 = ψ (s2),

. . . . . . . . . . . .

so = φ (sk , pn). w0 = ψ (s0).

В табличном способе строится таблица переходов, которая слева дополняется столбцом, в котором для каждого состояния sj указывается соответствующий ему выходной символ wj (табл.2.3).

В графическом способе каждому состоянию автомата ставится в соответствие вершина графа, которая помечается символом этого состояния si и выходным символом wi, соответствующим этому состоянию. Если из состояния si существует переход в состояние sj под воздействием входного символа pk, то вершины si и sj соединяются дугой исходящей из si, а сама дуга помечается символом pk под воздействием, которого осуществляется данный переход (рис.2.6).

Таблица 2.3

wj pi sj p1 p2 ….. pn
w0 s0 s1 s2 ….. s1
w1 s1 s2 s2 ….. sk
….. ….. ….. ….. ….. .…
wk sk     ….. s0

sj/wj
si/wi
pk

Рис. 2.6

Пример автомата Мура.

Пусть P = {p1 , p2}, W = {w0 , w1}, S = {s0 , s1 , s2 , s3}.

Функции перехода : Функции выхода : s0 = φ (s0 , p1), w0 = ψ (s0),

s1 = φ (s0 , p2), w1 = ψ (s1),

s2 = φ (s1 , p1), w0 = ψ (s2),

s2 = φ (s2 , p1), w0 = ψ (s3).

s3 = φ (s1 , p2),

s3 = φ (s2 , p2),

s3 = φ (s3 , p1).

Таблица переходов и выхода заданного автомата Мура (табл.2.4).

Таблица 2.4

wi pi si p1 p2
w0 s0 s0 s1
w1 s1 s2 s3
w0 s2 s2 s3
w0 s3 s3 s0


Граф заданного автомата Мура (рис.2.7).

s0 / w0
s1 / w1
s3 / w0
s2 / w0
p2
p2
p1
p1
p1
p1
p2
p2

Рис.2.7

В табл.2.5 приводится моделирование работы автомата Мура, приведенного в примере, по преобразования входного слова p1p2p2p1p2. В процессе работы происходит следующая смена состояний автомата: s0 Автомат без выходного преобразователя - student2.ru s0 Автомат без выходного преобразователя - student2.ru s1 Автомат без выходного преобразователя - student2.ru s3 Автомат без выходного преобразователя - student2.ru s3 Автомат без выходного преобразователя - student2.ru s0 и формируется следующая последовательность выходных символов w0w1w0w0w0, т.е. работа автомата Мура состоит в преобразования входного слова в выходное.

Таблица 2.5

tk t0 t1 t2 t3 t4 t5
si s0 s0 s1 s3 s3 s0
pj p1 p2 p2 p1 p2  
wq w0* w0 w1 w0 w0 w0

В момент t0 значение wo* не учитывается, т.к. не является реакцией на входной символ, а определяется s0 - начальным состоянием автомата Мура еще до подачи на вход первого символа входной последовательности.

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

Пусть заданы: P – входной алфавит, S – множество состояний, s0 – начальное состояние автомата и W – выходной алфавит.

Функции перехода и функции выхода могут быть представлены тремя способами, как и в автомате Мура:

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

2. табличный;

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

При перечислении приводятся все функции перехода и выхода:

s1 = φ (s0 , p1), w1 = ψ (s0 , p1),

s2 = φ (s1 , p1), w2 = ψ (s1 , p1),

. . . . . . . . . . . .

so = φ (sk , pn). w0 = ψ (sk , pn).

Функция перехода задается как в автомате Мура. Отличие состоит в задании функции выхода.

В табличном способе строится таблица переходов (табл.2.6) и аналогичная ей таблица выходов (табл.2.7), на пересечении i - той строки и j - того столбца которой указывается выходной символ wk, который выдает автомат при переходе из состояния si под воздействием входного символа pj.

Таблица 2.6 Таблица 2.7

pj si p0 p1 pn
s0 s1 s2 s3
s1 s2 s3
sк s0 sк
pj si p0 p1 pn
s0 w0 w1 wq
s1 w1 w2
sк w0 wq

Эти таблицы аналогичны, поэтому обычно они объединяются, и получается совмещенная таблица переходов и выхода (табл.2.8).

Таблица 2.8

pj si p0 p1 pn
s0 s1/w0 s2/w1 s3/wq
s1 s2/w1 s3/w2
sk s0/w0 sк/wq

В графическом способе каждому состоянию автомата ставится в соответствие вершина графа, которая помечается символом этого состояния si. Если из состояния si существует переход в состояние sj под воздействием входного символа pk, то вершины si и sj соединяются дугой исходящей из si, а сама дуга помечается символом pk, под воздействием которого осуществляется данный переход и выходным символом wq, который вырабатывается при этом переходе (рис.2.8).

si
sj
pk / wq

Рис.2.8

Пример автомат Мили.

Пусть P = {p1 , p2}, W = {w0 , w1}, S = {s0 , s1 , s2}.

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

s0 = φ( s0 , p1 ), w0 = ψ (s0 , p1),

s0 = φ( s2 , p2 ), w1 = ψ (s0 , p2),

s1 = φ( s0 , p2 ), w0 = ψ (s1 , p1),

s1 = φ( s1 , p1 ), w0 = ψ (s0 , p2),

s2 = φ( s1 , p2 ), w0 = ψ (s2 , p1),

s2 = φ( s2 , p1 ). w0 = ψ (s2 , p2).

Таблица переходов и выхода для заданного автомата Мили (табл.2.9).

Таблица 2.9

pj si p1
p1/w0
p1/w0
p2

s0 s0/w0
p2/w1
s1/w1

s1 s1/w0
s1
s0
s2/w0

s2 s2/w0
p2/w0
s0/w0

s2
p2/w0

Граф заданного автомата Мили (рис.2.9).

p1/w0

p1/W0
Рис.2.9

В табл.2.10 приводится моделирование работы автомата Мили, приведенного в примере, по преобразования входного слова p1p2p2p1p2. В процессе работы происходит следующая смена состояний автомата: s0 Автомат без выходного преобразователя - student2.ru s0 Автомат без выходного преобразователя - student2.ru s1 Автомат без выходного преобразователя - student2.ru s2 Автомат без выходного преобразователя - student2.ru s2 Автомат без выходного преобразователя - student2.ru s0 и формируется следующая последовательность выходных символов w0w1w0w0w0, т.е. работа автомата Мили состоит в преобразовании входного слова в выходное.

Таблица 2.10

tk t0 t1 t2 t3 t4 t5
si s0 s0 s1 s2 s2 s0
pj p1 p2 p2 p1 p2  
wq   w0 w1 w0 w0 w0

При сравнении работы автомата Мура (табл.2.5) и работы автомата Мили (табл.2.10) видно, что одно и то же входное слова p1p2p2p1p2 оба автомата перерабатывают в одно и то же выходное слова w0w1w0w0w0. Разница в работе автомата Мура и автомата Мили в том, что в автомате Мура выходной символ можно считывать сразу после установки его в начальное состояние, но при этом надо учитывать, что этот символ не является реакцией на входной символ, а определяется только начальным состоянием автомата Мура.

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

Наши рекомендации