Синхронный и асинхронный автомат

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

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

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

На практике теория автоматов активно используются в следующих областях:

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

2. Разработка лексических анализаторов. (Лексический анализатор – это часть компилятора, основная функция которой выделение из исходного текста программы отдельных лексем - идентификаторов, ключевых слов, знаков пунктуации и т.д.)

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

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

5. Автоматное программирование.

Определение абстрактного автомата. Понятие автомата как «черного ящика». Понятие состояния. Входной и выходной алфавит автомата. Функции переходов и выходов автомата. Начальное состояние автомата.

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

A = {X, Y, S, δ, λ, s₀}

· X = {x₁, ... , x_n}; – множество входных символов

· Y = {y₁, ... , y_k}; множество выходных символов

· S = {s₁, ... , s_m}; множество состояний автомата

· δ:S´X®S – функция переходов

· λ: S´X®Y – функция выходов:

· s₀ ÎS – начальное состояние автомата.

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

Автомат - чёрный ящик.

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

t – дискретное время: t = nT,

T – интервал (такт), разделяющий дискретные моменты времени;

если T = 1, то t =n,

Такты определяются либо принудительно тактирующими синхросигналами, либо асинхронно, наступлением внешнего события – поступления сигнала.

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

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

Множество состояний это множество величин, не являющихся входными воздействиями, от которых также зависит реакция системы.

λ: X´ S ®Y , т.е. y_l = λ (s_i, x_k);

Функция выходов определяет выходной сигнал (y_l Î Y) системы в зависимости от входного сигнала (x_k Î X),и текущего состояния(s_i Î S).

δ: X´ S ®S , т.е. s_j = δ(s_i, x_k),

Функция переходов определяет, в какое состояние (s_j Î S) перейдет система в зависимости от входного сигнала (x_k Î X) и текущего состояния (s_i Î S).

Автоматы Мура и Мили. Детерминированные и недетерминированные автоматы.

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

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

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

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

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

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

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

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

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

y(t) = λ(s(t))

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

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

Детерминированный автомат – автомат, в котором имеется полная определенность переходов из всех состояний в зависимости от входных сигналов (под действием одного и того же сигнала автомат не может переходить из любого рассматриваемого состояния в различные состояния). В таблице переходов детерминированного полностью определенного автомата запалены все ячейки, и в каждой ячейки находится ровно одно значение. На графе переходов детерминированного автомата из каждой вершины исходит только одна дуга, помеченная входным сигналом x (xÎX).

Синхронный и асинхронный автомат.

Автомат называется асинхронным, если каждое его состояние s_i Î S (i = 1, … , n) устойчиво;

Состояние автомата si называется устойчивым, если для любого входного сигнала хk , такого, что δ(sj , xk) = si , справедливо соотношение: δ(si , xk) = si , где sj – состояние, предшествующее si.

Иными словами, автомат не изменяет своего состояния при повторении на следующем такте сигнала, приведшего его в состояние si .

Устойчивость состояний в асинхронных автоматах достигается введением специальных сигналов синхронизации.

Если в автомате есть хотя бы одно неустойчивое состояние, он называется синхронным.