Абстрактный автомат

Тема 5.1. Переработка информации с помощью конечных автоматов

Глава 5. Основы теории конечных автоматов

Резюме по теме

Вопросы для повторения

1.Маршрут это?

2.В каком случае маршрут называется циклическим?

3.Что представляет собой цепь?

4.В каком случае цепь является простой цепью?

5.Дайте определение Эйлерова цикла?

6.В чем заключается отличие Эйлерова и Гамильтонова циклов?

7.Когда граф называется деревом?

8.Чем являются связные компоненты леса?

9.Вершина называется концевой если?

В данной теме рассмотрены такие понятия как маршрут, цикл, цепь, контур и так далее применительно графов. Приведены Эйлеров и Гамильтонов циклы. Показана отдельная структура графов, которая определяется как дерево. Совокупность данных структур характеризуется как лес.

Цель : рассмотреть основы теории конечных автоматов.

Задачи :

1. Рассмотреть понятие абстрактного автомата.

2. Выявить способы задания автоматов.

3. Рассмотреть взаимосвязь между автоматами Миля и Мура.

Автомат - дискретный преобразователь информации, способный под действием входных сигналов переходить из состояния в состояние и вырабатывать выходные сигналы.

Абстрактный автомат задается с помощью следующей пятерки множеств:

А = { X, Y, S, d , l} ,

где Х = {X 1 , X 2 ... X M } – входной алфавит автомата или множество входных символов;

Y = {Y 1 , Y 2 ... Y N } – выходной алфавит автомата или множество выходных символов;

S = {S 0 , S 1 . . . S K-1 } – алфавит или множество внутренних состояний автомата;

S 0 – начальное состояние автомата (в момент времени t = 0 ).

d – функция переходов;

l - функция выходов автомата.

Автомат называется конечным автоматом , если множества X, Y, S конечны (или счетны).

Автомат функционирует в дискретные моменты времени t = 0, 1, 2 ...n (рис. 5.1).

Рис. 5.1. Конечный автомат

В каждый момент времени автомат находится в одном из состояний из множества S .

Функция переходов d t следующее состояние автомата в зависимости от текущего состояния и входного сигнала или символа входного алфавита. Другими словами, функция d каждой паре «состояние – входной сигнал» ставит в соответствие следующее состояние.

d: S´X ® S; d - есть отображение декартова произведения S´X в S .

Функция переходов может быть записана следующим образом: S t+1 = d(S t , X t) .

Функция выходов l определяет в каждый момент времени t выходной сигнал автомата.

Существует две модели автоматов – автомат Мили и автомат Мура. Они отличаются функцией выходов, которая определяется следующим образом:

Y t = l (S t , X t) - для автомата Мили, или l: S´X®Y .

Y t = l (S t) - для автомата Мура.

В автомате Мили выходной сигнал в момент времени t зависит как от входного сигнала в момент времени t , так и от текущего состояния.

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

Состояние автомата – это память автомата о прошлых входных воздействиях.

Автоматы также называют последовательностными машинами (Sequential Machines), так как входная последовательность преобразуется в последовательность состояний и выходную последовательность.

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

Слово или цепочка – это конечная последовательность символов (букв) входного алфавита. Должны выполняться следующие условия (условия автоматности):

1. Длины входных и выходных слов одинаковы;

2. Одинаковым начальным отрезкам входных слов соответствуют одинаковые начальные отрезки выходных слов.

верификация систем взаимодействующих процессов;

Языки описания документов и объектно-ориентированных программ;

Оптимизация логических программ др.

Об этом можно судить по выступлениям на семинаре " Software 2000…" ученых и специалистов.

Дуг Росс: "…80 или даже 90 % информатики ( Computer Science ) будет в будущем основываться на теории конечных автоматов…"

Herver Gallaire: "Я знаю людей из "Боинга", занимающихся системами стабилизации самолетов с использованием чистой теории автоматов. Даже трудно себе представить, что им удалось с помощью этой теории. "

Brian Randell: "Большая часть теории автоматов была успешно использована в системных программах и текстовых фильтрах в ОС UNIX . Это позволяет множеству людей работать на высоком уровне и разрабатывать очень эффективные программы".

1.1. Основные понятия и определения.

Простейший преобразователь информации (рис.1.1,а) отображает некоторое множество элементов информации Х , поступающее на вход, в некоторое множество на выходе Y . Если множества Х и Y являются конечными и дискретными, то есть преобразование осуществляется в дискретные моменты времени, то такие преобразователи информации называются конечными преобразователями. Элементы множеств Х и Y в этом случае предварительно кодируют двоичными кодами и строят преобразование одного множества в другое.

Результат преобразования зачастую зависит не только от того, какая информация в данный момент появилась на входе, но и от того, что происходило раньше, то есть от предыстории преобразования. Например, один и тот же вход - извинение соседа после того, как он вам наступил на ногу в переполненном автобусе - вызовет у вас одну реакцию в первый раз и совсем другую - в пятый раз.

Рис. 1.1.

