Теория автоматов

Минимизация КА
Из примера 3.2 видно, что разные автоматы могут функционировать одинаково, даже если у них разное число состояний. Важной задачей является нахождение минимального автомата, который реализует заданное автоматное отображение.
Эквивалентными естественно назвать два состояния автомата, которые нельзя различить никакими входными экспериментами.

Минимизация КА
Определение 3.7. Два состояния р и q конечного автомата А -
называются эквивалентными (обозначается p«q), если (VaG X*)X*(p, a) =X*(q, a).
Для автомата (рис. 3.8, а) состояния qO и q2 эквивалентны: любая входная цепоч­ка, поданная на автомат, находящийся в состоянии qO, даст такую же реакцию, как и в случае, когда автомат вначале находился в состоянии q2. Эквивалентные со­стояния можно объединить в один класс и построить новый автомат, состояниями которого являются классы эквивалентных состояний (см. рис. 3.8, а). Эквивалент­ные состояния объединены в классы, эти классы и являются состояниями нового автомата (рис. 3.8, б). Если мы можем определить на множестве состояний авто­мата «максимально возможное» разбиение на классы эквивалентности, то, выби­рая его классы эквивалентности как новые состояния, получим минимальный ав­томат, эквивалентный исходному

Минимизация КА
Рис. 3.8. Классы эквивалентных состояний произведения конечных автоматов примера 3.

Минимизация КА
Определение 3.7 не является конструктивным: оно не дает нам процедуры выяс­нения того, являются ли два состояния эквивалентными, поскольку мы не можем перебрать все входные цепочки. Однако существует алгоритм определения макси­мального отношения эквивалентности на множестве состояний конечного авто­мата, который мы сейчас и рассмотрим.
Алгоритм состоит в последовательном построении на множестве состояний автома­та А разбиений я0, яь ..., я*,, таких, что в один класс разбиения 7ik попадают k-эк-вивалентные состояния, то есть те, которые неразличимы входными цепочками /фшной k. Такие состояния будем считать находящимися в отношении эквивалент­ности «k. Если -n(p«k q), то р и q назовем k-различимыми. Из определения 3.7: Р ~k Я <=> (Vae X*, | a | < k)X*(p, a) = X*(q, a).

