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

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

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

Владимир 2006

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

ОГЛАВЛЕНИЕ

Часть 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

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

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

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

S = 1>

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

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

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

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

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

где: q_j – следующее (новое) состояние автомата; q_i – текущее состояние автомата;
x_k – текущий входной символ;

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

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

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

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

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

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

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

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

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

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

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

Модель Мили.

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

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

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

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

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

Модель Мура.

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

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

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

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

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

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

Автомат Мили

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

Рис. 3. Табличный способ: а – таблица переходов, б – таблица выходов.

а) Таблица переходов

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

Автомат Мура

Таблица переходов и таблица выходов объединяются, и добавляется строка
выходных сигналов, соответствующих состояниям автомата. На рисунке 4 показана таблица переходов и выходов для автомата Мура.

Рис. 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. Автомат для задержки сигнала на один такт (для запоминания на один такт)

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

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

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

1. A= – алфавит состояний – множество состояний, в которых может находиться проектируемый цифровой автомат. Количество состояний играет важную роль при реализации ЦА. Чем больше состояний, тем больше требуется запоминающих элементов(триггеров) для построения ЦА.
2. X= – алфавит входных значений – множество значений, которые могут поступать на вход ЦА. Например , если у автомата двухразрядный двоичный вход, то элементами алфавита могут быть 00, 01, 10 и 11.
3. Y= – алфавит выходных значений – множество значений, которые могут быть установлены на выходе ЦА.
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 .

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

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

Абстрактный автомат называется конечным , если конечны множества А = , Z = , W = . Автомат носит название инициального , если в нем выделено начальное состояние 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

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

Приведенные понятия весьма общи и не конструктивны в случае, когда Q бесконечен. Более узкие классы могут быть выделены путем наложения различных ограничений на компоненты Q, X, Y, W, Ф. Поскольку эти ограничения не формулируются в структурных терминах, то они касаются гл. о. мощности алфавитов (напр., если Q конечен, то и автомат наз. конечным) или общих свойств функций Ф. В случае вырождения, когда тот или иной алфавит состоит из одного символа, удобнее рассматривать модифицированные определения, которые получаются при удалении вырожденных компонент. Напр., детерминированный автомат без выхода — это тройка Ч, где имеют прежний смысл; вероятностный автомат автономный — это пара Р), где W — матрица переходных вероятностей для состояний из Q (т. е. по существу такой автомат является цепью Маркова).

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

Анализ и синтез автоматов в А. т. а. Проблема синтеза заключается в поиске и построении автомата, исходя из условий, предъявляемых к реализуемому им оператору или к представляемому им мн-ву, причем в А. т. а. гл. о. имеются в виду реализация или представление в реальное время. Обычно предполагается, что эти условия выражены на достаточно четком и формализованном языке (т. н. язык заказчика), напр, в виде формулы 21 этого языка. Кроме того, считается, что искомый автомат принадлежит заранее очерченному классу автоматов, допускающих конструктивное описание. Формальный язык, средствами которого осуществляется это описание (язык исполнителя), также считается заданным. Когда речь идет о конечных автоматах, обычно, описание автомата заключается в представлении системы его команд посредством графического или табличного задания функций (матриц переходных и выходныхвероятностей, если автомат вероятностный). Построенный в результате абстрактного синтеза автомат может быть использован впоследствии как исходный материал на этапе синтеза автомата структурного.

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

1) Существование. Существует ли оператор, удовлетворяющий условию, выраженному формулой 21, и реализуемый (мн-во представимое) в автомате данного типа?

2) Единственность. Единственен ли этот оператор? 3) Конструкция. Для к.-н. оператора, удовлетворяющего условию 21, построить реализующий его автомат и указать соответствующую настройку: начальное состояние, заключительные состояния, а в случае вероятностного автомата—допустимый уровень надежности. 4) Минимизация. Построенный автомат ЗЛ привести посредством эквивалентных преобразований к эквивалентному ему автомату, удовлетворяющему

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

