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

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

Владимир 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. Таблица переходов и выходов

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

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

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

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

Рис. 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 0 = y 0 = 0; x 1 = y 1 = 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Абстрактный цифровой автомат А определяется совокупностью пяти объектов где - множество входных сигналов автомата А (входной алфавит автомата А); - множество состояний автомата А (алфавит состояний автомата - множество выходных сигналов автомата А (выходной алфавит автомата А); - функция переходов

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

Иныш словами, функция переходов показывает, что автомат А, находясь в некотором состоянии при появлении входного сигнала , переходит в некоторое состояние Последнее может быть записано также и выражением Функция выходов задающая отображение показывает, что автомат Л, находясь в некотором состоянии при появлении входного сигнала , выдает выходной сигнал Последнее может быть записано выражением

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

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

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

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

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

Абстрактный цифровой автомат называется инициальным, если на множестве его состояний 5 выделяется специальное начальное со стояние т. е. инициальный абстрактный автомат определяется совокупностью шести объектов Выделение на множестве начального состояния объясняется чисто практическими соображениями, связанными с возникающей часто необходимостью фиксировать условия начала работы автомата.

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

состояние Согласно определению абстрактного автомата, автомат Мили в этом случае характеризуется системой уравнений:

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

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

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

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

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

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

Таблица 10.1

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

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

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

Таблица переходов произвольного полностью определенного абстрактного автомата строится следующим образом. Столбцы таблицы помечаются буквами входного алфавита автомата, а строки таблицы - буквами алфавита состояний автомата. В клетке таблицы переходов, находящейся на пересечении столбца, отмеченного входным сигналом и строки, отмеченной состоянием ставится состояние являющееся результатом перехода автомата из состоянии под воздействием входного сигнала что определяется выражением Пример, таблицы переходов некоторого абстрактного полностью определенного автомата с входным алфавитом и алфавитом состояний представлен в табл. 10.1. Если абстрактный автомат частичный, то в клетке таблицы его переходов, находящейся на пересечении столбца, отмеченного входным сигналом и строки, отмеченной состоянием (при условии, что переход из состояния под воздействием входного сигнала неопределен), ставится прочерк, и любое входное слово, приводящее к указанному переходу, является запрещенным. Заполнение остальных клеток аналогично случаю полностью определенного автомата. Пример таблицы переходов некоторого абстрактного частичного автомата с входным алфавитом и алфавитом состояний представлен в табл. 10.2. Вид таблицы переходов не зависит от типа задаваемого автомата (автомат Мура, Мили, С-автомат). Таблицы выходов автомата Мура, Мили, С-автомата имеют различия. Таблица выходов полностью определенного автомата Мили строятся следующим образом. Идентификация столбцов и строк, а также формат таблицы соответствует таблице переходов полностью определенного автомата. В клетке таблицы выходов,

Таблица 10.2

Таблица 10.3

Таблица 10.4

находящейся на пересечении столбца, отмеченного входным сигналом и строки, отмеченной состоянием ставится выходной сигнал который автомат Мили выдает, находясь в состоянии при наличии входного сигнала что определяется выражением Пример таблицы выходов некоторого абстрактного полностью определенного автомата Мили с входным алфавитом алфавитом состояний и выходным алфавитом представлен в табл. 10.3.

Таблица выходов полностью определенного автомата Мура строится более просто: каждому состоянию автомата приписывается свой выходной сигнал. Пример таблицы выходов автомата Мура с алфавитом состояний и выходным алфавитом представлен в табл 10.4.

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

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

Прочерки в некоторых клетках таблицы выходов частичного автомата Мура не связаны с прочерками в клетках его таблицы переходов. Это определяется тем, что выходной сигнал автомата Мура зависит только от состояния, в котором находится автомат. Например, таблица выходов частичного автомата Мура, заданного таблицей переходов (табл. 10.2),

Таблица 10.5

Таблица 10.6.

Таблица 10.7

может быть представлена и как табл. 10.4, если в каждом своем состоянии автомат выдает какой-то выходной сигнал, и как табл. 10.6, если значение выходного сигнала автомата для некоторых состояний неоиределено.

На практике таблицы переходов и выходов автомата часто совмещаются в одну таблицу, называемую отмеченной таблицей переходов автомата. Отмеченная таблица переходов полностью определенного автомата Мили, представленного таблицей переходов (табл. 10.1) и таблицей выходов (табл. 10.3), сведена в табл. 10.7. Отмеченная таблица переходов частичного автомата Мура (табл. 10.2) и таблица выходов (табл. 10.4), сведена в табл. 10.8.

Кроме рассмотренных выше таблиц переходов и выходов, произвольный абстрактный автомат может быть описан матрицей соединений. Такое описание - один из способов матричного задания абстрактных автоматов. Матрица соединений произвольного абстрактного автомата является квадратной и содержит столько столбцов (строк), сколько различных состояний имеет рассматриваемый автомат. Каждый столбец (строка) матрицы соединений помечается буквой состояния автомата. Если автомат инициальный, то первый слева столбец и первая сверху строка матрицы его соединений помечаются буквой начального состояния автомата В клетке матрицы соединений, находящейся на пересечении столбца, помеченного буквой состояния и строки, помеченной буквой состояния автомата, ставится входной сигнал (или дизъюнкция входных сигналов), под воздействием которого осуществляется переход автомата из состояния в состояние Если матрицей соединения задается абстрактный автомат Милн, то рядом с буквой входного сигнала в скобках указывается буква выходного сигнала который автомат Мили выдает, осуществляя переход Матрица соединений некоторого автомата Мили, представленного отмеченной таблицей переходов (табл. 10.7), показана на рис. 10.3.

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

Таблица 10.8

При графическом способе задания абстрактные автоматы представляются ориентированными графами; состояния автомата изображаются вершинами графа, а переходы между состояниями - дугами между соответствующими вершинами. При этом каждой дуге графа приписывается некоторая буква входного алфавита автомата, указывающая, что данный переход автомата осуществляется только при появлении входного сигнала и каждой вершине графа - буква соответствующего состояния автомата. Если графом изображается автомат Мила, то выходные сигналы автомата проставляются на дугах графа (в соответствии с таблицей выходов автомата) рядом с буквой входного сигнала. Пример графа автомата Мили, заданного таблицей переходов (табл. 10.1) и таблицей выходов (табл. 10.3), показан на рис. 10.4. Если графом изображается автомат Мура, то выходные сигналы автомата проставляются около вершин графа (в соответствии с таблицей выходов автомата). Пример графа автомата Мура, заданного таблицей переходов (табл. 10.2) и таблицей выходов (табл. 10.4), показан на рис. 10.5.

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

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

Рассмотрим эквивалентное преобразование автоматов. Эквивалентными называются автоматы, индуцирующие одно и то же отображение множества слов во входном алфавите в множество слов в выходном алфавите. Рассмотрим только преобразование автомата Мура в эквивалентный ему автомат Мили. Преобразование автомата Мили в эквивалентный ему автомат Мура осуществляется несколько сложнее.

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

Разработка реальных автоматов (представленных хотя бы на уровне принципиальных электрических схем) требует их задания сначала на абстрактном уровне с последующим переходом на структурный уровень, учитывающий используемые в схеме автомата логические элементы и связи между ними. В связи с этим возникает задача синтеза абстрактного автомата, исходя из какого-то начального, например, словесного описания его работы. Существующие алгоритмы синтеза абстрактных автоматов на практике обычно не используются из-за сложности и громоздкости вычислеиий и поэтому не включены в материал учебника. Однако для лучшего уяснения понятия абстрактного автомата и способов его задания здесь рассмотрим пример синтеза абстрактного автомата, основываясь на чисто умозрительных соображениях.

Пример. Построить абстрактный цифровой автомат управления переключением спетофора при условии, что на вход автомата поступает только сигнал «переключить светофор». Обозначим этот сигнал буквой а его отсутствие - буквой

Очевидно, входной алфавит X такого автомата будет состоять из двух букв: Так как синтезируемый автомат должен обеспечивать переключение светофора в красный, желтый и зеленый цвет, то введем три соответствующих выходных сигнала управления Положим также, что в момент начала функционирования автомат находится в состоянии Алгоритм работы тривиален; возможное решение для автомата Мили показано на рис. 10.6, а для автомата Мура - на рис. 10.7. Для (упрощения полагаем, что в начальный момент времени автомат Мура выдает выходной сигнал «включить зеленый цвет». Отметим, что для построения графа автомата потребуется ввести четыре различных состояния. Число состояний можно уменьшить, например увеличив число входных сигналов автомата либо расширив возможности автомата в плане запоминания предыстории развития процесса управления во времени (в рассматриваемом примере запоминается только момент выдачи последнего выходного сигнала).

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

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

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

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

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

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

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

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

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

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

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

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

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

Ругать сына;

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

Надеяться;

Радоваться;

Ликовать.

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

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

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

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

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

Состояния;

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

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

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

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

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

На выходе оно выдаёт символы (в общем случае) другого алфавита.

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

Формально абстрактный автомат определяется как пятерка

Ограничение числа параметров абстрактного автомата определило такое понятие как конечный автомат .

Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата и последовательности выходных символов , которые для последовательности символов разворачиваются в моменты дискретного времени 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 нотации В информатике и инженерии программного обеспечения формальными методами называется группа техник, основанных на математическом аппарате для … Википедия

1.1 Основные понятия

1.4 Связь между моделями Мили и Мура

1.5 Эквивалентные автоматы. Эквивалентные преобразования автоматов

1.6 Минимизация числа внутренних состояний автомата

Список литературы

Введение

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

Цель работы - ознакомится с основными понятиями абстрактных цифровых автоматов; типами абстрактных автоматов; способами задания абстрактных автоматов; связью между моделями Мили и Мура; эквивалентными автоматами и эквивалентными преобразованиями автоматов; минимизацией числа внутренних состояний автомата и алгоритмом Ауфенкампа-Хона.

1. Абстрактные цифровые автоматы

1.1 Основные понятия

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

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

Общая теория автоматов подразделяется на абстрактную и структурную.

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

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

Абстрактный цифровой автомат (ЦА) является математической моделью дискретного управляющего устройства.

Абстрактный ЦА определяется множеством, состоящим из шести элементов:

X={x 1 , x 2 ,. x n } - множество входных сигналов (входной алфавит);

Y={y 1 , y 2 , y m } - множество выходных сигналов (выходной алфавит);

А={ a 0 ,a 1 , a 2 ,. а N } - множество состояний (алфавит состояний);

а о - начальное состояние (а о

- функция выходов автомата, задающая либо отображение (XxA)

Иными словами, функция переходов

Функция выходов показывает, что автомат S, находясь в некотором состоянии а j

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

Абстрактный автомат функционирует в дискретном автоматном времени t=0,1,2,. и переходы из состояния в состояние осуществляются мгновенно. В каждый момент tдискретного времени автомат находится в определенном состоянии a (t) из множества А состояний автомата, причем в начальный момент времени t=0 он всегда находится в начальном состоянии а о. В момент времени t, будучи в состоянии a (t), автомат способен воспринять на входном канале сигнал х (t)

1.2 Типы абстрактных автоматов

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

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

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

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

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

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) =

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

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

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

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

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

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

Чтобы задать конечный автомат S, необходимо описать все элементы множества: S={ X,A,Y,

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