Таким образом, существуют более сложные преобразователи информации (ПИ), реакция которых зависит не только от входных сигналов в данный момент, но и от того, что было раньше, от входной истории. Такие ПИ называются автоматами (схемами с памятью). В этом случае говорят об автоматном преобразовании информации (рис.1.1,б). На один и тот же входной сигнал автомат может реагировать по-разному, в зависимости от состояния, в котором он находился. Автомат меняет свое состояние с каждым входным сигналом.

Рассмотрим несколько примеров.

Пример 1 1Карпов Ю.Г. Теория автоматов-СПб.:Питер, 2003 . Автомат , описывающий поведение "умного" отца.

Опишем поведение отца, сын которого учится в школе и приносит двойки и пятерки. Отец не хочет хвататься за ремень каждый раз, как только сын получит двойку, и выбирает более тонкую тактику воспитания. Зададим такой автомат графом , в котором вершины соответствуют состояниям, а дуга из состояния s в состояние q , помеченное x/y , проводится тогда, когда автомат из состояния s под воздействием входного сигнала х переходит в состояние q с выходной реакцией y . Граф автомата , моделирующего умное поведение родителя, представлен на рис.1.2. Этот автомат имеет четыре состояния , два входных сигнала - оценки и выходные сигналы , которые будем интерпретировать как действия родителя следующим образом:

Брать ремень;

Ругать сына;

Успокаивать сына;

Надеяться;

Радоваться;

Ликовать.

Рис. 1.2.

Сына, получившего одну и ту же оценку - двойку, ожидает дома совершенно различная реакция отца в зависимости от предыстории его учебы. Например, после третьей двойки в истории сына встретят ремнем, а в истории будут успокаивать и т.д.

Конечный автомат может быть реализован как программно, так и аппаратно. Программную реализацию можно выполнить на любом языке высокого уровня разными способами. На рис.1.3 представлена блок-схема программы, реализующей поведение автомата примера 1. Нетрудно увидеть, что топология блок-схемы программы повторяет топологию графа переходов автомата . С каждым состоянием связана операция NEXT , выполняющая функцию ожидания очередного события прихода нового входного сигнала и чтения его в некоторый стандартный буфер х , а также последующий анализ того, какой это сигнал. В зависимости от того, какой сигнал пришел на вход, выполняется та или иная функция и происходит переход к новому состоянию.

Рис. 1.3.

Аппаратную реализацию автомата рассмотрим во второй части этого раздела.

Пример 2. "Студент"

Автомат , модель которого представлена на рис.1.4 , описывает поведение студента и преподавателей.

Рис. 1.4.

Состояния;

- входные сигналы: "н", "2" и "5".

Выходные реакции:

Пример 3 1 . Электронные часы (рис.1.5).

Электронные часы разнообразных функциональных возможностей являются одним из наиболее широко применяемых в быту электронных приборов, управление которыми построено на основе конечноавтоматной модели. Они обычно показывают: время, дату; у них имеется функции такие как "установка времени и даты", "Секундомер", "Будильник"и т.п. Упрощенная структурная схема электронных часов показана нарис.1.5

Рис. 1.5.

Регистры отображают либо время, либо дату, либо секундомер в зависимости от "Управления". Устройство управления построено на основе модели конечного автомата . Конечный автомат реагирует на нажатия кнопки "а" на корпусе переходом в состояние "Установка минут", в котором событие нажатия кнопки "b" вызовет увеличение числа.

Теория абстрактных автоматов

Владимир 2006

Учебное пособие для студентов очной и заочной форм обучения специальностям
в области вычислительной техники, информатики и управления.

Часть 1. Теория абстрактных автоматов…………………………………………………..3

1.1. Общие сведения……………………………..………………………………………..3

1.2. Способы задания автоматов…………………………………………………………4

1.3. Примеры абстрактных автоматов, выполняющих полезные действия…………...6

1.4. Поведение изолированного синхронного автомата………………………………..8

1.5. Регулярные выражения и конечные автоматы…………………………………….10

1.6. Алгоритмы и машины Тьюринга….………………………………………………...11

1.7. Элементы теории формальных грамматик и языков………………………………15

1.8. Условия автоматности отображения………………………………………………..20

1.9. Построение графа автомата по входо-выходным последовательностям…………21

1.10. Преобразование автоматов………………………………………………………….22

Задачи и упражнения.……………………………………………………………………..24

Литература…………………………………………………………………………………25

ЧАСТЬ 1. ТЕОРИЯ АБСТРАКТНЫХ АВТОМАТОВ

Общие сведения

Абстрактный автомат (АА) – дискретный преобразователь информации; представляет собой множество, состоящее из шести элементов:

S = {X, Q, Y, δ, λ, q 1 }

S – абстрактный автомат;

X – множество входных символов (входной алфавит автомата):

X = {x 1 , ... , x m };

Q – множество состояний автомата:

Q = {q 1 , ... , q n };

Y – множество выходных символов (выходной алфавит автомата):

Y = {y 1 , ... , y p };

δ – функция переходов автомата из одного состояния в другое:

q j = δ(q i , x k) ,

