Библиографическое описание:

Кузнецова М. С. Методы задания автоматов // Молодой ученый. — 2015. — №7. — С. 7-11.

Поведение многих объектов описывается так называемой конечно-автоматной моделью. В соответствии с этой моделью объект находится в одном из конечного множества состояний, а переходит в другое состояние под воздействием входных сигналов (команд, событий). Находясь в том или ином состоянии, объект вырабатывает некий выходной сигнал (параметр). Иначе говоря, конечный автомат — математическая (алгоритмическая) модель поведения устройств с конечной памятью. Конечные автоматы применяются, например, в системах синтаксического анализа и перевода текста, компьютерных играх, системах управления сложными техническими устройствами и др.

Абстрактный автомат — это математическая модель, описывающая техническое устройство совокупностью входных, выходных сигналов и состояний, кроме того: имеет множество внутренних состояний A={a1(t), a2(t),…,aM(t)}, называемых состояниями автомата; на вход автомата поступает конечное множество входных сигналов Z={z1(t), z2(t),…,zF(t)}; имеется конечное множество выходных сигналов W={u1, u2,…,uG}; задана функция перехода δ(am,zi); задана функция формирования выходов автомата λ(am,zi); определено начальное состояние автомата a1A.

То есть для описания автомата нужно использовать шестёрку вида S={A, Z, W, δ, λ, a1}, где

-           A={a1, a2,…,aM} — алфавит состояний;

-           Z={z1, z2,…,zF} — входной алфавит;

-           W={u1, u2,…,uG} — выходной алфавит;

-           δ: A×Z→A (as=δ(am,zi)/as);

-           λ: A×Z→W (us=λ(am,zi)/ as);

-           a1A

Автомат реализует некоторое отображение множества слов входного алфавита Z в множество слов выходного алфавита W.

В зависимости от способа определения выходного сигнала в синхронных автоматах различают:

1.                  Автомат первого рода (Автомат Мили)

A(t+1)=δ(a(t), z(t));

W(t)=λ(a(t), z(t)); где t=0, 1, 2…

2.                  Автомат второго рода (Автомат Мура)

A(t+1)=δ(a(t), z(t));

W(t)=λ(a(t), z(t)); где t=0, 1, 2…