Минимизация КА
Очевидно, что в любом автомате все состояния 0-эквивалентны, поскольку при подаче пустой цепочки на вход автомата (цепочки длины 0) выходом является также пустая цепочка независимо от состояния, в котором автомат находится. Следующее разбиение ъ также легко построить. Действительно, по определению в один блок щ попадают все состояния, в которых автомат одинаково реагирует на входные сигналы: р ^{ q <=> (Vxe Х)А,(р, х) = X(q, x). Разбиения я0, содержащее один единственный блок, в который входят все состоя­ния автомата, и п\, в каждом блоке которого собраны состояния, не различимые входными сигналами, являются исходными при построении цепочки разбиений я0, п 1,..., я*,. Если мы сможем определить, как строить следующее разбиение из преды­дущего, то начиная мы сможем последовательно построить и всю цепочку.

Минимизация КА
Теорема 3.2. Пусть р «k q, k >1. Для того чтобы p«k+iq> необходимо и достаточно, чтобы (Vx е Х)8(р, х) «k 8(q, x). Иными словами, для того, чтобы два эквивалентных состояния конечного автомата были бы k+1 -эквивалентными, необходимой достаточно, чтобы под воздействием любого входного сигнала автомат переходил из этих состояний в пару состояний, которые сами были бы эквивалентными.
Легко понять справедливость этой теоремы. Действительно, для того чтобы вход­ная цепочка длины k+1, например цепочка X0x1x2...xk, не различала пару состоя­ний р и q, нужно всего лишь, чтобы автомат из этих состояний переходил под воз-действием х0 в такие состояния, которые не различимы цепочкой XiX2...Xk, то есть чтобы 8(р, х0) и 5(q, xq) были бы k-неразличимы (см. рисунок

Минимизация КА
Докажем теорему формально.

Минимизация КА
(Необходимость.) Нужно доказать р «k+1 q =» (Vx € X)6(p, x) «k 8(q, x). Докажем контрапозицию: (ЭхеХ)[-т8(р, х) «k5(q, х)] =» ->р «k+i q. Если состояния §(р, х) и 8(q, х), в которые попадает автомат из р и q под воздействием х, различимы, то пусть xtx2.. .Xk — цепочка входных сигналов, их различающая. Тогда, очевидно, це­почка х XiX2.. .xk длиной k+1 различает р и q.
(Достаточность.) Нужно доказать (Vx e X)8(p, x) «k 8(q, x) =» р «k+j q, если р «k q при k > 1. Из определения расширенной функции переходов
Х*(р, х<*) =i(p, х)Я*(8(р, х)о) и X*(q, xo) = X(q, x)X*(8(q,x)o).
Поскольку k > 1 и р «kq, Х(р, х) = X(q, x). Из того, что 8(р, х) и 8(q, x) k-эквивалентны, следует, что (Va e Xk )Я * (5 (р, x)a) = Я * (8 (q, x )a). Следовательно, для любых цепочек Р длины k+1, Х*(р, Р) = A,*(q, Р), то есть р «k+1 q, что и требовалось доказать

Минимизация КА
Очевидно, что если р и qk+1-эквивалентны, то они k-эквивалентны. Иными сло-вами,,блоки разбиения яk+1 являются подблоками разбиения Я|<. Поскольку число состояний конечно, может быть только конечное число последовательно умень­шающихся разбиений Tik, начиная с максимального разбиения Я0, содержащего один единственный блок. Более того, очевидно, что их не больше, чем N-число состоя­ний автомата. Однако последовательное построение уменьшающихся разбиений я г можно не продолжать дальше, как только два последовательных разбиения со­впадают.
Теорема 3.3. Пусть 7tk+i *" я^ Тогда для любого i > k, n\e я^.
Доказательство. Из доказанного выше следует, что:
(Vp, qG S)p «ktl q <=> р «k q&(Vxe X)5(p, x) «k S(q, x).
Обозначим R(p, q, k) = (Vxe X)5(p, x) «?k 5(q, x)» Тогда доказанное утверждение теоремы 3.2 запишется: (Vp,qeS)p«k+1q<=»p«kq&R(p,q,k).

Минимизация КА
Пусть теперь р «r+i q - р «r q. Тогда (Vp, q € S)p «r q <=» p »r q&R (p, q, k). Но это зна­чит, что (Vp, qeS)p«r q=>R(p, q, r).
Предположим теперь, что для некоторого i > г «i' - «г, но «}+i * «j. Это значит, что -i[(Vp, qe S)p «j q =» R(p, q, i)]. Однако, поскольку «{ e »„ a R зависит только от «ь это противоречит утверждению (Vp, qe S)p «r q => R(p, q, г) и, следовательно, наше предположение неверно, что и требовалось доказать.
Начальное разбиение представляет собой один блок, включающий все состояния, поскольку входные цепочки длиной 0 (пустая цепочка е) не различают состояний: независимо от того, в каком состоянии автомат находился при подаче входа е, вы­ходом тоже будет е. Поэтому
я0-{Аов<1,2,3,4,5,6,7,8,9>}.

Минимизация КА
Разбиение ki в один блок объединяет те состояния, которые нельзя различить при подаче цепочек длиной 1. Функция выходов X при подаче а и b не может различить 1,3, 5, 6,8 и 9, поскольку для каждого из этих состояний при подаче на вход авто­мата а он выдает 1, а при подаче на вход b он выдает 0. Состояния 2,4 и 7 попадают в другой блок, но между собой входной цепочкой длины 1 их различить нельзя. Поэтому:
Я1 - {Ai - <1,3,5,6,8,9>; Bt - <2,4,7>}.
Следующее разбиение я2 объединяет в один блок те состояния, которые нельзя различить при подаче цепочек длиной 2. Перебирать все такие цепочки долго, по­этому воспользуемся теоремой 3.2. В соответствии с ней, в один блок разбиения 7tk+i попадут те состояния р и q, для которых справедливо (Vxe X)5(p, x) «k 5(q, x).

Минимизация КА
Как было установлено выше, эти состояния должны быть из одного блока преды­дущего разбиения. Обратимся к построению я2. Построим таблицу переходов, но вместо значения состояния 8(р, х) будем писать номер блока разбиения я^ в кото­рое попадает 5(р, х). Так, 8(3, а) - 1, а это состояние находится в блоке ai. Анало­гично, 8(3, Ь) - 4, а это состояние находится в блоке bi.
После такого построения видно, что состояния 1,3,5, б, 8 и 9 нужно разбить на три блока: <1, 5, 6>, <3, 9> и <8>. Состояния 2, 4 и 7 попадают в одни и те же блоки предыдущего разбиения яь поэтому они попадут в один и тот же блок разбиения я2. Итак:
я2 - {А2 - <1,5, б>; В2 - <2,4,7>; С2 - <3,9>; D2 - <8>}.

Минимизация КА
Аналогично строится Яз. При его построении не нужно проверять, в какой блок Я2 будет переходить автомат из состояния 8, поскольку оно единственное в блоке раз­биения я2, и поэтому далее дробиться этот блок не будет. Таким образом,
я3 - {А3 - <1,5, б>; В3 - <2>; С3 -<4,7>; D3 = <3,9>; Е3 - <8>}.
Разбиение я4 совпадает с разбиением я3. На основании теоремы 3.3 искомое раз­биение я,» совпадает с Я3. Итак, минимальный автомат с эквивалентным поведени­ем имеет 5 состояний, представляющих блоки разбиения я3, а его функции пере­ходов и выходов определяются так: 8(А3, а) = D3,8(А3, Ь) - А3, Х(А3, а) - 1 и т. д..

Автоматы Мили и Мура
Рассмотренная выше модель называется автоматом Мили. Автоматы Мура об­разуют другой класс моделей, с точки зрения вычислительной мощности полно­стью эквивалентный классу автоматов Мили. В автомате Мура А =
выходная функция Л определяется не на паре <состояние, входной сигнал>
а только на состоянии: X: S-»Y. Пример конечного автомата Мура представлен на рис. 3.9, а. Здесь выход автомата определяется однозначно тем состоянием, в которое автомат переходит после приема входного сигнала. Например, в состо­яние si можно прийти по трем переходам: из состояния sO под воздействием Ь, из состояния s2 под воздействием Ь, из состояния si под воздействием а. Во всех трех случаях выходная реакция автомата одна и та же: выходной сигнал у2. Оче­видно, что по любому автомату Мура легко построить эквивалентный ему авто-мат Мили; для автомата Мура (рис. 3.9, а) эквивалентный ему автомат Мили изоб­ражен на рис. 3.9, б

Автоматы Мили и Мура
Рис. 3.9. Автомат Мура (а) и эквивалентный ему автомат Мили

Автоматы Мили и Мура
Не столь очевидно, что справедливо и обратное: для любого автомата Мили суще­ствует эквивалентный ему автомат Мура. Справедливость этого утверждения лег­ко доказывается конструктивно. Рассмотрим рис. 3.10. Каждое состояние s авто­мата Мили (см. рис. 3.10, а) расщепляется на несколько эквивалентных состоя­ний, с каждым из которых связывается один выходной символ. Для нашего приме­ра это состояния рО, pi, qO, ql, rO, rl. Построение переходов эквивалентного авто­мата Мура ясно из рисунка.
а/О
Ь/0

Автоматы Мили и Мура
Рис. 3.10. Автомат Мили (а) и эквивалентный ему автомат Мура (б)

Примеры КА
Триггеры
Триггер является простейшим автоматом. Рассмотрим два типа триггеров: RS-f гер и счетный триггер. Состояние этих автоматов является их выходом, то есть автоматы Мура. В RS-триггере два входа: Reset и Set. Вход Reset сбрасывает, < устанавливает единичное состояние автомата. В счетном триггере единствен счетный вход переключает автомат из нулевого состояния в единичное и обра

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

Примеры КА
Структурная схема электронных часов казана на рис. 3.11. Управляющие кнопки обозначены здесь «а» и «Ь». Кроме устройства отображения, высвечивающего цифры, и схемы отображения, преобразующей двоично-десятичные коды цифр в семиразрядный код управления с диодами, на схеме показаны четыре регистра отображения, хранящие дво но-десятичные коды четырех цифр, которые в настоящий момент высвечивается на циферблате с помощью схемы и устройства отображения, комбинационные схемы «ИЛИ», пропускающие любой из разрешенных кодов на регистре отображения, шина «Управление», разрешающая в каждой ситуации выдач} регистры отображения сигналов только либо секундомера, либо часов, либо да На схеме также присутствуют регистры секундомера и генератор тиков, который выдает сигнал с частотой 1 Гц. На рисунке зафиксирован момент «19 июня, 15 сов, 04 минуты, 43 секунды».

Примеры КА
Устройство управления, организующее работу всех элементов электронных час построено на основе модели конечного автомата. Граф переходов этого автомата изображен на рис. 3.12. В начальном состоянии отображается время. Это значит что двоичный код этого состояния (после дешифрирования) открывает выход
41

Примеры КА
Примеры КА
четырех двоично-десятичных регистров, хранящих единицы и десятки шшут и единицы и десятки часов на входы четырех комбинационных схем «ИЛИ».
Рис. 3.11. Структурная схема электронных часов

Примеры КА
Рис. 3.12. Автомат устройства управления электронными часами
Конечный автомат реагирует на событие нажатия кнопки «а» на корпусе часов переходом в состояние «Установка минут», в котором событие нажатия кнопки