где: q j – следующее (новое) состояние автомата; q i – текущее состояние автомата;
x k – текущий входной символ;

λ – функция выходов:

y l = λ (q i , x k);

q 1 – начальное состояние автомата (применяется также обозначение q 0 ).

Автомат называется конечным , если множества X, Q, Y – конечны.

Рис.1. Представление абстрактного автомата

На рис. 1 t – дискретное время: t = nT , где T – интервал (такт), разделяющий дискретные моменты времени; если T = 1, то t = n , т. е. дискретное время сопоставляется упорядоченному ряду натуральных чисел.

Абстрактный автомат (АА) можно рассматривать как "черный ящик" с одним входом и одним выходом, с которым можно экспериментировать, не зная, что находится внутри.

Выходной символ (y l Î Y ) зависит не только от входного символа (x Î X ), но и от
того, в каком состоянии (q i Î Q ) находится автомат. Автомат функционирует в дискретном времени; это означает, что элементы описания автомата заданы только в упомянутые выше дискретные моменты.

Представим, что с некоторого начального, например, нулевого момента времени на вход автомата подаются входные символы, образующие входное слово некоторой длины (длина любого i -го слова измеряется числом символов). На выходе получаем выходное слово той же длины (рис. 2).

Рис.2. Преобразование входных слов в выходные

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

На практике широкое распространение получили две основные модели, описывающие функционирование АА:

1. Модель Мили;

2. Модель Мура.

Модель Мили.

Законы функционирования автомата Мили представлены следующим образом:

q(t+1) = δ(q(t), x(t))

y(t) = λ(q(t), x(t))

t – текущий момент времени;

t+1 – следующий момент времени;

q(t+1) – состояние автомата в следующий момент времени;

q(t), x(t), y(t) – элементы описания автомата в текущий момент времени.

Модель Мура.

Законы функционирования автомата Мура представлены следующим образом:

q(t+1) = δ(q(t), x(t))

y(t) = λ(q(t))

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

Любой автомат можно спроектировать по той или иной модели.

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

Рассмотри два основных способов задания автоматов:

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

Автомат Мили

Для автомата Мили табличный способ заключается в построении двух таблиц: таблицы переходов (ТП) и таблицы выходов (ТВ).

б) Таблица выходов

Рис. 4. Таблица переходов и выходов

Пример. Таблица переходов и выходов:

	y 1	y 1	y 3	y 2	y 3
x\q	q 1	q 2	q 3	q 4	q 5
x 1	q 2	q 5	q 5	q 3	q 3
x 2	q 4	q 2	q 2	q 1	q 1

Графовый способ

Автомат представляется ориентированным связным графом (орграфом), вершины которого соответствуют состояниям автомата, а дуги – переходам из состояния
в состояние. Обозначения входных и выходных сигналов распределяются в автоматах Мили и Мура по-разному.

Построим графы для автоматов Мили и Мура по вышеприведенным таблицам:

Рис. 5. Представление автомата Мили в виде графа

Рис. 6. Представление автомата Мура в виде графа

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

Детерминированный автомат – автомат, в котором имеется полная определенность переходов из всех состояний в зависимости от входных сигналов (под действием одного и того же сигнала автомат не может переходить из любого рассматриваемого состояния в различные состояния). Фрагмент графа, изображенный на рисунке 7, не может относиться к детерминированному автомату.

Рис.7. Фрагмент графа, иллюстрирующий неопределенность переходов

Замечание : Недетерминированные (например, вероятностные) автоматы существуют, но их рассмотрение не предусмотрено в данном курсе.

Состояние автомата q i называется устойчивым , если для любого входного сигнала х к , такого, что δ(q s , x k) = q i , справедливо соотношение: δ(q i , x k) = q i . (здесь q s – состояние, предшествующее q i ). Это означает, что, автомат не изменяет своего состояния при повторении на следующем такте сигнала, приведшего его в состояние q i . Фрагмент графа, иллюстрирующий устойчивость состояния, приведен на рисунке 8.

Рис. 8. Устойчивое состояние автомата

Автомат называется асинхронным , если каждое его состояние q i Î Q (i = 1, … , n) устойчиво; в противном случае автомат называется синхронным . Синхронные автоматы важны для теории, а на практике чаще используются асинхронные; устойчивость состояний в асинхронных автоматах достигается введением специальных сигналов синхронизации.

Примеры абстрактных автоматов, выполняющих полезные действия

1. Автомат для задержки сигнала на один такт (для запоминания на один такт)

x\q	q 0	q 1			x\q	q 0	q 1
x 0	q 0	q 0			x 0	y 0	y 1
x 1	q 1	q 1			x 1	y 0	y 1

Поскольку автомат является двоичным, введем обозначения: x 0 = y 0 = 0; x 1 = y 1 = 1.

Рис. 9. Граф автомата для задержки сигнала на один такт

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

2. Автомат для проверки двоичной последовательности на четность.

Опишем данный автомат таблицами и графом:

Таблица переходов и таблица выходов:

x\q	q 0	q 1			x\q	q 0	q 1
x 0	q 0	q 1
x 1	q 1	q 0