W(t+1)=λ(a(t+1))= λ (δ(a(t), z(t))

Методы задания автоматов

Для задания конечного автомата S требуется описать все элементы множества S={A, Z, W, δ, λ}. Наиболее часто используемой формой описания элементов множества S используется табличный, графический, матричный способы.

Теоретико-множественное представление автоматов.

Для задания конечного автомата S={A, Z, W, δ, λ} все элементы множества должны быть заданы явно. Так для автомата Мили:

A={a1, a2,…,aM} — алфавит состояний;

Z={z1, z2,…,zF} — входной алфавит;

W={u1, u2,…,uG} — выходной алфавит;

δ: A×Z→A (as=δ(am,zi)/as);

λ: A×Z→W (us=λ(am,zi)/ as);

a1- начальное состояние автомата.

Например, автомат Мили S1={A, Z, W, δ, λ, а1}, представленный в табл.1.3 в явной форме описывается так:

A={a1, a2, a3}; Z={z1, z2}; W={u1, u2}; δ: a2=δ(a1,z1); a3=δ(a1,z2); a1=δ(a2,z1); a3=δ(a2,z2); a3=δ(a3,z1); a2=δ(a3,z2); λ: u1=λ(a1,z1); u2=λ(a1,z2); u2=λ(a2,z1); u1=λ(a2,z2); u1=λ(a3,z1); u1=λ(a3,z2).

Автомат Мура S2={A, Z, W, δ, λ, а1}, представленный в табл.1.8 в явной форме описывается так:

A={a1, a2, a3, a4, a5}; Z={z1, z2, z3}; W={u1, u2, u3}; δ: a2=δ(a1,z1); a1=δ(a1,z2); a4=δ(a2,z3); a1=δ(a2,z1); a5=δ(a2,z2); a3=δ(a2,z3); a1=δ(a3,z1); a2=δ(a3,z2); a5=δ(a3,z3); a1=δ(a4,z1); a5=δ(a4,z2); a2=δ(a4,z3); a1=δ(a5,z1); a3=δ(a5); a4=δ(a5,z3); λ: u1=λ(a1); u3=λ(a2); u2=λ(a3); u1=λ(a4); u3=λ(a5).

Табличная форма.

Табличная форма для автомата Мили иллюстрируется табл.1.1 (переходов) и табл.1.2 (выходов).

Таблица 1.1

zf \a m

a1

aM

z1

δ(а1, z1)

δ(аM,z1)

zF

δ(a1,zF)

δ(aM,zF)

 

Таблица 1.2

zf\a m

a1

aM

z1

λ(а1, z1)

λ(аM,z1)

zF

λ(a1,zF)

λ(aM,zF)

 

Строки этих таблиц соответствуют входным сигналам, а столбцы — состояниям, причем крайний левый столбец обозначен начальным состоянием a1. На пересечении столбца am и строки zf…. в таблице переходов ставится функция перехода δ(am,zf), то есть состояние, в которое автомат переходит из состояния am под действием входного сигнала zf, а в таблице выходов — выходная функция λ(am,zf), то есть соответствующий этому переходу выходной сигнал ug.

Пример табличного способа задания автомата Мили показан в табл. 1.3 (переходов) и табл. 1.4 (выходов).

Таблица 1.3

zf\a m

a1

a2

a3

z1

a2

a1

a3

z2

a3

a3

a2

 

Таблица 1.4

zf /a m

a1

a2

a3

z1

u1

u2

u1

z2

u2

u2

u2

 

Таблица 1.5

z f\ am

a 1

a2

a 3

a 4

z1

a 2

a 1

a 3

-

z2

a 3

a 3

a -

a 1

z3

-

a4

a2

a4

 

Таблица 1.6

z f\a m

a 1

a2

a 3

a 4

z1

u1

u 2

u 1

-

z2

u 2

u1

-

u 2

z3

-

u1

u2

u1

 

Автомат называется частично заданным, если он определен не для всех пар переходов (am, zf). Для частично заданного автомата на месте отсутствующего перехода ставится прочерк как в таблице переходов, так и в таблице выходов.

Пример табличного способа задания частичного автомата показан в табл.1.5 (переходов) и табл.1.6 (выходов).

Табличная форма задания автомата Мура представляет собой совмещенную табл.1.7, в которой выходной сигнал, соответствующий состоянию в am автомате Мура размещен в верхней строке над соответствующими состоянием, а остальная информация аналогична представлению автомата Мили. Пример представления автомата Мура приведен в табл.1.8.

Таблица 1.7

uG

u1

uG

zf\ am

a 1

am

z1

δ(a1,z1)

δ(aM,z1)

zF

δ(a1,zF)

δ(aM,zF)

 

Таблица 1.8

uG

u1

u3

u2

u1

u3

zf\ am

a 1

a2

a3

a4

a5

z1

a2

a1

a1

a1

a1

z2

a3

a5

a2

a5

a3

z3

a4

a3

a5

a2

a4

 

Графовая форма задания абстрактных автоматов

В данном случае автомат S={A, Z, W, δ, λ, а1} представляется графом, в котором:

1.                  множество A изображено вершинами графа;

2.                  функция δ задана дугами графа, причем две вершины графа am и as, соединяются дугой, если в автомате существует переход из am в as;

3.                  множество Z изображено метками дуг: zf ставится на дуге из вершины am в вершину as, если в автомате существует переход из am в as под действием входного сигнала zf;

4.                  функция λ задана метками дуг или вершин: для автомата Мили дуга из вершины am в вершину as помечается выходным сигналом ug, если в автомате существует переход из am в as и при этом вырабатывается выходной сигнал ug; а для автомата Мура выходным сигналом ug помечается вершина, определяющая as=λ(am).

На рис.1 приведены примеры описания автомата Мили и автомата Мура:

Рис. 1

 

Матричная форма

Для автомата Мили матричная форма состоит из матрицы C=׀cms׀ размерностью M×M, где каждый элемент матрицы cms=zf/ug, стоящий на пересечении m-ой строки и s-го столбца соответствует входному сигналу zf, вызывающему переход из состояния am в состояние as с выработкой выходного сигнала ug.

Пример матричного описания автомата Мили показан ниже.

Для автомата Мура матричная форма состоит из матрицы C=׀cms׀ размерностью M×M, где каждый элемент матрицы cms=zf, стоящий на пересечении m-ой строки и s-го столбца, соответствует входному сигналу zf, вызывающему переход из состояния am в состояние as. Так как выходной сигнал ug в автомате Мура зависит только от состояния, следовательно, выходные сигналы могут быть представлены матрицей-столбцом. Пример матричного описания автомата Мура показан на формуле, приведенной выше.

Наконец, для задания абстрактных автоматов можно использовать различные операции, выражающие одни автоматы через другие. В качестве примера такой операции рассмотрим сумму S+P автоматов, где S={A, Z, W, δ, λ} и P={Aʹ, Z, W, δʹ, λʹ}, где AAʹ=. Полагаем, S+P={A.Aʹ, Z, W, δʹʹ, λʹʹ}, где δʹʹ(a,z)=δ(a,z), λʹʹ(a,z)=λ(a,z) при aA, zZ и δʹʹ(a,z)=δʹ(a,z), λʹʹ(a,z)=λʹ(a,z) при aAʹ, zZ.

 

Литература:

 

1.         Брауэр В. Введение в теорию конечных автоматов.- М.: Радио и связь, 1987,-392с.

2.         Карпов Ю. Г. Теория автоматов.-СПб.: Питер, 2002,-204с.

3.         Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов.-М.: Наука, 1985,-320с.

4.         Математическая энциклопедия. Ред. коллегия: И. М. Виноградов (гл. ред.) [и др.]. Т.1 — М.: Советская энциклопедия, 1977. — 1152 стб.

5.         Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (поведение и синтез).-М.: Наука, 1970,-400с.

6.         Тюрин С. В. Элементы теории автоматов (Часть 1): Учебное пособие. Воронеж: Воронеж. гос. техн. ун-т, 2002. 98 с.

7.         Пентус А. Е., Пентус М. Р. Математическая теория формальных языков. БИНОМ. Лаборатория знаний, Интернет университет информационных технологий — ИНТУИТ.ру, 2006,-248с.

8.         Хопкрофт Дж.Э., Мотвани Р., Ульман Дж.Д. Введение в теорию автоматов, языков и вычислений, 2-у изд.-М.: Вильямс, 2002,-528с.

Обсуждение

Социальные комментарии Cackle