Основные понятия теории абстрактных автоматов. Как уже отмечалось, абстрактный автомат работает как преобразователь слов входного алфавита в слова выходного алфавита
Теория абстрактных автоматов
Владимир 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. Граф одноразрядного двоичного последовательного сумматора
В числителе "дроби", записанной при каждой из дуг графа, указаны цифры слагаемых; в знаменателе – результат суммирования в текущем разряде. Сумматор позволяет суммировать двоичные последовательности произвольной длины.
На выходе оно выдаёт символы (в общем случае) другого алфавита.
Абстрактный автомат
Формально абстрактный автомат определяется как пятерка
Ограничение числа параметров абстрактного автомата определило такое понятие как конечный автомат .
Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата и последовательности выходных символов , которые для последовательности символов разворачиваются в моменты дискретного времени t = 1, 2, 3, … Моменты дискретного времени получили название тактов.
Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений:
Для уточнения свойств абстрактных автоматов введена классификация .
Абстрактные автоматы образуют фундаментальный класс дискретных моделей как самостоятельная модель, и как основная компонента машин Тьюринга , автоматов с магазинной памятью , конечных автоматов и других преобразователей информации.
Wikimedia Foundation . 2010 .
- Диаграмма состояний (теория автоматов)
- Нагорный Карабах
Смотреть что такое "Абстрактный автомат" в других словарях:
абстрактный автомат - abstraktusis automatas statusas T sritis automatika atitikmenys: angl. abstract automaton vok. abstrakter Automat, m rus. абстрактный автомат, m pranc. automate abstrait, m … Automatikos terminų žodynas
Автомат - В Викисловаре есть статья «автомат» Автомат: Автомат устройство, самостоятельно выполняющее некоторые действия … Википедия
Конечный автомат - Конечный автомат абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию. Существуют различные варианты задания конечного автомата. Например,… … Википедия
ТЬЮРИНГА, МАШИНА - Абстрактный автомат (то есть компьютер или другой точный, определенный механизм), теоретически охарактеризованный британским математиком Аланом М. Тьюрингом в 1930 х гг. В основном, машина Тьюринга состоит из ленты и считывающей головки. Лента… … Толковый словарь по психологии
Теория автоматов
Теория автоматов - раздел теоретической кибернетики, который изучает математические модели (называемые здесь автоматами или машинами) реальных или возможных устройств, перерабатывающих дискретную информацию дискретными же тактами. Основными… … Экономико-математический словарь
теория автоматов - Раздел теоретической кибернетики, который изучает математические модели (называемые здесь автоматами или машинами) реальных или возможных устройств, перерабатывающих дискретную информацию дискретными же тактами. Основными понятиями этой теории… … Справочник технического переводчика
Теория автоматов - Теория автоматов раздел дискретной математики, изучающий абстрактные автоматы вычислительные машины, представленные в виде математических моделей и задачи, которые они могут решать. Теория автоматов наиболее тесно связана с… … Википедия
Компьютер - Схема персонального компьютера: 1. Монитор 2. Материнская плата 3 … Википедия
Формальные методы - Пример формальной спецификации с использованием Z нотации В информатике и инженерии программного обеспечения формальными методами называется группа техник, основанных на математическом аппарате для … Википедия
Тема 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. Одинаковым начальным отрезкам входных слов соответствуют одинаковые начальные отрезки выходных слов.
- 1.1 Основные понятия
- Вывод
- Список литературы
Введение
Тема контрольной работы по дисциплине "Прикладная теория цифровых автоматов" - "Абстрактные цифровые автоматы".
Цель работы - ознакомится с основными понятиями абстрактных цифровых автоматов; типами абстрактных автоматов; способами задания абстрактных автоматов; связью между моделями Мили и Мура; эквивалентными автоматами и эквивалентными преобразованиями автоматов; минимизацией числа внутренних состояний автомата и алгоритмом Ауфенкампа-Хона.
1. Абстрактные цифровые автоматы
1.1 Основные понятия
Цифровой автомат можно трактовать как устройство, осуществляющее прием, хранение и преобразование дискретной информации по некоторому алгоритму. С определенной точки зрения к автоматам можно отнести как реальные устройства (ЭВМ), так и абстрактные системы (математические модели).
Автоматом называется дискретный преобразователь информации, способный принимать различные состояния, переходить под воздействием входных сигналов из одного состояния в другое и выдавать выходные сигналы.
Общая теория автоматов подразделяется на абстрактную и структурную.
Абстрактная теория автоматов, отвлекаясь от структуры автомата (т.е. не интересуясь способом его построения), изучает лишь поведение автомата относительно внешней среды. Абстрактная теория автоматов близка к теории алгоритмов, являясь по существу ее дальнейшей реализацией.
В противоположность абстрактной теории автоматов, структурная теория автоматов интересуется как структурой самого автомата, так и структурой входных воздействий и реакций автомата на них. В структурной теории изучаются способы построения автоматов, способы кодирования входных воздействий и реакций автомата на них. Структурная теория автоматов является продолжением и развитием абстрактной теории. Опираясь на аппарат булевых функций и на абстрактную теорию автоматов, структурная теория дает эффективные рекомендации по разработке реальных устройств вычислительной техники.
Абстрактный цифровой автомат (ЦА) является математической моделью дискретного управляющего устройства.
Абстрактный ЦА определяется множеством, состоящим из шести элементов:
S={ X,A,Y,ao},
где:
X={x1, x2,. xn} - множество входных сигналов (входной алфавит);
Y={y1, y2, ym} - множество выходных сигналов (выходной алфавит);
А={ a0,a1, a2,. аN} - множество состояний (алфавит состояний);
ао - начальное состояние (аоА);
- функция переходов автомата, задающая отображение (ХхА) А, т.е. ставящая в соответствие любой паре элементов декартового произведения (ХхА) элемент множества А;
- функция выходов автомата, задающая либо отображение (XxA) Y, либо отображение AY.
Иными словами, функция переходов показывает, что автомат S, находясь в некотором состоянии аjА, при появлении входного сигнала хjХ переходит в некоторое состояние арА. Это можно записать:
ap= (ai,Xj).
Функция выходов показывает, что автомат S, находясь в некотором состоянии аjА, при появлении входного сигнала хjХ выдает выходной сигнал уkY. Это можно записать: уk = (ai, Xj).
Понятие состояние в определение автомата было введено в связи с тем, что часто возникает необходимость в описании поведения систем, выходы которых зависят не только от состояния входов в данный момент времени, но и от некоторой предыстории, т.е. от сигналов, которые поступали на входы системы ранее. Состояние как раз и соответствует некоторой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входов в данный момент времени.
Абстрактный автомат функционирует в дискретном автоматном времени t=0,1,2,. и переходы из состояния в состояние осуществляются мгновенно. В каждый момент t дискретного времени автомат находится в определенном состоянии a (t) из множества А состояний автомата, причем в начальный момент времени t=0 он всегда находится в начальном состоянии ао. В момент времени t, будучи в состоянии a (t), автомат способен воспринять на входном канале сигнал х (t) X, и выдать на выходном канале сигнал y (t) = (a (t), x (t)), переходя в состояние a (t+1) = = (a (t),x (t)). Зависимость выходного сигнала от входного и от состояния означает, что в его составе имеется память.
1.2 Типы абстрактных автоматов
По способу формирования функции выходов выделяют три типа абстрактных автоматов: автомат Мили, автомат Мура, С-автомат. Автомат Мили характеризуется системой уравнений:
y (t) = (a (t), x (t));
a (t+1) = д (a (t), x (t)). (1-1)
Автомат Мура - системой уравнений:
y (t) = (a (t));
a (t+1) = д (a (t), x (t)). (1-2)
С-автомат - системой уравнений:
у= y1y2
y1 (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),. - выходное слово. Для случая С-автомата на его выходах будут появляться две последовательности: y1 (0), y1 (1),. и y2 (0), y2 (1),. В абстрактном С - автомате выходной сигнал y2 (t) = (a (t)) выдается все время, пока автомат находится в состоянии a (t). Выходной сигнал y1 (t) =л1 (a (t),x (t)) выдается во время действия входного сигнала x (t) при нахождении С-автомата в состоянии a (t).
Таким образом, на уровне абстрактной теории функционирование цифрового автомата понимается как преобразование входных слов в выходные слова.
Выделяют полностью определенные и частичные автоматы.
Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены для всех пар переходов (xi,aj).
Частичным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены не для всех пар переходов (xi,aj).
Абстрактный цифровой автомат называется инициальным, если на множестве его состояний А выделяется начальное состояние ао.
1.3 Способы задания абстрактных автоматов
Чтобы задать конечный автомат S, необходимо описать все элементы множества: S={ X,A,Y,ao}. Существует несколько способов задания работы автомата, но наиболее часто используется табличный (матричный), графический, аналитический.
При табличном способе автомат задается двумя таблицами: таблицей переходов и таблицей выходов, или матрицей соединений. Таблица переходов произвольного полностью определенного автомата строится следующим образом: строки таблицы помечаютсябуквами входного алфавита автомата, а столбцы таблицы - буквами алфавита состояний автомата; В клетке таблицы переходов, находящейся на пересечении строки, отмеченной входным сигналом xi, и столбца отмеченного состоянием aj, ставится состояние аk, являющееся результатом перехода автомата из состояния aj под воздействием входного сигнала хi, что определяется выражением ak= (aj, хj).
Таблица 1.1 Таблица переходов автомата
Пример заполнения таблицы переходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={х1, х2} - и алфавитом состояний A={a1, a2, а3} представлен в табл.1.2.
Таблица 1.2
Если абстрактный автомат частичный, то в клетке таблицы его переходов, находящейся, на пересечении строки, отмеченной входным сигналом и столбца отмеченного соответствующим состоянием (при условии, что переход в это состояние под действием данного входного сигнала не определен) ставится прочерк, и любое входное слово, приводящее к указанному переходу является запрещенным.
Заполнение остальных клеток аналогично случаю полностью определенного автомата. Вид таблицы переходов не зависит от типа задаваемого автомата (автомат Мили, Мура, С-автомат). Таблицы выходов автоматов Мили, Мура, С-автомата имеют различия.
Таблица выходов полностью определенного автомата Мили строится следующим образом: идентификация столбцов и строк, а также формат таблицы соответствуют таблице переходов полностью определенного автомата. В клетке таблицы выходов, находящейся на пересечении строки, отмеченной входным сигналом Xj, и столбца, отмеченного состоянием ак, ставится выходной сигнал Уm, который автомат выдает, находясь в состоянии аk при наличии входного сигнала Xj, что определяется выражением Ym= (аk, хj).
Таблица 1.3 Таблица выходов абстрактного автомата Мили.
Пример заполнения таблицы выходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={x1, x2}, алфавитом состояний A={a1, а2, а3} и выходным алфавитом Y={y1, y2, y3}-представлен в табл.1.4.
Таблица 1.4
Очевидно, абстрактный полностью определенный С-автомат задается двумя таблицами выходов, первая из которых есть таблица выходов автомата Мили, а вторая - Мура. Если автомат частичный, то в некоторых клетках его таблицы может стоять прочерк, что означает отсутствие выходного сигнала.
На практике таблицы переходов и выходов часто совмещают в одну таблицу, называемую отмеченной таблицей переходов автомата. Примеры отмеченных таблиц переходов представлены в табл.1.6. - 1.8 (Общий вид отмеченной таблицы переходов - табл.1.6., отмеченная таблица переходов автомата Мили - табл.1.7., отмеченная таблица переходов автомата Мура - табл.1.8.).
Кроме рассмотренных выше таблиц переходов и выходов произвольный абстрактный автомат может быть задан матрицей соединений.
Матрица соединений является квадратной и содержит столько столбцов (строк), сколько различных состояний содержит алфавит состояний данного автомата. Каждый столбец (строка) матрицы соединений помечается буквой состояния автомата. В клетке, находящейся на пересечении столбца, помеченного буквой аj и строки, помеченной буквой as автомата, ставится входной сигнал (или дизъюнкция входных сигналов), под воздействием которого осуществляется данный переход.
Для абстрактного автомата Мили в клетке рядом с состоянием проставляется также выходной сигнал, который автомат выдает в результате данного перехода (табл.1.9.) Для автомата Мура выходной сигнал проставляется в строке рядом с состоянием (эти состояния соответствуют исходным состояниям автомата).
Таблица 1.6
Таблица 1.8
При графическом способе задания абстрактные автоматы представляются ориентированными графами. Графом автомата называется ориентированный связный граф, вершины которого соответствуют состояниям автомата, а дуги между ними - переходам между состояниями. Две вершины ak и as соединяются дугой в том случае, если в автомате имеется переход из состояния ak в состояние as. Для автомата Мили входной и выходной сигналы проставляются на дуге, соответствующей данному переходу (рис 1.3.), для автомата Мура входной сигнал проставляется на дуге, а выходной - рядом с вершиной, соответствующей состоянию (рис 1.4.).
Здесь рассматриваются только детерминированные автоматы, у которых выполнено условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Применительно к графическому способу задания автомата это означает, что в графе автомата из любой вершины не могут выходить две и более дуги, отмеченные одним и тем же входным сигналом.
Рисунок 1.3-Граф автомата Мили Рисунок 1.4-Граф автомата Мура
При аналитическом способе задания абстрактные автоматы задаются четверкой объектов:
S={ X,A,Y,F}, где F задает для каждого состояния аj автомата отображение (ХхА) - > (AxY). Другими словами, при аналитическом способе задания для каждого состояния автомата аj указывается отображение Fai, представляющее собой множество всех троек ар, xm, yk, и таких, что под воздействием входного сигнала xm автомат переходит из состояния а j в состояние ар, выдавая при этом выходной сигнал yk.
Применительно к общему определению абстрактного автомата, последнее равнозначно описанию функций д и л в соответствии с выражением: ap= д (ai, xm), yк= л (ai, xm).
Отображение Fai записывается следующим образом:
Fai{ap (Xm/yk),ai (Xf/yz) …}.
Для абстрактного автомата Мили (табл.1.7.) аналитическое задание имеет следующий вид:
S={ X,A,Y,F}, X={x1,x2}, A={a1, а2, а3}, Y={y1, y2, у3},
Fa1={a2 (x1/y2), a1 (x2/у3) },
Fа2={а3 (x1/y3), a1 (x2/y1) },
Fa3={a1 (x1/y3), а2 (x2/y2) }.
Следует отметить, что функция Fai всегда записывается для исходного состояния.
Определим синхронные и асинхронные автоматы. Состояние аs автомата S называется устойчивым cостоянием, если для любого входного сигнала хjХ, такого, что аs= д (аi Хm) имеет место as= д (as, xm).
Автомат S называется асинхронным, если каждое его состояние as А устойчиво. Автомат S называется синхронным, если он не является асинхронным.
Необходимо заметить, что построенные на практике автоматы всегда асинхронные и устойчивость их состояний всегда обеспечивается тем или иным способом, например, введением сигналов синхронизации. Однако, на уровне абстрактной теории автоматов, когда автомат всего лишь математическая модель, которая не отражает многих конкретных особенностей его реализации, часто оказывается более удобным оперировать с синхронными автоматами.
1.4 Связь между моделями Мили и Мура
Как уже отмечалось, абстрактный автомат работает как преобразователь слов входного алфавита в слова выходного алфавита.
Пусть абстрактный автомат Мили задан графом рис.1.5.
На вход этого автомата, установленного в начальное состояние, поступает входное слово X=x1, x1, x2, x1, x2, x2.
Рисунок 1.5 - Граф автомата Мили
Так как? (a1, x1) = а3, a ? (a1, x1) = y1, то под действием первой буквы слова Х входного сигнала x1 автомат перейдет в состояние a3 и на выходе его появится сигнал y1. Далее, ? (а3, x1) = a1, а? (а3, x1) = у2, потому при приходе второго сигнала x1 автомат окажется в состоянии a1, а на выходе его появится сигнал у2. Проследив непосредственно по графу или таблицам переходов и выходов дальнейшее поведение автомата, опишем его тремя строчками, первая из которых соответствует входному слову X, вторая - последовательности состояний, которые проходит автомат под действием букв слова X, третья - выходному слову У, которое появляется на выходе автомата:
x1x1 x2 x1 x2 x2
a1а3 a1a1 а3a 2 а3
y1 y2 y1 y1 y1 y2
Назовем у = ? (а1, X) реакцией автомата Мили в состоянии a1 на входное слово X. Как видно из примера, в ответ на входное слово длины k автомат Мили выдает последовательность состояний длины к+1 и выходное слово длины k. В общем виде поведение автомата Мили, установленного в состояние аm, можно описать следующим образом:
Точно так же можно описать поведение автомата Мура, находящегося в состоянии am, при приходе входного слова xi1, xi2,., хik. Напомним, что в соответствии с (1-2) выходной сигнал в автомате Мура в момент времени t (У (t)) зависит лишь от состояния, в котором находится автомат в момент t (a (t)):
Очевидно, что выходной сигнал уi1=л (am) в момент времени i1 не зависит от входного сигнала xi1, а определяется только состоянием аm.
Таким образом, этот сигнал yi1 никак не связан с входным словом, поступающим на вход автомата, начиная с момента i1. В связи с этим под реакцией автомата Мура, установленного в состояние am на входное слово X=xi1, хi2, . , хik будем понимать выходное слово той же длины у= л (am,Х) =уi2, уi3,., yik+1.
В качестве примера рассмотрим автомат Мура S5, граф которого изображен на рис.1-6, и найдем его реакцию в начальном состоянии на то же самое входное слово которое мы использовали при анализе поведения автомата Мили S1:
Рисунок 1-6 - Граф автомата Мура
Как видно из этого и предыдущего примеров, реакции автоматов S5 и S1 в начальном состоянии на входное слово Х с точностью до сдвига на 1 такт совпадают (реакция автомата Мура обведена линией). Дадим теперь строгое определение эквивалентности полностью определенных автоматов.
Два автомата SA и SB с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установления их в начальные состояния их реакции на любое входное слово совпадают.
1.5 Эквивалентные автоматы. Эквивалентные преобразования автоматов
Можно показать, что для любого автомата Мили существует эквивалентный ему автомат Мура и, обратно, для любого автомата Мура существует эквивалентный ему автомат Мили.
При описании алгоритмов взаимной трансформации автоматов Мили и Мура в соответствии с изложенным выше мы будем пренебрегать в автоматах Мура выходным сигналом, связанным с начальным состоянием (? (a1)).
Рассмотрим сначала преобразование автомата Мура в автомат Мили.
Пусть дан автомат Мура: SA={ ХA, АA, УA,?A,?A, аоA}, где:
ХA={х1, х2,. хn}; Y={y1, у2,. уm}; А={ а0, а1, а2,. аN}; а0A = а0 - начальное состояние (а0AА); ?A - функция переходов автомата, задающая отображение (ХAхАA) - >АA; ?A - функция выходов автомата, задающая отображение АA->УA.
Построим автомат Мили: SB={ ХB, АB, YB,??B, ?B, а0B}, у которого АB=АA; ХB=ХA; YB=УA; ?B=?A; а0B=а0A. Функцию выходов?B определим следующим образом. Если в автомате Мура?A (аm, х1) = аs и?A (аs) =yg, то в автомате Мили?B (am, х1) =yg
Рисунок 1.7 - Иллюстрация перехода от модели Мура к модели Мили
Переход от автомата Мура к автомату Мили при графическом способе задания иллюстрируется рис.1-7: выходной сигнал yg записанный рядом с вершиной (as), переносится на все дуги, входящие в эту вершину.
При табличном способе задания автомата таблица переходов автомата Мили совпадает с таблицей переходов исходного автомата Мура, а таблица выходов получается из таблицы переходов заменой символа as, стоящего на пересечении строки хf и столбца аm, символом выходного сигнала yg отмечающего столбец as в таблице переходов автомата SA.
Из самого способа построения автомата Мили SB очевидно, что он эквивалентен автомату Мура SA. По индукции нетрудно показать, что любое входное слово конечной длины, поданное на входы автоматов SA и SB, установленных в состояния am, вызовет появление одинаковых выходных слов и, следовательно, автоматы SA и SB эквивалентны.
Прежде чем рассмотреть трансформацию автомата Мили в автомат Мура, наложим на автомат Мили следующее ограничение: у автомата не должно быть преходящих состояний. Под преходящим будем понимать состояние, в которое при представлении автомата в виде графа не входит ни одна дуга, но которое имеет по крайней мере одну выходящую дугу. Итак, пусть задан автомат Мили:
SA={ ХA, АA,YA, ?A, ?A, a0A},
где:
ХA={x1, x2,. xn}; Y={y1, у2,. ym}; А={ a0,a1,a2,. aN}; a0A = a0 - начальное состояние (а0AА); ?A - функция переходов автомата, задающая отображение (ХAxАA) - >АA; ?A - функция выходов автомата, задающая отображение (ХAxАA) - >YA.
Построим автомат Мура: SB={XB, AB, YB, ?B, ?B, a0B}, у которого XB=XA; YB=YA.
Для определения AB каждому состоянию asАA поставим в соответствие множество As всевозможных пар вида (as, yg)
Функцию выходов?B определим следующим образом. Каждому состоянию автомата Мура SB, представляющему собой пару вида (as,yg), поставим в соответствие выходной сигнал yg.
Если в автомате Мили SA был переход?A (am, xf) = as и при этом выдавался выходной сигнал?A (am,xf) =yg, то в SB будет переход из множества состояний Am, порождаемых am, в состояние (as,yg) под действием входного сигнала xf.
В качестве начального состояния a0B можно взять любое из состояний множества A0, которое порождается начальным состоянием a0 автомата SA. При этом выходной сигнал в момент времени t=0 не должен учитываться.
Рассмотрим пример. Пусть задан автомат Мили (табл.1.10.)
Поставим в соответствие каждой паре аi/xk состояние Ьik (i-номер состояния, k-номер входного сигнала), с учетом b0.
Составим таблицу переходов автомата Мура, руководствуясь следующими правилами:
1) Выпишем из таблицы 1.11 состояния автомата Мили и соответствующие каждому из них множества состояний автомата Мура (bik):
а0= {b0, b02, b11, b21}; a1= {b22}; а2= {b01, b12};
2) Если состояние автомата Мура bik входит в множество, соответствующее состоянию аp автомата Мили, то в строку таблицы переходов автомата Мура для состояния bik следует записать строку из таблицы переходов автомата Мили, соответствующую состоянию ар (из 1.10.).
3) Функцию выходов автомата Мура определим следующим образом: ?B (bik) =?A (аi, xk). Для начального состояния b0 значение выходного сигнала можно выбрать произвольно, но порождаемый начальным состоянием a0 (с учетом понятия эквивалентности состояний). Результирующая таблица переходов и выходов автомата Мура эквивалентного автомату Мили, заданному таблицей 1.10 представлена в таблице 1.12.
4) Найдем в таблице 1.12 эквивалентные состояния и удалим их (заменим на представителя класса эквивалентности).
Если выходной сигнал возле b0 доопределить y1, то окажется, что в данной таблице переходов находится 3 эквивалентных состояния (b0,b11,b02). Заменив класс эквивалентности одним представителем (b0), получим окончательную таблицу переходов (табл.1.13).
Таблица 1.12
Изложенные методы взаимной трансформации автоматов Мили и Мура показывают, что при переходе от автомата Мура к автомату Мили число состояний автомата не изменяется, тогда как при обратном переходе число состояний в автомате Мура, как правило, возрастает.
Таким образом, эквивалентные между собой автоматы могут иметь различное число состояний, в связи с чем возникает задача нахождения минимального (с минимальным числом состояний) автомата в классе эквивалентных между собой автоматов. Существование для любого абстрактного автомата эквивалентного ему абстрактного автомата с минимальным числом внутренних состояний впервые было доказано Муром.
1.6 Минимизация числа внутренних состояний автомата
Алгоритм Ауфенкампа-Хона.
В основу метода минимизации состояний автомата положена идея разбиения всех состояний исходного, абстрактного автомата на попарно не пересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием (представителем данного класса). Образующийся в результате этих преобразований минимальный автомат имеет столько же состояний, на сколько классов эквивалентности разбиваются исходные состояния.
Два состояния автомата am и as называются эквивалентными (am =as), если? (am,X) = ? (as,X) для всех возможных входных слов длины X.
Если am и as не эквивалентны, они различимы. Более слабой эквивалентностью является K-эквивалентность. Состояния am и аs K-эквивалентны, если? (am, Хk) = ? (as, Хk) для всех возможных входных слов длины К. При минимизации числа внутренних состояний автомата Мили S={X,Y, А, ?, ?, а0} используется алгоритм Ауфенкампа-Хона:
1. Находят последовательные разбиения?1,?2,…,?k,?k+1, множества А на классы одно-, двух-,., К-, (К+1) - эквивалентных состояний до тех пор, пока на каком-то (К+1) шаге не окажется, что?k=?k+1. В этом случае К-эквивалентные состояния являются эквивалентными. Число шагов К, при котором?k=?k+1 не превышает N-1, где N - число внутренних состояний автомата.
2. В каждом классе эквивалентности? выбирают по одному элементу (представителю класса), которые образуют множества А" состояний минимального автомата S".
3. Функцию переходов?" и выходов?" автомата S" определяют на множестве A"xX.
Для этого в таблице переходов и выходов вычеркивают столбцы, соответствующие не вошедшим в множество А" состояниям, а в оставшихся столбцах таблицы переходов все состояния заменяются на эквивалентные из множества А", (на представителей).
4. В качестве а"0 выбирается одно из состояний, эквивалентное состоянию а0. В частности, удобно принять само состояние а0.
При минимизации автомата Мура вводится понятие 0-эквивалентности состояний и разбиения множества состояний на 0-классы: 0-эквивалентными называются любые, одинаково отмеченные выходными сигналами, состояния автомата Мура. В качестве примера рассмотрим минимизацию автомата Мура, заданного таблицей переходов и выходов (Таблица 1.14).
Таблица 1.14
Выполним разбиение?0:
? 0={В1, В2, В3};
B1={a1, a2, a8}, В2={а6, а9, а10, а11, а12}, В3={а3, a4, a5, a7}.
Построим таблицу разбиения?0:
Выполним разбиение?1:
1={С1, С2, С3, С4};
C1={a1, a2, a8}, С2={а6, а9, а11}, С3={ а10, a12}, С4={а3, а4, a5, a7}.
Построим таблицу разбиения?1:
Выполним разбиение?2.
1={D1, D2, D3, D4};
D1={a1, a2, a8}, D2={а6, а9, а11}, D3={ а10, a12}, D4={а3, а4, a5, a7}.
Разбиение?2 повторяет разбиение?1 - процедура разбиения завершена.
Выберем произвольно из каждого класса эквивалентности D1, D2, D3, D4 по одному представителю - в данном случае по минимальному номеру: A"={a1, а3, a6, а10}.
Удаляя из исходной таблицы переходов "лишние" состояния, определяем минимальный автомат Мура (табл.1.15.)
Таблица 1.15.
Вывод
В процессе выполнения контрольной работы мы ознакомились с основными понятиями абстрактных цифровых автоматов; типами абстрактных автоматов; способами задания абстрактных автоматов; связью между моделями Мили и Мура; эквивалентными автоматами и эквивалентными преобразованиями автоматов; минимизацией числа внутренних состояний автомата и алгоритмом Ауфенкампа-Хона - привели примеры.
Список литературы
1. Самофалов К.Г., Романкевич А.М., и др. Прикладная теория цифровых автоматов. - Киев. “Вища школа" 1987.
2. Соловьев Г.Н. Арифметические устройства ЭВМ. - М. “Энергия”. 1978.
3. Савельев А.Я. Прикладная теория цифровых автоматов - М. “Высшая школа”. 1987.
4. Каган Б.М. Электронные вычислительные машины и системы. - М. Энергоатомиздат. 1985.
5. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. - Минск. “Вышэйшая школа”. 1980.
верификация систем взаимодействующих процессов;Об этом можно судить по выступлениям на семинаре " 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" вызовет увеличение числа.