Рис. 10. Граф автомата для проверки двоичной последовательности на четность

Анализ показывает, что «0» на выходе автоматически вырабатывается при четном числе единиц на входе, а «1» на выходе вырабатывается при нечетном числе единиц на входе.

Оба рассмотренных автомата имеют "слабую" память, но слабую в разном смысле.
У первого автомата "короткая" память во времени (помнит только один сигнал).
У второго автомата память "длинная" (длина входной последовательности может быть любой), но он различает (распознает ) лишь два класса последовательностей.

3. Автомат для задержки сигнала на два такта.

Автомат имеет четыре состояния, закодированных двумя двоичными разрядами:
q 0 = 00; q 1 = 01; q 2 = 10; q 3 = 11.

Рис. 11. Граф автомата для задержки сигнала на два такта

Достоинства примененного кодирования:

· первая цифра кода состояния показывает, какой сигнал выдает автомат (он легко преобразуется в автомат Мура); вторая цифра кода показывает, под действием какого сигнала автомат приходит в данное состояние.

· легко проверить, что выходной сигнал повторяет входной через два такта.

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

Автомат имеет два состояния: q 0 – нет переноса (сложение цифр операндов не требует учета единицы переноса из предыдущего разряда кода);

q 1 – есть перенос (единица переноса должна быть учтена).

Рис. 12. Граф одноразрядного двоичного последовательного сумматора

В числителе "дроби", записанной при каждой из дуг графа, указаны цифры слагаемых; в знаменателе – результат суммирования в текущем разряде. Сумматор позволяет суммировать двоичные последовательности произвольной длины.

По способу формирования функции выходов выделяют три типа абстрактных автоматов: автомат Мили, автомат Мура, С-автомат. Автомат Мили характеризуется системой уравнений:

y (t) =(a (t), x (t));

a (t+1) = δ (a (t), x (t)). (1-1)

Автомат Мура - системой уравнений:

a (t+1) = δ (a (t), x (t)). (1-2)

С-автомат - системой уравнений:

y 1 (t) =(a (t),x (t));

У 2 (t) = 2 (a (t));

a (t+1) =δ (a (t),x (t)).

Произвольный абстрактный автомат Мили или Мура (рис.1.1.) имеет один входной и один выходной каналы. Произвольный абстрактный С-автомат имеет один входной и два выходны х канала (рис.1.2.).

Рисунок 1.1 - Абстрактный автомат

Рисунок.1.2 Абстрактный С-автомат

Если на вход абстрактного автомата Мили или Мура, установленного в начальное состояние а о, подавать буква за буквой некоторую последовательность букв входного алфавита х (0), х (1),. - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита у (0), у (1),. - выходное слово. Для случая С-автомата на его выходах будут появляться две последовательности: y 1 (0), y 1 (1),. и y 2 (0), y 2 (1),. В абстрактном С - автомате выходной сигнал y 2 (t) =(a (t)) выдается все время, пока автомат находится в состоянии a (t). Выходной сигнал y 1 (t) =λ 1 (a (t),x (t)) выдается во время действия входного сигнала x (t) при нахождении С-автомата в состоянии a (t).

Таким образом, на уровне абстрактной теории функционирование цифрового автомата понимается как преобразование входных слов в выходные слова.

Выделяют полностью определенные и частичные автоматы.

Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены для всех пар переходов (x i ,a j).

Частичным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены не для всех пар переходов (x i ,a j).

Абстрактный цифровой автомат называется инициальным, если на множестве его состояний А выделяется начальное состояние а о.

1.3 Способы задания абстрактных автоматов

Чтобы задать конечный автомат S, необходимо описать все элементы множества: S={ X,A,Y,,,a o }. Существует несколько способов задания работы автомата, но наиболее часто используется табличный (матричный), графический, аналитический.

При табличном способе автомат задается двумя таблицами: таблицей переходов и таблицей выходов, или матрицей соединений. Таблица переходов произвольного полностью определенного автомата строится следующим образом: строки таблицы помечаютсябуквами входного алфавита автомата, а столбцы таблицы - буквами алфавита состояний автомата; В клетке таблицы переходов, находящейся на пересечении строки, отмеченной входным сигналом x i , и столбца отмеченного состоянием a j , ставится состояние а k , являющееся результатом перехода автомата из состояния a j под воздействием входного сигнала х i , что определяется выражением a k =(a j , х j).

Таблица 1.1 Таблица переходов автомата

Состояния
входные сигналы
				(а к, х j)

Пример заполнения таблицы переходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={х 1 , х 2 } - и алфавитом состояний A={a 1 , a 2 , а 3 } представлен в табл.1.2.

Таблица 1.2

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

Заполнение остальных клеток аналогично случаю полностью определенного автомата. Вид таблицы переходов не зависит от типа задаваемого автомата (автомат Мили, Мура, С-автомат). Таблицы выходов автоматов Мили, Мура, С-автомата имеют различия.

