Раздел V. Основы теории конечных автоматов
Исторически первыми автоматами были механические устройства, выполнявшие некоторые действия без участия человека. Функции управления в них, как правило, выпол-нялись при помощи разного рода кулачковых механизмов.
Под автоматами в современной трактовке данного тер-мина обычно понимают:
- реальные физические устройства, осуществляющие пре-образование информации, энергии, веществ без непосред-ственного участия человека, либо
- программы, управляющие работой ЭВМ либо других спе-циализированных вычислительных устройств, входящих в состав систем управления роботами.
С точки зрения изучения свойств и основных законо-мерностей структуры и функционирования автоматов оба определения равносильны в том смысле, что работа авто-мата в самом общем виде может быть рассмотрена как про-цесс преобразования некоторой входной информации в требуемую выходную.
Дискретность означает, что:
1) устройство состоит из некоторых неделимых элементов (которые могут относиться к различным типам), соединён-ных между собой некоторым образом;
2) каждый элемент принимает конечное число состояний (обычно два – “включён-выключен” – в механических сис-темах; высокое–низкое напряжение в электрических и т.д.).
Конечность означает, что автомат имеет ограничен-ную физическую структуру.
К дискретным конечным автоматам (в дальнейшем просто - автоматы) относятся все цифровые вычислитель-ные и управляющие системы, а также их элементы, име-
278
ющие дискретную структуру. Наряду с электрическим, дан-ные автоматы могут иметь гидравлический, пневматичес-кий и другие способы физической реализации.
1. Основные понятия теории
1.1. Автоматы Мили. Граф переходов. Однотактные и многотактные автоматы
Определение. Автоматом Мили называют набор А= (Х, Z, Q, F, G), в котором:
1) Х = (Х1,Х2,…,ХN) – множество возможных входов,
2) Z = (Z1,Z2,…,ZM) – множество возможных выходов,
3) Q = (Q1,Q2,…,QР) – множество возможных внутренних состояний,
4) F : Х Q Z - функция выходов,
5) G : Х Q Q - функция переходов.
Определение. Автомат Мили называют инициальным, если указано его начальное состояние в момент времени t=0: Q(t0)=Q0. В этом случае Q(t0) указывается дополни-тельно к набору (Х, Z, Q, F, G).
Схема функционирования любого автомата в графи-ческом виде может быть задана при помощи графа перехо-дов, который также называют диаграммой Мура (диаграм-мой переходов).
Определение. Графом переходов (диаграммой Мура) автомата Мили называется ориентированный граф, в кото-ром множество вершин соответствует множеству всех возможных внутренних состояний автомата, значения вхо-
дов и выходов показаны на ориентированных ребрах (ду-гах), которые показывают направление переходов. Выходы задают после разделительной линии либо в скобках. На-чальное состояние инициального автомата отмечается звез-дочкой.
В качестве входов и выходов у реальных автоматов
279
может использоваться самая различная информация, напри-
мер, звуковая или зрительная.
Рассмотрим пример реального автомата.
Пример. Автомат предназначен для продажи единич-ных изделий двух видов – А и В.
Описание и обозначения входов и выходов. На панели автомата (Рис.5.1) имеется:
Рис.5.1
1. Переключатель I, который включает автомат и за-даёт тип изделия (А или В) и может находиться в одном из трёх возможных положений – “ “, “А” или “В” (Обо-значим данный вид входной информации, соответственно, I=, I=А и I=В). Переключатель сохраняет свое состояние до смены положения.
2. Окно для оплаты II. Если в него опущена сумма, равная стоимости SА изделия А, обозначаем II=SА, если опущена сумма, равная стоимости SВ изделия В, обозначаем II=SВ, иначе (в том числе – и при отсутствии оплаты) II=S.
3. Окно выдачи III . В зависимости от ситуации в дан-ном окне может: а) не производиться никаких действий, б) выдаваться одно изделие типа А, в) одно изделие типа В ли-бо г) производиться возврат внесенной оплаты. Обозначим эти выходные действия, соответственно, как III =, III=А,
280
III =В, III = S .
Общее число N качественно различных действий по вводу информации и оплаты в автомат равно 3+3=6 (по 3 в переключателе I и окне для оплаты II). Присваивая индексы входам, получим:
X1 ={ I= }, X4 ={ II=SА },
X2 ={ I= А }, X5 ={ II=SВ },
X3 ={ I= В }, X6 ={ II= S }.
Общее число М качественно различных внешних действий автомата равно 4. Присваивая индексы выходам, получим:
Z1 ={ III = }, Z3 ={ III =В },
Z2 ={ III =А }, Z4 ={ III = ”Возврат оплаты” }.
Описание функционирования автомата и его внутренних состояний.
1. При положении переключателя I (ввод X1) ав-томат находится в состоянии ожидания. Обозначим его Q= Qож. В этом положении автомат на ввод оплаты в окно II (вводы X4 - X6) должен производить возврат оплаты (выход Z4) и оставаться в состоянии Qож . После перевода переклю-чателя в положение А (ввод X2) автомат переходит в состоя-ние Qв/А выдачи изделия А, после перевода переключателя в положение В (ввод X3) автомат переходит в состояние Qв/В выдачи изделия В . При вводах X1, X2, X3 выход отсутствует (равен Z1) .
2. В состоянии Qв/А выдачи изделия А автомат после ввода суммы SА (ввод X4) выдает изделие А (выход Z2), пос-ле ввода сумм SВ или S (вводы X5, X6) - выводит их обратно (выход Z4), при всех других действиях не выводит ничего (вывод Z1). После ввода X1 - переход в состояние Qож, после X2, X4, X5, X6 – возврат в состояние Qв/А, после X3 - переход в Qв/В .
3. В состоянии Qв/В выдачи изделия В автомат после ввода суммы SВ (ввод X5) выдает изделие В (выход Z3), пос-
281
ле ввода сумм SА или S (вводы X4, X6) - выводит их обратно (выход Z4), при всех других действиях не выполняет ничего (выход Z1). После ввода X1 - переход в состояние Qож, после X3 , X4, X5, X6 – возврат в состояние Qв/В, после X2 - переход в Qв/А .
Множество внутренних состояний автомата имеет вид: Q ={Qож , Qв/A , Qв/В }.
Рассмотрим построение графа переходов.
Решение.
1. На графе отмечаем в кругах все возможные внутренние состояния автомата Q ={Qож , Qв/A , Qв/В }.
2. Подробно опишем построение дуг, выходящих из состоя-ния Qож. После ввода I=А (X2) автомат переходит в состоя-ние Qв/A , при этом в окне выдачи III никаких действий не совершается (Z1). Следовательно, проводится дуга из Qож в Qв/A , на которой ставим обозначение “X2/Z1”. Аналогично проводится дуга из Qож в Qв/В, на которой ставим обо-значение “X3/Z1”. Поскольку при остальных вводах (X1, X4- X6) состояние Qож сохраняется, а выходы должны быть равны, соответственно, (Z1, Z4, Z4, Z4), то соответствующие дуги являются петлями (начинаются и заканчиваются в од-ной вершине графа), на которых стоят обозначения “X1/Z1”, “X4/Z4”,“X5/Z4”,“X6/Z4”.
3. Из вершины Qв/A проводим дугу в вершину Qож с обозна-
чением “X1/Z1”, дугу в вершину Qв/В с обозначением “X3/Z1”, а также петли с обозначениями “X2/Z1”, “X4/Z2”, “X5/Z4”, “X6/Z4”.
4. Из вершины Qв/В проводим дугу в вершину Qож с обозначением “X1/Z1”, дугу в вершину Qв/А с обозначением “X2/Z1”, а также петли с обозначением “X3/Z1”, “X4/Z4”, “X5/Z3”, “X6/Z4”,
Таким образом, граф переходов (Рис.5.2) построен.
282
Рис.5.2
Определение. Однотактными называют автоматы, не имеющие памяти. Их выход Z( ti ) в любой момент времени ti полностью определяется входом X( ti ).
У однотактных автоматов отсутствует память – внут-ренние состояния (Q= ).
Определение. Многотактными называют автоматы, имеющие память. Размер её характеризуется числом р внут-ренних состояний Q = (Q1,Q2,…,QР).
Анализ и синтез однотактных автоматов, имеющих двоичные выходы и входы (функциональные схемы), были даны в алгебре логики. Поэтому далее будут рассматри-ваться только многотактные автоматы.
Задачи.
1. На вход автомата поступает по одному бесконечная слу-чайная последовательность символов “A”, ”B”, ”=”. Ввести множества Q, Х, Z и построить граф переходов для ав-томата, распознающего наличие во входном потоке сочета-ния Х(ti-2)Х(ti-1)Х(ti)= “A=B”. При каждом появлении его автомат должен выдавать значение “Да”, иначе - ”Нет”.
283
2. На вход автомата случайно по одному поступают двоич-ные символы 0 и 1. Ввести множества Q, Х, Z и построить граф переходов для автомата, складывающего в двоичной системе текущий входной символ Х(ti) с предыдущим Х(ti-1). Самый первый символ складывается с нулем.
3. Для входа из Задачи 2 построить граф переходов для ав-томата, умножающего в двоичной системе текущий символ Х(ti) на предыдущий Х(ti-1). Первый символ умножается на единицу.
4. Для входа из Задачи 2 построить граф переходов для ав-томата, инвертирующего текущий символ Х(ti) в том случае, когда предыдущий Х(ti-1) был равен 1, и сохраняющего теку-щий символ при предыдущем 0. Первый символ сохра-няется.
5. Построить граф переходов для распознающего автомата Мили с множествами входов Х = (0,1) и выходов Z = (0,1, 2,3), у которого по парам входных элементов {Х(t1), Х(t2)}, {Х(t2), Х(t3))}, {Х(t3), Х(t4)},…выдаются следующие выход-ные: 000, 011, 102, 113. Предполагаем, что перед первым вводимым элементом был 0.
6. Построить граф переходов для распознающего автомата Мили из Задачи 5, в котором распознаются только непе-ресекающиеся подряд идущие парные комбинации входных элементов {Х(t1), Х(t2)}, {Х(t3), Х(t4))}, {Х(t5), Х(t6)},…