Введение
"Теория автоматов" - является одной из важных компонент федерального государственного стандарта по направлению "Информатика и вычислительная техника".
Теория автоматов имеет широкие возможности применения:
Проектирование систем логического управления;
Обработка текстов и построение компиляторов;
Спецификация и верификация систем взаимодействующих процессов;
Языки описания документов и объектно-ориентированных программ;
Оптимизация логических программ др.
Об этом можно судить по выступлениям на семинаре "Software 2000…" ученых и специалистов.
Дуг Росс: "…80 или даже 90 % информатики (Computer Science) будет в будущем основываться на теории конечных автоматов…"
Herver Gallaire: "Я знаю людей из "Боинга", занимающихся системами стабилизации самолетов с использованием чистой теории автоматов. Даже трудно себе представить, что им удалось с помощью этой теории. "
Brian Randell : "Большая часть теории автоматов была успешно использована в системных программах и текстовых фильтрах в ОС UNIX. Это позволяет множеству людей работать на высоком уровне и разрабатывать очень эффективные программы".
1.1. Основные понятия и определения.
Простейший преобразователь информации (рис.1.1,а) отображает некоторое множество элементов информации Х, поступающее на вход, в некоторое множество на выходе Y. Если множества Х и Y являются конечными и дискретными, то есть преобразование осуществляется в дискретные моменты времени, то такие преобразователи информации называются конечными преобразователями. Элементы множеств Х и Y в этом случае предварительно кодируют двоичными кодами и строят преобразование одного множества в другое.
Результат преобразования $$F: X \to Y$$ зачастую зависит не только от того, какая информация в данный момент появилась на входе, но и от того, что происходило раньше, то есть от предыстории преобразования. Например, один и тот же вход - извинение соседа после того, как он вам наступил на ногу в переполненном автобусе - вызовет у вас одну реакцию в первый раз и совсем другую - в пятый раз.
(рис 1.1)
Таким образом, существуют более сложные преобразователи информации (ПИ), реакция которых зависит не только от входных сигналов в данный момент, но и от того, что было раньше, от входной истории. Такие ПИ называются автоматами (схемами с памятью). В этом случае говорят об автоматном преобразовании информации (рис.1.1,б). На один и тот же входной сигнал автомат может реагировать по-разному, в зависимости от состояния, в котором он находился. Автомат меняет свое состояние с каждым входным сигналом.
Рассмотрим несколько примеров.
Пример 1Карпов Ю.Г. Теория автоматов-СПб.:Питер, 2003 . Автомат, описывающий поведение "умного" отца.
Опишем поведение отца, сын которого учится в школе и приносит двойки и пятерки. Отец не хочет хвататься за ремень каждый раз, как только сын получит двойку, и выбирает более тонкую тактику воспитания. Зададим такой автомат графом, в котором вершины соответствуют состояниям, а дуга из состояния s в состояние q, помеченное x/y, проводится тогда, когда автомат из состояния s под воздействием входного сигнала х переходит в состояние q с выходной реакцией y. Граф автомата, моделирующего умное поведение родителя, представлен на рис.1.2.
Этот автомат имеет четыре состояния $$\{ S_0, S_1, S_2, S_3\}$$, два входных сигнала - оценки $$\{ x_2, x_5 \}$$ и выходные сигналы $$\{ y_0, y_1, y_2, y_3, y_4, y_5 \}$$, которые будем интерпретировать как действия родителя следующим образом:
$$y_0$$ - брать ремень;
$$y_1$$ - ругать сына;
$$y_2$$ - успокаивать сына;
$$y_3$$ - надеяться;
$$y_4$$ - радоваться;
$$y_5$$ - ликовать.
(рис 1.2)
Сына, получившего одну и ту же оценку - двойку, ожидает дома совершенно различная реакция отца в зависимости от предыстории его учебы. Например, после третьей двойки в истории $$(х_2, х_2, х_2) $$ сына встретят ремнем, а в истории $$(х_2, х_2, х_2, х_5, х_2)$$ будут успокаивать и т.д.
Конечный автомат может быть реализован как программно, так и аппаратно. Программную реализацию можно выполнить на любом языке высокого уровня разными способами. На рис.1.3 представлена блок-схема программы, реализующей поведение автомата примера 1. Нетрудно увидеть, что топология блок-схемы программы повторяет топологию графа переходов автомата. С каждым состоянием связана операция NEXT, выполняющая функцию ожидания очередного события прихода нового входного сигнала и чтения его в некоторый стандартный буфер х, а также последующий анализ того, какой это сигнал. В зависимости от того, какой сигнал пришел на вход, выполняется та или иная функция $$y_0 ... y_5$$ и происходит переход к новому состоянию.
(рис 1.3)
Аппаратную реализацию автомата рассмотрим во второй части этого раздела.
Пример 2. "Студент"
Автомат, модель которого представлена на рис.1.4, описывает поведение студента и преподавателей.
(рис 1.4)
$$\{S_0 ,S_1 ,\dots , S_5,\} $$ - состояния;
$$\{x_1, x_2, x_3\}$$ - входные сигналы: "н", "2" и "5".
$$\{y_1, y_2, y_3,\dots , y_7\}$$ - выходные реакции:
$$y_1$$ - отмечаем "н";
$$y_2$$ - успокаивать;
$$y_3$$ - хвалим студента;
$$y_4$$ - поощряем;
$$y_5$$ - надеемся;
$$y_6$$ - предупреждаем;
$$y_7$$ - отчисляем;
Пример 31. Электронные часы (рис.1.5).
Электронные часы разнообразных функциональных возможностей являются одним из наиболее широко применяемых в быту электронных приборов, управление которыми построено на основе конечноавтоматной модели. Они обычно показывают: время, дату; у них имеется функции такие как "установка времени и даты", "Секундомер", "Будильник"и т.п. Упрощенная структурная схема электронных часов показана нарис.1.5
(рис 1.5)
Регистры отображают либо время, либо дату, либо секундомер в зависимости от "Управления". Устройство управления построено на основе модели конечного автомата. Конечный автомат реагирует на нажатия кнопки "а" на корпусе переходом в состояние "Установка минут", в котором событие нажатия кнопки "b" вызовет увеличение числа. Устройство управления построено на основе модели конечного автомата, граф которого показан нарис.1.6
(рис 1.6)
Итак. С одной стороны АВТОМАТ - устройство, выполняющее некоторые действия без участия человека. С другой стороны, АВТОМАТ - математическая модель, описывающая поведение технического устройства. В данном случае реальное устройство, система и т.д. рассматривается как некоторый "ЧЁРНЫЙ ЯЩИК" (рис.1.7).
(рис 1.7)
Абстрактный автомат - это математическая модель, описывающая техническое устройство совокупностью входных, выходных сигналов и состояний, кроме того:
имеет множество внутренних состояний $$А=\{ а_1(t), а_2(t), а_3(t), а_m(t)\}$$, называемых состояниями автомата;
на вход автомата поступает конечное множество входных сигналов $$Z=\{ z_1(t), z_2(t), z_3(t), \dots, z_f(t)\};$$
имеется конечное множество выходных сигналов $$W=\{ w_1, w_2, w_3, \dots w_g\}$$ ;
задана функция перехода $$\delta(a,z)$$ ;
задана функция формирования выходов автомата $$\lambda(a,z)$$ ;
определено начальное состояние автомата $$а_1 \in А$$.
То есть для описания автомата нужно использовать шестёрку вида $$S=\{A, Z, W, \sigma, \lambda, а_1\}$$, где
$$A=\{ a_1, a_2, a_3, \dots a_М\};$$
$$Z=\{ z_1, z_2, z_3, \dots z_F\};$$
$$W=\{ w_1, w_2, w_3, \dots w_G\};$$
$$\delta : A * Z \to A ( a_s=\delta( a_m, z_i) | a_s \in А);$$
$$\lambda : A*Z \to W ( w_s= \lambda( a_m, z_i) | a_s \in А, w \in W );$$
$$a_1 \in А$$.
Автомат реализует некоторое отображение множества слов входного алфавита Z в множество слов выходного алфавита W.
Автомат называется конечным, если множество его внутренних состояний и множество значений входных сигналов есть конечные множества.
Автомат называется синхронным, если интервал временной дискретизации постоянен, в противном случае говорят об асинхронном автомате.
Автомат называется детерминированным, если поведение автомата в каждый момент времени однозначно определено ( $$z_i, a_i$$,)
В зависимости от способа определения выходного сигнала в синхронных автоматах различают:
Автомат первого рода ( Автомат Мили )$$a(t+1)=\delta( a(t),Z(t)); где\ t=0,1,2,\dots$$
$$W(t)=\lambda( a(t), Z(t))$$ ;
Автомат второго рода ( Автомат Мура )$$A(t+1)=\delta( a(t),Z(t)) $$,
$$W(t)=\lambda( a(t)); где\ t=0,1,2,\dots$$
$$W(t+1)=\lambda(a(t+1))=\lambda(\delta( a(t), z(t)))$$
1.2. Методы задания автоматов
Для задания конечного автомата S требуется описать все элементы множества
$$S=\{A, W, Z, \delta, \lambda, а_1\},$$
наиболее часто используемой формой описания элементов множества S используется табличный, графический, матричный способы.
Теоретико-множественное представление автоматов.
Для задания конечного автомата $$S={A, Z, W, \delta, \lambda, a_1}$$ все элементы множества должны быть заданы явно. Так для автомата Мили:
$$A=\{a_1, a_2, \dots, a_M\}$$ - алфавит состояний;
$$W=\{w_1, w_2,\dots, w_G\}$$ - выходной алфавит;
$$Z=\{z_1, z_2, \dots,z_F\}$$ - входной алфавит;
$$\delta: A \times Z \to A(a_s = \delta (a_m,z_i)/a_s \inA);$$
$$\lambda: A \times Z \to W(w_s = \lambda (a_m, z_i)/ a_s \in A, w \in W);$$
$$a_1 \in A$$ - начальное состояние автомата.
Например, автомат Мили $$S_1=( A, Z, W, \delta, \lambda, a_1)$$, представленный в табл.1.3 в явной форме описывается так:
$$A=\{a_1, a_2, a_3 \}; Z= \{ z_1, z_2\}; W= \{ w_1, w_2\}; \delta: a_2= \delta( a_1 , z_1); a_3= \delta( a_1 , z_2); a_1= \delta( a_2 , z_1); a_3= \delta( a_2 , z_2); a_3= \delta( a_3 , z_1); a_2= \delta( a_3 , z_2); \lambda: w_1= \lambda( a_1 , z_1); w_2= \lambda ( a_1 , z_2); w_2= \lambda ( a_2 , z_1); w_1= \lambda ( a_2 , z_2); w_1= \lambda ( a_3 , z_1); w_2= \lambda ( a_3 , z_2).$$
Автомат Мура $$S_2=( A, Z, W, \delta, \lambda, a_1)$$, представленный в табл.1.8 в явной форме описывается так:
$$A=\{a_1, a_2, a_3 , a_4, a_5 \}; Z= \{ z_1, z_2, z_3\}; W= \{ w_1, w_2, w_3\}; \delta: a_2= \delta( a_1 , z_1); a_1= \delta( a_1 , z_2); a_4= \delta( a_2 , z_3); a_1= \delta( a_2 , z_1); a_5= \delta( a_2 , z_2); a_3= \delta( a_2 , z_3); a_1= \delta( a_3 , z_1); a_2= \delta( a_3 , z_2); a_5= \delta( a_3 , z_3); a_1= \delta( a_4 , z_1); a_5= \delta( a_4 , z_2); a_2= \delta( a_4 , z_3); a_1= \delta( a_5 , z_1); a_3= \delta( a_5); a_4= \delta( a_5 , z_3); \lambda: w_1= \lambda( a_1); w_3= \lambda ( a_2); w_2= \lambda ( a_3); w_1= \lambda ( a_4); w_3= \lambda ( a_5).$$
Табличная форма.
Табличная форма для автомата Мили иллюстрируется табл.1.1 (переходов) и табл.1.2 (выходов).
| z f \a m |
a 1 |
… |
a M |
|---|
| z1 | $$\delta (a_ 1 , z_1)$$ |
|
$$\delta (a_ M , z_1)$$ |
|---|
| … | … |
… |
… |
|---|
| z F | $$\delta (a_ 1 , z_F)$$ |
|
$$\delta (a_ M , z_F)$$ |
|---|
| z f\a m |
a 1 |
… |
a M |
|---|
| z1 | $$\lambda (a_ 1 , z_1)$$ |
|
$$\lambda (a_ M , z_1)$$ |
|---|
| … | … |
… |
… |
|---|
| z F | $$\lambda (a_ 1 , z_F)$$ |
|
$$\lambda (a_ M , z_F)$$ |
|---|
Строки этих таблиц соответствуют входным сигналам, а столбцы - состояниям, причем крайний левый столбец обозначен начальным состоянием $$а_1$$. На пересечении столбца $$a_m$$ и строки $$z_f$$ …. в таблице переходов ставится функция перехода $$\delta (a_ m , z_f)$$, то есть состояние, в которое автомат переходит из состояния $$a_m$$ под действием входного сигнала $$z_f,$$ а в таблице выходов - выходная функция $$\lambda (a_m , z_f)$$, то есть соответствующий этому переходу выходной сигнал $$w_g$$.
Пример табличного способа задания автомата Мили показан в табл. 1.3 (переходов) и табл. 1.4 (выходов).
| z f \a m |
a1 |
a2 |
a3 |
|---|
| z1 | a2 |
a1 |
a3 |
|---|
| z2 | a3 |
a3 |
a2 |
|---|
| |
|
|
|---|
| z f \a m |
a1 |
a2 |
a3 |
|---|
| z1 | w1 |
w2 |
w1 |
|---|
| z2 | w2 |
w2 |
w2 |
|---|
| |
|
|
|---|
Автомат называется частично заданным, если он определен не для всех пар переходов ( $$a_m, z_f$$ ). Для частично заданного автомата на месте отсутствующего перехода ставится прочерк как в таблице переходов, так и в таблице выходов.
Пример табличного способа задания частичного автомата показан в табл.1.5 (переходов) и табл.1.6 (выходов).
| z f\ a m |
a 1 |
a2 |
a 3 |
a 4 |
|---|
| z1 | a 2 |
a 1 |
a 3 |
- |
|---|
| z2 | a 3 |
a 3 |
a - |
a 1 |
|---|
| z3 | - |
a4 |
a2 |
a4 |
|---|
| z f\ a m |
a 1 |
a2 |
a 3 |
a 4 |
|---|
| z1 | w1 |
w 2 |
w 1 |
- |
|---|
| z2 | w 2 |
w1 |
- |
w 2 |
|---|
| z3 | - |
w1 |
w2 |
w1 |
|---|
Табличная форма задания автомата Мура представляет собой совмещенную табл.1.7, в которой выходной сигнал, соответствующий состоянию в $$a_m$$ автомате Мура размещен в верхней строке над соответствующими состоянием, а остальная информация аналогична представлению автомата Мили.
Пример представления автомата Мура приведен в табл.1.8.
| \wG |
w1 |
|
wG |
|---|
| zf\ am | a 1 |
… |
am |
|---|
| z1 | $$\delta (a_ 1 , z_1)$$ |
|
$$\delta (a_ M , z_1)$$ |
|---|
| … | … |
… |
… |
|---|
| zF | $$\delta (a_ 1 , z_F)$$ |
|
$$\delta (a_ M , z_F)$$ |
|---|
| \ wG |
w1 |
w3 |
w2 |
w1 |
w3 |
|---|
| zf\ am | a 1 |
a2 |
a3 |
a4 |
a5 |
|---|
| z1 | a2 |
a1 |
a1 |
a1 |
a1 |
|---|
| z2 | a3 |
a5 |
a2 |
a5 |
a3 |
|---|
| z3 | a4 |
a3 |
a5 |
a2 |
a4 |
|---|
Графовая форма задания абстрактных автоматов
В данном случае автомат $$S=\{A, Z,W, \delta, \lambda, a_1\}$$ представляется графом, в котором:
множество $$А$$ изображено вершинами графа;
функция $$\delta$$ задана дугами графа, причем две вершины графа $$a_m$$ и $$a_s$$, соединяются дугой, если в автомате существует переход из $$a_m$$ в $$a_s$$ ;
множество $$Z$$ изображено метками дуг: $$z_f$$ ставится на дуге из вершины $$a_m$$ в вершину $$a_s$$, если в автомате существует переход из $$a_m$$ в $$a_s$$ под действием входного сигнала $$z_f$$ ;
функция $$\lambda$$ задана метками дуг или вершин: для автомата Мили дуга из вершины $$a_m$$ в вершину $$a_s$$ помечается выходным сигналом $$w_g$$, если в автомате существует переход из $$a_m$$ в $$a_s$$ и при этом вырабатывается выходной сигнал $$w_g$$ ; а для автомата Мура выходным сигналом $$w_g$$ помечается вершина, определяющая $$a_s= \lambda (a_m)$$.
На рисунке 1.8 приведены примеры описания автомата Мили и автомата Мура:
(рис 1.8)
Матричная форма
Для автомата Мили матричная форма состоит из матрицы $$C = |c_{ms}|$$ размерностью $$M \times M$$, где каждый элемент матрицы $$c_{ms}=z_f/w_g,$$ стоящий на пересечении $$m$$ -ой строки и $$s$$ -го столбца соответствует входному сигналу $$z_f$$, вызывающему переход из состояния $$a_m$$ в состояние $$a_s$$ с выработкой выходного сигнала $$w_g$$. Пример матричного описания автомата Мили показан ниже.
$$С=\left|\left|\begin{array}{ccc}
z_2/w_1 - z_1/w_1\\
z_1/w_1 - z_2/w_2\\
z_1/w_2 z_2/w_1 - \end{array}\right|\right|$$
$$С=\left|\left|\begin{array}{cccсс}
- z_1 - z_1 - \\
- - z_2 - z_1\\
- z_2 - z_1 -\\
- - z_1 - z_2\\
z_2 - - z_1 - \end{array}\right|\right|$$
$$W=\left|\left|\begin{array}{c}
w_1\\
w_2 \\
w_3\\
w_2 \\
w_3 \end{array}\right|\right|$$
Для автомата Мура матричная форма состоит из матрицы $$C = |c_{ms}|$$ размерностью $$M \times M$$, где каждый элемент матрицы $$c_{ms} =z_f$$, стоящий на пересечении $$m$$ -ой строки и $$s$$ -го столбца, соответствует входному сигналу $$z_f$$, вызывающему переход из состояния $$a_m$$ в состояние $$a_s.$$ Так как выходной сигнал $$w_g$$. в автомате Мура зависит только от состояния, следовательно, выходные сигналы могут быть представлены матрицей-столбцом. Пример матричного описания автомата Мура показан на формуле, приведенной выше.