Таблица выходов полностью определенного автомата Мили строится следующим образом: идентификация столбцов и строк, а также формат таблицы соответствуют таблице переходов полностью определенного автомата. В клетке таблицы выходов, находящейся на пересечении строки, отмеченной входным сигналом X j , и столбца, отмеченного состоянием а к, ставится выходной сигнал У m , который автомат выдает, находясь в состоянии а k при наличии входного сигнала Xj, что определяется выражением Ym=(а k , х j).

Таблица 1.3 Таблица выходов абстрактного автомата Мили.

Состояния
Входные сигналы

Пример заполнения таблицы выходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={x 1 , x 2 }, алфавитом состояний A={a 1 , а 2 , а 3 } и выходным алфавитом Y={y 1 , y 2 , y 3 }-представлен в табл.1.4.

Таблица 1.4

Очевидно, абстрактный полностью определенный С-автомат задается двумя таблицами выходов, первая из которых есть таблица выходов автомата Мили, а вторая - Мура. Если автомат частичный, то в некоторых клетках его таблицы может стоять прочерк, что означает отсутствие выходного сигнала.

На практике таблицы переходов и выходов часто совмещают в одну таблицу, называемую отмеченной таблицей переходов автомата. Примеры отмеченных таблиц переходов представлены в табл.1.6. - 1.8 (Общий вид отмеченной таблицы переходов - табл.1.6., отмеченная таблица переходов автомата Мили - табл.1.7., отмеченная таблица переходов автомата Мура - табл.1.8.).

Кроме рассмотренных выше таблиц переходов и выходов произвольный абстрактный автомат может быть задан матрицей соединений.

Матрица соединений является квадратной и содержит столько столбцов (строк), сколько различных состояний содержит алфавит состояний данного автомата. Каждый столбец (строка) матрицы соединений помечается буквой состояния автомата. В клетке, находящейся на пересечении столбца, помеченного буквой а j и строки, помеченной буквой a s автомата, ставится входной сигнал (или дизъюнкция входных сигналов), под воздействием которого осуществляется данный переход.

Для абстрактного автомата Мили в клетке рядом с состоянием проставляется также выходной сигнал, который автомат выдает в результате данного перехода (табл.1.9.) Для автомата Мура выходной сигнал проставляется в строке рядом с состоянием (эти состояния соответствуют исходным состояниям автомата).

Таблица 1.6

Состояния
Входные сигналы
		 (a 2 , x j)		 (а k , x j)
		 (a 2 , x j)		 (а k , x j)

Таблица 1.7

Таблица 1.9.

При графическом способе задания абстрактные автоматы представляются ориентированными графами. Графом автомата называется ориентированный связный граф, вершины которого соответствуют состояниям автомата, а дуги между ними - переходам между состояниями. Две вершины a k и a s соединяются дугой в том случае, если в автомате имеется переход из состояния a k в состояние a s . Для автомата Мили входной и выходной сигналы проставляются на дуге, соответствующей данному переходу (рис 1.3.), для автомата Мура входной сигнал проставляется на дуге, а выходной - рядом с вершиной, соответствующей состоянию (рис 1.4.).

Здесь рассматриваются только детерминированные автоматы, у которых выполнено условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Применительно к графическому способу задания автомата это означает, что в графе автомата из любой вершины не могут выходить две и более дуги, отмеченные одним и тем же входным сигналом.

Рисунок 1.3-Граф автомата Мили Рисунок 1.4-Граф автомата Мура

При аналитическом способе задания абстрактные автоматы задаются четверкой объектов:

S={ X,A,Y,F}, где F задает для каждого состояния а j автомата отображение (ХхА) - > (AxY). Другими словами, при аналитическом способе задания для каждого состояния автомата а j указывается отображение F ai , представляющее собой множество всех троек а р, x m , y k , и таких, что под воздействием входного сигнала x m автомат переходит из состояния а j в состояние а р, выдавая при этом выходной сигнал y k .

Применительно к общему определению абстрактного автомата, последнее равнозначно описанию функций δ и λ в соответствии с выражением: a p = δ (a i , x m), y к = λ (a i , x m).

Отображение F ai записывается следующим образом:

F ai {a p (X m /y k),a i (X f /y z) …}.

Для абстрактного автомата Мили (табл.1.7.) аналитическое задание имеет следующий вид:

S={ X,A,Y,F}, X={x 1 ,x 2 }, A={a 1 , а 2 , а 3 }, Y={y 1 , y 2 , у 3 },

F a1 ={a 2 (x 1 /y 2), a 1 (x 2 /у 3) },

F а 2 ={а 3 (x 1 /y 3), a 1 (x 2 /y 1) },

F a 3 ={a 1 (x 1 /y 3), а 2 (x 2 /y 2) }.

Следует отметить, что функция F ai всегда записывается для исходного состояния.

Определим синхронные и асинхронные автоматы. Состояние а s автомата S называется устойчивым cостоянием, если для любого входного сигнала х j Х, такого, что а s = δ (а i Х m) имеет место a s = δ (a s , x m).

Автомат S называется асинхронным, если каждое его состояние a s А устойчиво. Автомат S называется синхронным, если он не является асинхронным.

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

