Автор: Кузнецова Маргарита Сергеевна

Рубрика: Математика

Опубликовано в Молодой учёный №7 (87) апрель-1 2015 г.

Дата публикации: 04.04.2015

Статья просмотрена: 401 раз

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

Кузнецова М. С. Методы задания автоматов // Молодой ученый. — 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с.

Основные термины (генерируются автоматически): автомата Мили, автомата Мура, выходной сигнал, описания автомата, выходной сигнал ug, задания автомата, матричного описания автомата, задания автомата Мили, задания автомата Мура, автомата Мили матричная, описания автомата Мили, автомата Мили дуга, автомата Мура матричная, формирования выходов автомата, автомата Мура выходным, описания автомата Мура, представлению автомата Мили, представления автомата Мура, задания конечного автомата, состояние автомата a1A.

Обсуждение

Социальные комментарии Cackle
Задать вопрос