Решение указанных проблем мыслится в виде алгоритмов, которые по заданной формуле 91 доставляют ответы на вопросы 1)- 2) и осуществляют необходимые конструкции и преобразования для проблем 3)-4). Соответствующая теория существенно зависит от языков, употребляемых заказчиком; в качестве языка исполнителя обычно рассматриваются различные классы автоматных диаграмм. При выборе языка заказчика естественно руководствоваться следующими двумя (антагонистичными) требованиями: выразительность языка, т. е. удобство (для заказчика) изложения в нем условий, предъявляемых к поведению проектируемого автомата; простота алгоритмов, решающих проблему синтеза в целом и отдельные ее задачи. (Аналогия: в теории программирования — выразительность входного языка и простота транслятора). Эта ситуация подробно исследована применительно к конечным автоматам. G точки зрения простоты алгоритмов предпочтительны алгебр, языки (см. Регулярные события и выражения). Более выразительными являются языки, основанные на применении фрагментов логики предикатов (см. Язык логический для задания автоматов), но и алгоритмы синтеза для них становятся более громоздкими.

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

Эксперименты и синтез. Пусть имеется детерминированный автомат инициальный , который неизвестен экспериментатору или же (при некоторых других постановках) известна лишь какая-то верхняя оценка для числа состояний автомата ЯЛ. Предполагается, что с этим «черным ящиком» можно экспериментировать в том смысле, что можно подавать входные слова и наблюдать соответствующие выходные слова. Задача заключается в такой организации эксперимента, которая позволила бы извлечь полезную информацию о поведении «черного ящика», т. е. об операторе , который реализуется этим «черным яшиком» в реальное время; в лучшем случае — построить автомат, эквивалентный или по крайней мере установить достаточно характерные свойства оператора . Эта задача связана и с проблемой абстрактного синтеза в следующей ситуации, часто встречающейся в инженерной практике (см. Язык анкетный для задания автоматов). Заказчик задумал вполне определенный оператор, который должен реализовать проектируемый автомат, однако он не в состоянии описать этот оператор на языке исполнителя. В таком случае исполнитель пытается путем подходящего опроса заказчика (выступающего здесь в роли «черного ящика») разгадать задуманный им оператор. Осн. результаты относятся к экспериментам с конечными автоматами. В последнее время имеется продвижение и для некоторых классов бесконечных автоматов.

Для конечных автоматов существует алгоритм экспериментирования, который при наличии верхней оценки для числа состояний автомата ЯЛ полностью восстанавливает (расшифровывает) его поведение, т. е. строит автомат, эквивалентный «черному ящику». Если же экспериментатор не располагает такой верхней оценкой, то алгоритм расшифровки невозможен; однако и в этой ситуации разработаны процедуры (называемые частными алгоритмами расшифровки), которые хотя и не для всех «черных ящиков», но для подавляющего большинства их (при разумном определении «большинства») все же устанавливают поведение. В теории экспериментов установлены и достаточно точные оценки сложности алгоритмов расшифровки (напр., оценка длины входных слов, для которых необходимо вести наблюдение). В случае частотных алгоритмов расшифровки они существенно зависят от того, с какой частотой гарантируется правильная расшифровка. Эти результаты основаны на детальных оценках параметров и спектров поведения (см. Оператор автоматный).

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

Лит.: Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464-469]; Бюхи Д. Р.

О разрешающем методе для ограниченной арифметики второго порядка. В кн.: Кибернетический сборник, в. 8. М., 1964; Цетлин М. Л, Исследования по теории автоматов и моделированию биологических систем. М., 1969 [библиогр. с — 306—316]; Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (Поведение и синтез). М., 1970 [библиогр. с. 389—395]. Б. А. Трахтенброт.

Источники:

http://allrefrs.ru/5-26385.html
http://dvoris.ru/osennyaya-obuv/primery-abstraktnyh-avtomatov-vypolnyayushchih-poleznye-deistviya/
http://scask.ru/f_book_kiber1.php?id=4