6 Основные понятия и определения теории абстрактных авто­матов (лекция №9)
Цифровой (дискретный) автомат (ЦА) – устройство, которое осуществляет прием, хранение и/или преобразование дискретной информации по некоторому алгоритму. Примерами ЦА могут служить живые организмы, процессоры, бытовая техника калькуляторы – это реальные устройства, а также есть абстрактные, например, модели алгоритмов. ЦА относятся к последовательным устройствам. Этот класс устройств определяется тем , что значение выходов зависит не только от входных значений, но и от текущего состояния устройства. Т.е. вводится понятие – состояние . Для того чтобы хранить данные о состоянии, в котором находится устройство в ЦА используются запоминающие элементы – триггеры.
6.1 Математическая модель цифрового автомата
Цифровой автомат - устройство, характеризующееся набором внутренних состояний в которое оно попадет под воз­действием команд заложенной в него программы. Переход автомата из одного состояния в другое осуществляется в определенный момент времени.

Математической моделью ЦА (а в общем случае любого дискретного устройства) является так называемый абстракт­ный автомат, определенный как 6-компонентный кортеж: S=(A,X,Y,,,а 1) у которого:

1. 
   A={a 1 , a 2 , ... ,a m } – алфавит состояний – множество состояний, в которых может находиться проектируемый цифровой автомат. Количество состояний играет важную роль при реализации ЦА. Чем больше состояний, тем больше требуется запоминающих элементов(триггеров) для построения ЦА.
2. 
   X={x 1 , x 2 , ... ,x f } – алфавит входных значений – множество значений, которые могут поступать на вход ЦА. Например , если у автомата двухразрядный двоичный вход, то элементами алфавита могут быть 00, 01, 10 и 11.
3. 
   Y={y 1 , y 2 , ..., y g } – алфавит выходных значений – множество значений, которые могут быть установлены на выходе ЦА.
4. 
   : AXA – функция переходов a(t+1)=  (x(t),a(t)) . Функция переходов определяет, в какое состояние a(t+1) перейдет автомат под воздействием входного сигнала x(t) , если в текущий момент времени автомат находится в состоянии a(t).
5. 
    : AZW – функция выходов y (t )=  (a (t ), x (t )). Функция выходов определяет какое выходное значение y (t ) будет установлено на выходе автомата в зависимости от входного значения x (t ) и текущего состояния a (t ) .
6. 
   a i  A - начальное состояние автомата –состояние в которое устанавливается ЦА после подачи питания или после сброса

Под алфавитом здесь понимается непустое множество попарно различных символов. Элементы алфавита называются буквами , а конечная упорядоченная последовательность букв - словом в данном алфавите.

Рисунок 6.1 – Абстрактный автомат

Абстрактный автомат (рисунок 6.1) имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,... В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата , причем в начальный момент t = 0 он всегда находится в начальном со­стоянии a(0)=a1. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе букву входного алфавита X(t)  Z. В соответствии с функцией выходов он выдаст в тот же момент времени t букву выходного алфавита y(t)=(a(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t+1)=, a(t)  A, y(t)  Y.

Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов вход­ного алфавита X во множество слов выходного алфавита Y. Т.е. если на вход автомата, установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита x(0), x(1),... - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита y(0), y(1),... - выходное слово. Т.о. выходное слово = (входное слово), где  - отображение, осуществляемое абстрактным автоматом.

На уровне абстрактной теории понятие "работа автомата" понимается как преобразование входных слов в выходные. Можно сказать, что в абстрактном автомате отвлекаемся от его структуры - содержимого прямоугольника (рисунок 6.1), рассматривая его как "черный ящик", т.е. основное внимание уделяем поведению автомата относительно внешней среды.

Понятие состояния в определении автомата введено в связи с тем, что часто возникает необходимость в описании пове­дения систем, выходы которых зависят не только от состояния входов в данный момент времени, но и от некоторой пре­дыстории, т.е. от сигналов , которые поступали на входы системы ранее. Состояния как раз и соответствуют некоторой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходной сигнал как функцию со­стояния и входа в данный момент времени.

6.2 Классификация цифровых автоматов

Рассмотренные выше абстрактные автоматы можно разделить на:

1. 
   полностью определенные и частичные;
2. 
   детерминированные и вероятностные;
3. 
   синхронные и асинхронные;

Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов и функция выходов определены для всех пар (a i , z j).

Частичным называется абстрактный автомат, у которого функция переходов или функция выходов , или обе эти функ­ции определены не для всех пар (a i , z j).

К детерминированным относятся автоматы, у которых выполнено условие однозначности переходов: автомат, находя­щийся в некотором состоянии a i , под действием любого входного сигнала z j не может перейти более, чем в одно состоя­ние.

В противном случае это будет вероятностный автомат , в котором при заданном состоянии a i и заданном входном сиг­нале z j возможен переход с заданной вероятностью в различные состояния.

Для определения синхронных и асинхронных автоматов вводится понятие устойчивого состояния . Состояние a s автомата называется устойчивым, если для любого состояния a i и входного сигнала z j таких, что (a i , z j) = a s имеет место (a s , z j) = a s , т.е. состояние устойчиво, если попав в это состояние под действием некоторого сиг­нала zj, автомат выйдет из него только под действием другого сигнала z k , отличного от z j .

Автомат, у которого все состояния устойчивы - асинхронный .

Автомат называется синхронным , если он не является асинхронным.

Абстрактный автомат называется конечным , если конечны множества А = {a 1 , a 2 , ..., a m }, Z = {z 1 , z 2 , ..., z f }, W = {w 1 , w 2 , ..., w g }. Автомат носит название инициального , если в нем выделено начальное состояние a 1 .
6.3 Разновидности цифровых автоматов
На практике наибольшее распространение получили два класса автоматов - автоматы Мили (Mealy) и Мура (Moore).

Закон функционирования автомата Мили задается уравнениями:

a(t+1) = (a(t), z(t)); w(t) = (a(t), z(t)), t = 0,1,2,...
Закон функционирования автомата Мура задается уравнениями:
a(t+1)=(a(t), z(t)); w(t) = (a(t)), t = 0,1,2,...
Из сравнения законов функционирования видно, что, в отличие от автомата Мили, выходной сигнал в автомате Мура зависит только от текущего состояния автомата и в явном виде не зависит от входного сигнала. Для полного задания автомата Мили или Мура дополнительно к законам функционирования , необходимо указать начальное состояние и оп­ределить внутренний, входной и выходной алфавиты.

Кроме автоматов Мили и Мура иногда оказывается удобным пользоваться совмещенной моделью автомата, так на­зываемым С- автоматом.

Абстрактный С- автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита X, и двумя выходами, на которых появляются сигналы из алфавитов Y и U. Отличие С - автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов  1 и  2 , каждая из которых характерна для этих моделей в отдельности. Закон функционирования С- автомата можно описать следующими уравнениями:
а(t+1) =(a(t), z(t)); w(t) = 1 (a(t), z(t)); u(t) =  2 (a(t)); t = 0, 1, 2, ...
Выходной сигнал U h = 2 (a m) выдается все время, пока автомат находится в состоянии a m . Выходной сигнал Wg= 1 (a m , z f) выдается во время действия входного сигнала Z f при нахождении автомата в состоянии a m .
7 Способы описания и задания автоматов (лекция№10)
Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, X, Y, , , а 1). Множества А, X, Y описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций  и  (следовательно и всего автомата в целом) наибольшее распространение получили табличный и графиче­ский.
7.1 Табличный способ описания цифровых автоматов

При табличном способе описания цифровых автоматов применяется два вида таблиц – таблица переходов и таблица выходов.

Таблица переходов отображает функцию переходов. Строкам таблицы соответствуют состояния автомата, т.е. в таблице столько строк, сколько состояний у автомата. Столбцам таблицы соответствуют входные значения , которые могут поступать на входы ЦА, т.е. столбцом столько – сколько элементов во входном алфавите. На пересечении i-столбца и j-строки в ячейке таблицы указывается состояние в которое перейдет ЦА под воздействием входного сигнала x i (которому соответствует i-й столбец) из состояния a j (которому соответствует j-я строка). Таблица переходов приведена на рисунке 6.2

	x 1	x 2	…	x m
a 1	a 2	a 1	…	a 2
a 2	a n-1	a 3	…	a 1
…			…
a n	-	a n	…	a 2

Рисунок 6.2 – Таблица переходов ЦА
Таблица переходов имеет одинаковый вид как для автомата Мура, так и для автомата Мили. Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте не определенных состояний и выходных сигналов ставится прочерк. В таких автоматах выходной сигнал на каком-либо переходе всегда не определен, если неопределенным является состояние перехода
Таблица выходов для автомата Мили имеет такой же вид как и таблица переходов , только на пересечении i-столбца и j-строки в ячейке таблицы указывается выходное значение, которое сформирует ЦА под воздействием входного сигнала x i (которому соответствует i-й столбец) в состоянии a j (которому соответствует j-я строка). Таблица выходов автомата Мили приведена на рисунке 6.3

	x 1	x 2	…	x m
a 1	y 1	y 3	…	y 1
a 2	y n-1	y 2	…	y n-1
…			…
a n	-	y 1	…	y 2

Рисунок 6.3 – Таблица выходов автомата Мили

Таблица выходов для автомата Мура состоит из одного столбца. Строкам таблицы соответствуют состояния автомата, т.е. в таблице столько строк, сколько состояний у автомата. Пример таблицы приведен на рисунке 6.4

	x 1
a 1	y 1
a 2	y n-1
…
a n	y 2

Рисунок 6.4 – Таблица выходов автомата Мура
В некоторых случаях вместо двух таблиц определяющих ЦА удобно применять совмещенную таблицу переходов и выходов. На рисунке 6.5 приведена совмещенная таблица для автомата Мили. На рисунке 6.6 приведена совмещенная таблица переходов для автомата Мура.

	x 1	x 2	…	x m
a 1	a 2 /y 1	a 1 /y 3	…	a 2 /y 1
a 2	a n-1 /y n-1	a 3 /y 2	…	a 1 /y n-1
…			…
a n	-	a n /y 1	…	a 2 /y 2

Рисунок 6.5 – Совмещенная таблица переходов и выходов автомата Мили

	x 1	x 2	…	x m	Y
a 1	a 2	a 1	…	a 2	y 2
a 2	a n-1	a 3	…	a 1	y 1
…			…
a n	-	a n	…	a 2	y 2

Рисунок 6.6 – Совмещенная таблица переходов автомата Мура
7.2 Графический способ задания цифровых автоматов
При графическом способе автомат задается в виде ориентированного графа, вершины которого соответствуют состояниям, а дуги - переходам между ними. Дуга, направленная из вершины a m , задает переход в автомате из состояния a m в состояние a s . В начале этой дуги записывается входной сигнал X f X, вызывающий данный переход a s =(a m ,x f). Для графа автомата Мили выходной сигнал y g Y, формируемый на переходе, записывается в конце дуги, а для автомата Мура - рядом с вершиной a m , отмеченной состоянием a m , в котором он формируется. Если переход в автомате из состояния a m в состояние a s производится под действием нескольких входных сигналов , то дуге графа, направленной из a m в a s , приписываются все эти входные и соответствующие выходные сигналы. Граф С-автомата содержит выходные сигналы двух типов и они обозначаются на графе как на графах соответствующих автоматов. Граф автомата Мура представлен на рисунке 6.7, а автомата Мили – на рисунке 6.8.

y 2

Рисунок 6.7 –Графическое представление автомата Мура

Рисунок 6.8 –Графическое представление автомата Мили

8 Абстрактный синтез цифровых автоматов
Теория цифровых автоматов рассматривает абстрактный и структурный синтез цифровых автоматов. Абстрактный синтез не описывает внутреннего строения автомата, а дает описание взаимодействия с окружающей средой. К абстрактному синтезу относят:

• 
  определение входного, выходного и алфавита состояний, функции переходов и выходов ;
• 
  задание графов автомата и таблиц переходов и выходов;
• 
  минимизацию числа состояний

8.1 Структура цифрового автомата

Внутреннюю структуру цифрового автомата можно изобразить, как показано на рисунке 8.1.

Рисунок 8.1 – Структурная схема цифрового автомата.

Комбинационная схема №1 реализует переходы автомата из одного состояния в другое под воздействием входных сигналов. Схема проектируется исходя из закодированной таблицы переходов и подграфа переходов выбранного запоминающего элемента.

Блок памяти представляет собой набор триггеров, которые хранят разряды закодированного номера состояния. Количество триггеров зависит от количества состояний, в которых может находиться автомат. И вычисляется как:

N=log 2 M
где M – количество состояний, а N –количество триггеров
Комбинационная схема №2 реализует функцию выходов автомата и на ее выходе устанавливаются выходные значения автомата в соответствии с текущим состоянием автомата и входными значениями.

8.2 Минимизация числа состояний цифрового автомата
Часто при выполнении абстрактного синтеза вводятся избыточные состояния, эквивалентность которых не является очевидной. Избыточное количество состояний может привести к применению лишних триггеров, что усложнит КС1 и КС2. Поэтому очень важно выполнять минимизацию числа состояний перед его структурным синтезом.

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

Определение Два состояния a s и a m являются эквивалентными, если
 (a s , E) =  (a m , E), где  - функция перехода, E – входное слово произвольной длины.

Другими словами, состояния эквивалентны, если в ответ на одни и те же входные слова вырабатывается одна и та же последовательность состояний, независимо от того в каком из двух состояний a s или a m находился автомат в начальный момент времени. Если два состояния эквивалентны , то одно состояние можно заменить на другое.

Кроме эквивалентных состояний существует понятие k-эквивалентных состояний: 1-эквивалентные, 2-эквивалентные и т.д.

Определение Два состояния a s и a m являются k - эквивалентными, если
 (a s , E k ) =  (a m , E k ), где  - функция перехода, E k – входное слово длины k .
Алгоритм минимизации:

1. 
   Находится последовательно разбиения П 1 , П 2 , … П К, П К+1 состояний автомата до тех пор пока на каком-то К+1 шаге П К.+1 станет равно П К. В этом случае полученное к-эквивалентное разбиение будет представлять собой полностью эквивалентные классы.
2. 
   В каждом классе эквивалентности выбирают по одному состоянию, которые образуют новое множество состояний минимизированного автомата.
3. 
   Для переопределения функций переходов и выходов вычеркивают строки, которые соответствую состояниям , не вошедшим в новое множество состояний минимизируемого автомата, а в остальных строка таблицы переходов все состояния заменяются на им эквивалентные состояния, которые вошли в новое множество.
4. 
   Если множество состоит из одного состояние, то у него нет эквивалентных состояний. Если все состояния входят в отдельные множества из одного состояния, то автомат нельзя минимизировать.
5. 
   Разбиение на множества начинается с 0-эквивалентного класса. В данном случае в одни множества попадают состояния с одинаковыми выходными сигналами.