Продолжение функций и на слова
Пусть — алфавит.
Определение. Словом длины 
, 
, над алфавитом 
называется любая конечная последовательность длины 
элементов множества 
.
Для обозначения слов используют запись .
Слово, в котором нет ни одной буквы, называют пустым словом и обозначают символом .
Введем ряд обозначений:
— множество всех слов над алфавитом 
,
— множество всех слов длины 
;
— множество всех непустых слов.
Очевидно, выполнены равенства: 
; 
.
Определение. Произведением двух слов 
и 
называется слово 
.
Утверждение 1. Произведение двух слов ассоциативная операция, т.е. для любых трех слов 
выполняется равенство: 
.
Это утверждение относится к разряду очевидных.
Поскольку расстановка скобок в произведении не влияет на результат, то, записывая произведение нескольких слов, скобки опускают. Например, вместо 
пишут 
.
Заметим, что произведение слов зависит от порядка сомножителей, т.е. в общем случае .
Определение. Продолжением функций 
и 
на слова называются соответственно функции 
и 
, определенные индуктивно следующим образом:
;
;
;
;
;
.
Пример 2. Рассмотрим автомат 
, у которого 
, 
, 
, 
и функции 
и 
заданы таблицей.
;
.
Приведенный автомат
Определение. Состояния 
и 
автомата называются неотличимыми, если для 
. В противном случае состояния 
и 
называются отличимыми.
Введем на множестве состояний автомата бинарное отношение неотличимости ~:
.
Это отношение является отношением эквивалентности. Следовательно, оно порождает разбиение множества 
на классы эквивалентности. Следуя определению классов эквивалентности, класс эквивалентности произвольного элемента 
по отношению неотличимости ~ определим как множество 
. Множество классов эквивалентности по отношению неотличимости обозначим 
, для его элементов будем использовать обозначение 
.
Определение. Приведенным автоматом, соответствующим конечному автомату 
, называется автомат 
, функция переходов 
и функция выходов 
которого определены следующим образом:
; 
, где 
.
Докажем корректность этого определения, т.е. его независимость от выбора представителя 
в классе эквивалентности 
.
1. Чтобы доказать корректности определения функции 
, будем рассуждать от противного. Предположим, что найдутся такие 
и 
, что 
. Это означает, что состояния 
и 
отличимы, и, значит, 
, для которого 
. Но тогда 
. Следовательно, 
и 
отличимы, а это противоречит тому 
и 
принадлежат одному и тому же классу эквивалентности 
.
2. Докажем корректность определения функции 
. Возьмем 
и 
; 
и 
неотличимы, следовательно, 
. Таким образом, функция 
определена корректно.
Утверждение 2. Все состояния приведенного автомата попарно отличимы.
Доказательство. Будем рассуждать от противного. Пусть найдутся различные 
и 
такие, что 
. Тогда 
. Тогда согласно определению функции 
будем иметь 
, где 
, 
. Отсюда следует, что 
и, значит, по свойству классов эквивалентности 
. Получили противоречие. Следовательно, наше предположение о существовании различных неотличимых классов эквивалентности было неверным. ■
Замечания. 1. Автоматы 
и 
работают одинаково, т.е. если на вход этих автоматов подавать одну и ту же входную последовательность, то выходные последовательности автоматов будут одинаковыми.
Типы конечных автоматов
Автомат — система механизмов, устройств, в которой полностью автоматизированы процессы получения, преобразования, передачи энергии, материалов, информации Термин «автомат» используется в двух аспектах:
При математическом подходе под автоматом понимается математическая модель технического устройства, у которого должны быть входы, внутренние состояния и выходы. Относительно деталей структуры устройства сведений не должно быть.
При техническом подходе под автоматом понимается вполне реальное устройство, например, телефонный автомат, торговый автомат и т. д. В данном случае, естественно, известными являются детали внутреннего строения устройства.
Частным и важным случаем автомата выступает цифровой автомат (ЦА), в котором полностью автоматизированы процессы приема, преобразования, хранения и выдачи цифровой информации.
С точки зрения сигналов ЦА полезно определить как систему, которая может принимать входные сигналы, под их воздействием переходить из одного состояния в другое, сохранять его до прихода следующего входного сигнала, выдавать выходные сигналы.
ЦА считается конечным, если конечны множества входных сигналов X, состояний S и выходных сигналов Y. Конечный автомат можно поставить в соответствие такому устройству, как компьютер. Компьютер перерабатывает поступающие входные данные в выходные данные (результат), но этот результат соответствует не только входным данным, но и текущему состоянию компьютера, т.е. тем данным, которые хранятся в памяти компьютера, например, результаты предыдущих вычислений, программы вычислений.
Работа ЦА осуществляется в автоматном времени, определяемом числом периодов поступления входных сигналов.
Абстрактным автоматом называют математическую модель дискретного устройства, имеющего один входной канал, куда поступают последовательности символов какого-либо языка, один выходной канал, с которого снимают последовательности символов какого-либо другого языка и находящегося в каждый из моментов дискретного времени в каком-либо состоянии. Графически абстрактный автомат представлен рис.
Слова входного языка можно представить символами множества X=1,x2. xn>, который называют входным алфавитом, а слова выходного языка — символами множества Y=1,y2. yp>, который называют выходным алфавитом. Множество состояний автомата S=1,s2. sm> называют алфавитом состояний.
Понятие состояние автомата используется для описания систем, выходные сигналы которых зависят не только от входных сигналов в данный момент времени, но и от некоторой предыстории, т.е. сигналов, которые поступали на входы системы ранее. Следовательно, цифровые автоматы относятся к последовательностным схемам, которые, как уже отмечалось, обладают памятью. Понятие состояние автомата соответствует некоторой памяти о прошлом, поэтому ввод этого понятия позволяет устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входных сигналов.
Работу абстрактного автомата следует рассматривать применительно к конкретным интервалам времени, т.к. каждому интервалу дискретности t будет соответствовать свой выходной сигнал y(t). Следовательно, функционирование автомата рассматривается через дискретные интервалы времени конечной продолжительности. В абстрактной теории цифровых автоматов считается, что входные сигналы воздействуют на синхронный автомат в момент начала каждого i -того интервала (кванта) времени, выделенного соответствующим синхроимпульсом (тактом), а изменение внутренних состояний автомата происходит в интервалы времени между смежными синхроимпульсами, когда нет воздействия входных сигналов.
Понятие «состояние» используют для того, чтобы установить функциональную зависимость генерируемых автоматом символов и/или слов выходного языка от символов и/или слов входного языка при реализации автоматом заданного алгоритма. Для каждого состояния автомата sÎS и для каждого символа xÎX в момент дискретного времени [t] на выходе устройства генерируется символ yÎY. Эту зависимость определяет функция выходов автомата j. Для каждого текущего состояния автомата sÎS и для каждого символа xÎX в момент дискретного времени [t] автомат переходит в очередное состояние sÎS. Эту зависимость определяет функция переходов автомата y. Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата (s1[[1]s2[2]s3[3]. ) и последовательности выходных символов (y1[1]y2[2]y3[3]. ), которые для последовательности символов (x1[1]x2[2]x3[3]. ) разворачиваются в моменты дискретного времени t = 1,2,3. В прямоугольных скобках указывают моменты дискретного времени, которые называют иначе тактами, в круглых скобках — последовательности символов алфавитов X, Y и S.
Итак, математическая модель конечного автомата есть трехосновная алгебра, носителями которой являются три множества X, Y и S, а операциями — две функции j и y:
M = á X; Y; S; y; jñ, (1.1)
| где X=< x1;x2;. xn > | — | множество символов входного алфавита; |
| Y=< y1;y2;. yp > | — | множество символов выходного алфавита; |
| S=1;s2;. sm> | — | множество символов состояний автомата; |
| y: (SÄX) ® S | — | функция переходов автомата для отображения пары (s;x) текущего момента дискретного времени [t] в состояние s очередного момента дискретного времени [t+1]; |
| j: (SÄX) ® Y | — | функция выходов автомата для отображения пары (s;x) текущего момента дискретного времени [t] в символ y выходного канала этого же момента дискретного времени [t]. |
Так как области определения функций переходов и выходов совпадают, то обобщенный оператор поведения автомата можно представить так:
Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений:
Если на входе автомата имеем слово a = (x1x2x3. xn), то, считывая последовательно символы этого слова, на выходе автомата генерируется последовательность символов слова b по следующей схеме:
Так как на каждом i-ом такте к слову длины (i-1) приписывается справа очередной символ j(s[1];x1[1]x2[2]. xi[i]), то последовательность символов выходного слова можно записать так:
Если считывание символов входного слова a выполняется последовательно слева направо, то всегда найдется такая последовательность (x1x2. xn-1)=g, для которой
Поэтому если входное слово a = (gxn), то выходное слово b можно записать так:
Это означает, что последний символ слова b есть результат работы автомата, начавшего работу в состоянии s и считавшего последний символ слова a, но значение этого символа зависит от всей входной последовательности.
Длина выходного слова всегда равна длине входного слова.
Изменение состояний автомата для последовательности символов слова a = (x1x2x3. xn) может быть описано следующей схемой:
где s[1] — начальное состояние автомата.
Так как за один такт автомат считывает один символ входного слова, то в последовательности состояний автомата можно не указывать номер такта, то есть.
Если входное слово a = (gxn), то изменение состояния автомата может быть описано так:
Это означает, что s[n+1] есть последнее состояние автомата, начавшего работу в состоянии s и считавшего последний символ слова a в момент дискретного времени n.
Если функции переходов и выходов однозначно определены для каждой пары (s;x)Î(SÄX), то автомат называют детерминированным. В противном случае автомат называют недетерминированным или частично определенным.
Если функция переходов и/или функция выходов являются случайными, то автомат называют вероятностным.
Если у автомата задано начальное состояние s=s0ÎS, в котором он находится всегда до приема первого символа входного слова, то автомат называют инициальным. В этом случае модель автомата записывают так:
Последовательность символов в слове b и последовательность состояний автомата s однозначно определяются начальным состоянием автомата s=s0 и последовательностью символов во входном канале a. Поэтому отображение входного слова a на выходное слово b чаще называют автоматным отображением, то есть b = М(s0;a), а М – автоматным оператором.
Автоматное отображение обладает свойствами:
1) входное и выходное слова имеют одинаковую длину (свойство сохранения длины);
2) yi-ый символ выходного слова зависит от всей последовательности символов входного слова, до xi-го включительно; кроме того если a=a1a2, то b=b1b2..
Задание конечного автомата:
Для описания (задания) ЦА используются разнообразные средства, называемые языками, которые делятся на начальные и автоматные языки. Поскольку языки базируются на алфавитах, то применительно к ЦА множество Х трактуется в качестве входного алфавита, множество Y — выходного алфавита, а множество S — внутреннего алфавита. Как и для других объектов, для автоматов используются разные таблицы, матрицы, графы.
Наиболее общее при выработке выходных сигналов, формировании новых состояний под действием входных сигналов отражается законом функционирования автомата [4, 12]:
s(t)= d (s(t-1), x (t)),
y (t)= l (s(t-1), x (t)).
Как видно, закон функционирования представляет собой совокупность двух функций: функции перехода d и функции выхода l.
В формулах используются обозначения:
t — данное автоматное время, t-1 — предыдущее автоматное время, d — оператор формирования данного состояния s, l — оператор формирования данного выходного сигнала y, х — входной сигнал.
Видно, что данное состояние s(t) зависит от предыдущего состояния s(t-1) и входного сигнала в данный момент времени, что выходной сигнал в данный момент времени так же определяется предыдущим состоянием и входным сигналом в данный момент времени.
Автомат задан, если заданы:
1. Конечное множество входных сигналов, заданных с помощью входного алфавита X=1, x2,…, xm>
2. Конечное множество выходных сигналов, заданных с помощью выходного алфавита y=1, y2. yn>
3. Конечное множество состояний автомата заданного с помощью алфавита S=1,s2. sm>
4. Начальное состояние автомата
5. Функция выходов, определяющая зависимость выходного сигнала и состояния автомата y[kt]=fв(U[kt], a[kt]) где t – длительность такта k – номер такта. Конечный автомат существует в конечном (дискретном) времени.
6. Функция переходов
Функция выходов и функция переходов является характеристическими функциями.
Таким образом, в определении конечного автомата фигурирует три множества и две функции M=в, fп>
Функция перехода fп:X*S S Функция выхода fв:X*S Y
Операторы, описывающие работу автомата, обычно задают таблицей переходов и таблицей выходов.
В таблице переходов показывают в какое состояние попадает автомат от того или иного входного сигнала. В таблице выходов показывают какой выходной сигнал генерирует автомат в зависимости от типа входного сигнала и текущего состояния автомата.
К примеру, рассмотрим таблицы переходов и выходов некоторого автомата.
Таблица переходов автомата
| Входной сигнал | Состояние | |||
| a0 | a1 | a2 | a3 | |
| x1 | a1 | a2 | a3 | a3 |
| x2 | a0 | a0 | a0 | a0 |
Таблица выходов автомата
| Входной сигнал | Состояние | |||
| a0 | a1 | a2 | a3 | |
| x1 | y2 | y2 | y1 | y2 |
| x2 | y2 | y2 | y2 | y3 |
В клетку таблицы переходов, находящуюся на пересечении столбца с буквой аi и строки с буквой x j, записывается состояние автомата, в которое он переходит из состояния аi при подаче на вход сигнала x j. В аналогичную клетку таблицы выходов записывается выходной сигнал y i, который формируется автоматом при таком переходе.
Операторы переходов и выходов могут быть заданы одной таблицей, по которой однозначно определяются переходы и выходы автомата.
Таблица переходов и выходов автомата
| Выходной сигнал | Cостояние | |||
| a0 | a1 | a2 | a3 | |
| x1 | a1 y2 | a2 y2 | a3 y1 | a3 y2 |
| x2 | a0 y2 | a0 y2 | a0 y2 | a0 y3 |
Большую наглядность обеспечивает задание конечных автоматов с помощью графов или диаграмм состояний.
Граф автомата состоит из узлов, соединенных ветвями. Узлы (кружки на схеме графа) отождествляют внутренние состояния автомата. Каждая ветвь графа, т.е. ориентированная линия, стрелка которой указывает следующее состояние автомата, отмечается входным сигналом, вызывающим в автомате соответствующий данной ветви переход, и выходным сигналом, который возникает при этом переходе. Входной и соответствующий ему выходной сигналы разделяются на чертеже запятой или косой чертой. Если некоторый входной сигнал не меняет состояния автомата, то соответствующая ветвь замыкается на кружке (узле), из которого она выходит.
Поскольку таблица состояний и граф (диаграмма) состояний несут одну и ту же информацию, их можно преобразовать друг в друга. Каждое состояние представляется кружком, а каждый элемент таблицы преобразуется в отрезок ориентированной линии, соединяющей соответствующие кружки. Процедура обратного преобразования очевидна.
Типы конечных автоматов
1) по закону функционирования ЦА делятся на автоматы 1-го рода (автоматы Мили) и ЦА 2-го рода. Последние автоматы в случае, когда нет явной зависимости от входных сигналов x (t), являются автоматами Мура. Видимо, целесообразнее по первому критерию автоматы делить на автоматы Мили и Мура;
В автомате Мили функция выходов j определяет значение выходного символа по классической схеме абстрактного автомата. Математическая модель автомата Мили и схема рекуррентных соотношений не отличаются от математической модели и схемы рекуррентных соотношений абстрактного автомата, т.е.
Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y[t] обнаруживается только при наличии символа во входном канале x[t].
Рис. 1.3. Функциональная схема автомата Мили.
В автомате Мура функция j определяет значение выходного символа только по одному аргументу — состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе. Математическая модель и схема рекуррентных соотношений автомата Мура имеют вид:
Особенностью автомата Мура является то, что символ y[t] в выходном канале существует все время пока автомат находится в состоянии q[t].
Рис. 1.4. Функциональная схема автомата Мура.
2) по конечности множеств X, Y, и S автоматы бывают конечными и бесконечными. Может быть, данный критерий стоит трактовать как критерий по мощности ЦА;
3) по объему памяти автоматы делятся на автоматы с памятью (последовательностные автоматы) и автоматы без памяти (логические комбинационные схемы);
4) по степени раскрытия структуры автоматы бывают абстрактными автоматами (детали структуры не раскрыты) и структурными автоматами (раскрыты детали структуры);
5) по отношению между автоматами среди автоматов можно выделить подавтоматы, надавтоматы. Если, например, известно, что ЦАА < ЦАВ, то автомат А является подавтоматом автомата В, а автомат В - надавтоматом автомата А;
6) по полноте используемых переходов автоматы делятся на полностью определенные автоматы и частично определенные автоматы;
7) по стабильности периода следования входных сигналов автоматы бывают синхронными автоматами (период следования входных сигналов- постоянная величина) и асинхронными автоматами (период — переменная величина);
8) по вероятности переходов автоматы делятся на детерминированные (не вероятностные) и недетерминированные (вероятностные) автоматы;
9) при нулевой мощности множества внутренних состояний (| S |= 0) автомат называется автономным, при | Y | = 0 — автоматом без выхода. Если среди состояний автомата выделяется начальное состояние s0, то автомат называется инициальным;
10) по применению автоматы можно разделить на автоматы:
а) промышленные (сварочные, кузнечно-прессовые, литейные, строительные, транспортные, упаковочные роботы, контрольные, диагностические и др.);
б) сельскохозяйственные (доильные, раздаточные, уборочные и др.);
в) торговые (газетные, упаковывающие, взвешивающие и др.);
г) учебные (обучающие, тестирующие, моделирующие, демонстрирующие и др.);
д) медицинские (искусственные органы, хирургические, диагностирующие, дыхательные, тренирующие и др.);
е) информационные (видеомагнитофоны, системы «вопрос — ответ» и др.).
Объединение автоматов Мили и Мура представляет С-автомат, для которого схема рекуррентных соотношений имеет вид:
Рис.1. 5. Функциональная схема С-автомата.
Интересно выделить особые классы автоматов, математические модели которых опираются только на два носителя алгебры.
Пусть X=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:
Функциональная схема автомата приведена на рис.1.6.
Рис.1.6. Функциональная схема порождающего автомата.
Особенностью функционирования такого автомата является генерация последовательности символов выходного слова только в зависимости от последовательности состояний автомата. Такие автоматы называют порождающими или автономными. С помощью такого автомата генерируется последовательность управляющих команд на какие-либо объекты внешней среды.
Пусть Y=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:
Функциональная схема автомата приведена на рис.1.7.
Рис. 1.7. Функциональная схема распознающего автомата.
Особенностью функционирования такого автомата является распознавание в последовательности изменений аргумента функции переходов значения (qi[t];xi[t]) и перевод автомата в заключительное состояние qk. С помощью такого автомата обнаруживают заданные возмущения со стороны объектов внешней среды или распознают заданную последовательность входных символов. Поэтому такие автоматы называют распознающими. Часто и автомат Мура представляют автоматом без выхода, так как его выходной сигнал эквивалентен состоянию автомата.
Пусть Q=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:
Функциональная схема автомата приведена на рис.8.
Рис. 1.8. Функциональная схема комбинационного автомата.
Особенностью функционирования такого автомата является отсутствие «памяти», т.е. на каждый символ входного алфавита автомат генерирует символ выходного алфавита без учета состояния автомата. Такие автоматы чаще всего называют комбинационными автоматами.
Автоматы, выполняющие роль «0» и
«1» в алгебре автоматов. С — автомат
Любая алгебра должна иметь конструкции, выполняющие в ней роль «0» и «1». По аналогии с алгеброй алгоритмов роль «0» выполняет пустой автомат (ноль-автомат), ЦА0. Пустой автомат – это автомат, в котором запрещены всевозможные переходы. Естественно, что ЦАА \/ ЦА0 = ЦАА, ЦАА /\ ЦА0 = ЦА0.
Роль «1» возлагается на полный ЦА (ЦА1), в простейшем случае такой автомат представляет собой настраиваемое объединение рассматриваемых автоматов. Естественно, что ЦАА \/ ЦА1 = ЦА1, ЦАА /\ ЦА1 = ЦАА, дополнение ЦА1 = ЦА0, дополнение ЦА0 = ЦА1.
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
§12.4 Элементы теории конечных автоматов
Определение Конечным автоматом Мили называется множество из пяти объектов , в котором:
— конечное непустое множество (пространство) состояний,
— конечное непустое множество входных сигналов (входной
алфавит),
— конечное непустое множество выходных сигналов (выходной
алфавит),
— функция переходов,
— функция выходов.
ЗАМЕЧАНИЕ Автоматы могут задаваться:
1) в виде взвешенного орграфа (диаграмма состояний автомата)
или в виде блок-схемы программы, реализующей поведение
2) таблично (функции переходов и выходов задаются в виде таблиц
или совмещенной таблицы состояний).
ЗАМЕЧАНИЕ При графическом изображении автомата состоя
ния обозначают вершинами, а переходы — дугами с направлениями,
определяемыми функцией переходов. При этом над дугой указыва
ются соответствующие значения входа и выхода (взвешенная дуга)
Рассмотрим специальный класс автоматов.
Определение Пусть. Тогда
функции перехода и выхода являются функциональными преобразователями. Обозначим их
,
,
и реализуем в виде логических схем (ЛС) с 
входами и соответст венно 
выходами (рис.2.17). Составим из них ЛС, соединив выходы левого блока с соответствующими входами правого и левого
блоков. входов сделаем общими для обоих блоков. Полученная ЛС (рис.2.18) всегда находится в определенном состоянии, пока на нее не действуют входные сигналы. Ввиду того, что один и тот же сигнал может вызвать разные выходные сигналы, эта ЛС не будет комбинаци онной. Она называется последовательностной схемой или цифровым автоматом.
ЗАМЕЧАНИЕ Цифровой автомат задается еще и:
3) аналитически ( задаются в виде функциональных преобразова
4) в виде логической схемы.
Произвольный автомат можно реализовать как составную часть
цифрового автомата. Для построения последнего нам понадобятся
Определение Пусть 
— конечное множество и 
. Тогда
инъективное отображение называется кодировщиком
множества 
, а сюръективное 
— декодировщиком множества 
.
ЗАМЕЧАНИЕ Пусть — отображение конечного
множества 
в конечное множество 
и 
.
Тогда это отображение можно представить в виде композиции
, где 
— кодировщик, 
—
функциональный преобразователь и — декодировщик.
Область определения и область значений функционального
преобразователя по числу элементов, вообще говоря, больше
соответственно областей 
для отображения 
.
Определение Обозначим алфавит, то есть конечное множе
ство элементов (букв), — множество всевозможных конечных
цепочек букв (слов) вида . Количество букв в слове называет
ся его длиной и обозначается 
. Операция составления двух слов в одно 
называется склеиванием (сцеплением, конкатена цией) этих слов. Если 
есть пустая цепочка, то 
.
Пример .
ЗАМЕЧАНИЕ Множество представляет собой полугруппу
относительно операции склеивания, так как последняя обладает
свойством ассоциативности: .
Понятие склеивания позволяет расширить действие автомата с множества букв 
на множество слов 
.
Определение Расширенными функциями переходов и выходов автомата 
называются отображения 
, определяемые рекуррентными формулами:
.
Следующее замечание дает развернутый алгоритм вычисления значений (представления) расширенных функций на слове.
ЗАМЕЧАНИЕ (свойства расширенных функций)
1) .
2)
Определение Реакцией состояния 
автомата Мили называ ется вход-выходное отображение 
, определяемое по правилу 
. Реакцией автомата называется совокупность реакций всех состояний этого автомата.
ЗАМЕЧАНИЕ Реакция состояния совпадает с сужением
расширенной функции выходов 
на множество 
.
Обратно, совокупность реакций всех состояний определяет
расширенную функцию выходов.
Определение Состояния 
автомата 
называются эквива
лентными, если их реакции совпадают:
, то есть 
.
Определение Состояния 
автомата 
называются 
эквива лентными, если их реакции совпадают на словах длины 
:
.
Обозначение 
или, что все равно, 
ТЕОРЕМА 12.6 1) Множество состояний разбивается на
максимальные классы эквивалентных состояний. Совокупность
таких классов обозначается .
2) .
3) Если 
, то 
.
4) (теорема Хаффмана-Мили) . То есть, если
реакции 
совпадают на словах длины 
, то
состояния эквивалентны
Понятие эквивалентных состояний очевидным образом обобщает
ся на состояния из разных автоматов, у которых одинаковы соответст
венно входные и выходные алфавиты. Это позволяет дать такое
Определение Два автомата с одинаковыми входными и выход ными алфавитами называются эквивалентными автоматами, если каждое состояние одного из них эквивалентно некоторому состоянию другого автомата, и наоборот.
Определение Автомат называется приведенным (минимальным или сокращенным), если все его состояния попарно не эквивалентны.
СЛЕДСТВИЕ Согласно теореме Хаффмана-Мили, начиная с
разбиения 
пространства 
все состояния, попавшие в один
класс, имеют одинаковые реакции. Если отождествить все
состояния, попавшие в один класс, то получаем новый автомат,
который является приведенным по построению. Он эквивалентен
исходному автомату, что следует из определения.
АЛГОРИТМ (построения приведенного эквивалентного
автомата). 1) По таблице выходов строим разбиение .
2) По таблице переходов последовательно строим разбиения ,
используя пункт 2) теоремы. В силу пункта 4) таких шагов будет не
более .
3) В силу пункта 3) первое разбиение, для которого ,
определяет классы эквивалентных состояний.
Определение Автомат Мили называется частичным, если функции перехода или выхода определены не всюду. В этом случае в таблице состояний автомата ставят прочерки.
Для формулировки алгоритма построения минимального конечного автомата «покрывающего» произвольный частичный автомат, нам понадобится ряд понятий.
Определение Слово 
называется применимым к состоянию 
, если функция перехода 
может оказаться неопределенной лишь после считывания последней буквы этого
Определение Дополним алфавиты 
неопределенным симво лом «-». Слово 
покрывает слово 
той же длины, если 
получается из 
заменой некоторых букв 
на прочерк. 
называются совместимыми словами, если существует слово 
, покрывающее и 
и 
.
Определение Состояния 
частичного автомата 
называются совместимыми, если для любого применимого к ним слова 
выходные слова совместимы.
АЛГОРИТМ (построения всех попарно совместимых состояний)
1) Всевозможные пары состояний изображают в виде клеток. Клетку вычеркивают, если хотя бы для одной буквы 
. В невычеркнутую клетку 
вписывают все те пара определенных состояний, в которые может перейти 
.
2) Во множестве полученных таким образом невычеркнутых клеток вычеркивают те, в которые вписаны вычеркнутые на первом шаге пары.
3) Шаг 2) повторяется до тех пор, пока будет что вычеркивать. Полученное множество невычеркнутых клеток дает все пары совместимых состояний автомата.
Этот алгоритм имеет наглядный вид при .
Определение Множество попарно совместимых состояний
частичного автомата называется группой совместимости.
Определение Конечное число групп совместимости автомата называется группировкой, если любое состояние автомата попадает хотя бы в одну из этих групп.
Определение Группировка называется замкнутой, если для любой группы совместимости 
, 
либо хотя бы одно из значений 
не определено, либо 
принадлежат одной группе совместимости этой группировки.
Пусть автоматы 
, 
имеют одинаковые входные и выходные алфавиты.
Определение Состояние 
автомата 
покрывает состояние 
автомата 
, если любое слово, применимое к состоянию 
, будет так же применимо к состоянию 
, а слово 
покрывает слово 
.
Определение Автомат 
покрывает автомат 
, если каждое состояние последнего покрывается некоторым состоянием автомата 
.
АЛГОРИТМ (построения покрывающего автомата)
1) Определяют все пары совместимых состояний.
2) Выписывают все состояния автомата в порядке возрастания
индексов. В этой последовательности вычеркивают все состояния,
несовместимые с первым. Затем вычеркивают все состояния,
несовместимые с первым невычеркнутым. И так далее.
Невычеркнутые состояния составляют первую группу совмести
Составляют последовательность вычеркнутых состояний. Проде
лывая с ней то же самое, получают вторую группу совместимости.
Получение групп совместимости продолжают, пока есть что
вычеркивать. В результате получается группировка.
3) Если группировка не замкнута, то строят на ее основе замкнутую,
работая с таблицей переходов и оставаясь во множестве пар совме
стимых состояний. При этом либо расширяют группы, совместимо
сти, либо добавляют новые.
4) Группы совместимости полученной замкнутой группировки соста
вляют множество состояний искомого покрывающего автомата. Его
строят, руководствуясь таблицей исходного частичного автомата.
Определение Приведенный автомат Мили называется автоматом с конечной памятью, если существуют такие число 
и отображение 
, что
имеет место равенство 
. Наименьшее число 
с
таким свойством называется памятью автомата.
ЗАМЕЧАНИЕ Если есть автомат с конечной памятью, то
будет
.
То есть функционирование автомата вполне определяется знанием предыдущих входных букв и откликов на них.
ТЕОРЕМА 12.7 1) (Гилл) Если есть автомат с конечной
памятью, 
, то 
.
2) Автомат имеет конечную память тогда и только тогда, когда для
некоторого не существует двух равных вход-выходных путей
длины 
, оканчивающихся в разных состояниях:
.
Из теоремы следует такой
АЛГОРИТМ (вычисления памяти автомата)
Составим матрицу перехода 
автомата. 
1) 
. Вычисляем 
, а по ней составляем множества вход-
выходных путей длины 
: 
.
2) Если 
, то полагаем память 
. В противном
случае переходим к 3).
3) Если 
, то переходим к 1) и полагаем 
. В случае
по теореме Гилла память автомата бесконечна.
Рассмотрим одну разновидность автоматов Мили.
Определение Автомат Мили 
, у которого функция выходов задается в виде 
, где 
— отображение (называемое определяющим), называется автоматом Мура. То есть функция выходов автомата Мура определяется только состоянием автомата, но не 
, как у автомата Мили, а состоянием 
, в которое он переходит при подаче буквы 
.
Обозначение .
Определение Реакцией состояния 
автомата Мура называется отображение 
, определяемое по правилу
ЗАМЕЧАНИЕ Каждый автомат Мили порождает эквивалентный ему автомат Мура с числом состояний по правилу:
каждое состояние исходного автомата заменяется на несколько
состояний в количестве, равном числу различных значений
функции выходов при переходе автомат в это состояние.
Определение Автомат 
всегда находится в определенном состоянии 
. Это состояние называется начальным, а пара 
— инициальным автоматом.
ЗАМЕЧАНИЕ Каждый автомат 
порождает 
Пример (сумматор последовательного действия) Для этого иници ального автомата 
, 
. На его вход последовательно подаются пары цифр, стоящие в одном разряде слагаемых чисел, начиная с младшего разряда. Значение состояния автомата интерпретируется как «то, что он держит в уме», когда на вход подается пара очередного разряда. При этом функция переходов определяет число, которое автомат будет «держать в уме» в результате сложения цифр этой пары, а функция выходов определяет число, которое он запишет в текущий разряд искомой суммы. Поэтому таблицы функций переходов и выходов
:
:
§3.4. Приведённый автомат
неотличимыми , если ψ ( q , w ) = ψ ( q ′ , w ) для всех w A + .
Состояния q и q ′ отличимы , если ψ ( q , w ) ≠ ψ ( q ′ , w ) при
некотором w A + . Положим q ~ q ′ , если q и q ′ неотличичимы. Нетрудно видеть, что отношение неотличимости ~ на множестве Q состояний автомата V является отношением эквивалентности. Это отношение вызывает разбиение множества Q на непересекающиеся классы эквивалентности: Q = Q 1 Q 2 . Q k . При этом любые
два состояния q , q ′ , лежащие в одном классе, неотличимы, а любые два состояния из разных классов отличимы.
Множество классов отношения ~ (фактор-множество Q / ~) обозначим
через Q . Построим новый автомат V . В качестве входного и
выходного алфавитов автомата V возьмём те же множества
которые были у автомата V , а в качестве множества состояний возьмём
Надо определить теперь функции ϕ €: Q × A
a A . Наиболее естественным является следующее
определение значения ϕ €( q €, a ) : взять какой-нибудь элемент q , принадлежащий классу q €, найти ϕ ( q , a ), а затем класс, в котором лежит элемент ϕ ( q , a ), объявить значением ϕ €( q €, a ). То есть считать, что
Докажем корректность этого определения, т.е. независимость от выбора представителя в классе эквивалентности. Пусть Определение будет некорректным, если окажется, что
Докажем, что определение корректно. Если
( q , a ), то ψ ( ϕ ( q , a ), w ) ≠ ψ ( ϕ ( q , a ), w ) при
. Это означает, что ψ ( q , aw )
Следовательно, q ~ / q ′ , что противоречит условию. Итак,
( q , a ) ~ ϕ ( q , a ), поэтому определение (1) корректно.
определим на Q по формуле
ψ €( q €, a ) = ψ ( q , a ).
По определению неотличимости состояний мы имеем
ψ ( q , a ) ~ ψ ( q , a ), поэтому определение (2) корректно.
Автомат V = ( A , Q , B , ϕ €, ψ €) называется приведённым автоматом ,
соответствующим автомату V = ( A , Q , B , ϕ , ψ ).
Докажем, что у приведённого автомата все состояния отличимы
друг от друга . Пусть q € ~ q ′ . Тогда
( q ′ , w ) для всех
. Отсюда по формуле (2) получаем, что ψ ( q , w ) = ψ ( q , w )
. Следовательно, q ~ q . Отсюда следует, что
Итак, у автомата V
неотличимыми являются только
совпадающие друг с другом состояния.
Автомат V = ( A , Q , B , ϕ , ψ ) и приведённый автомат
( A , Q , B , ϕ €, ψ €) работают одинаково: для любой входной
последовательности a (1) a (2) a (3) . последовательность
b (1) b (2) b (3) . на выходе автомата V и автомата V одна и та же:
b (1) = ψ ( q , a (1)) = ψ €( q €, a (1)),
b (2) = ψ ( q , a (1) a (2)) = ψ €( q €, a (1) a (2)) и т.д. (здесь q − начальное
Пример 1. Построить приведённый автомат для автомата, заданного следующей диаграммой Мура, изображенной на рис. 3.14.
Решение . Вычислим: ψ ( q 1 ,0) = 1, ψ ( q 2 ,0) = 1, ψ ( q 3 ,0) = 0,
ψ ( q 4 ,0) = 1, ψ ( q 5 ,0) = 1. Следовательно, состояние q 3 отличимо
q 1 
от всех остальных. Мы
получаем (пока) следующее
классы, т.е. непересекающиеся
(далее это разбиение будет
ψ ( q 1 ,1) = 1, ψ ( q 2 ,1) = 0,
ψ ( q 4 ,1) = 1, ψ ( q 5 ,1) = 0. Отсюда следует, что q 1 не может лежать в одном классе с q 2 или q 5 , q 2 с q 1 или q 4 и т.д. Разбиение,
полученное ранее, измельчается до следующего:
K 2 = < q 1 , q 4 >, K 3 = < q 2 , q 5 >. Покажем, что это окончательное разбиение. Имеем: ϕ ( q 1 ,0) = q 3 , ϕ ( q 4 ,0) = q 3 , поэтому
ϕ ( K 2 ,0) K 1 . Аналогично получаем ϕ ( K 2 ,1) K 2 и т.д., т.е. функция ϕ “не разбивает” классы. Следовательно, классы K 1 , K 2 , K 3
можно считать состояниями нового автомата. Это и есть приведённый автомат, его диаграмма Мура изображена на рисунке 3.15.
Пример 2. Построить приведённый автомат для автомата V , заданного следующей таблицей 3.6:
Решение . Верхняя строка таблицы 11011 определяет разбиение
σ : Q = < q 3 >< q 1 , q 2 , q 4 , q 5 >, нижняя строка − разбиение
τ : Q = < q 1 , q 3 >< q 2 , q 4 , q 5 >. Их пересечение σ ∩ τ − это разбиение
Q = < q 1 > < q 3 >< q 2 , q 4 , q 5 >. Докажем, что состояния q 2 , q 4 , q 5 неотличимы друг от друга. В столбцах таблицы, соответствующих этим
состояниям, мы имеем: 1 , 1 , 1 , значит, функция ψ на
состояниях q 2 , q 4 , q 5 принимает одинаковые значения. Кроме того,
другая часть столбцов:
в одном классе разбиения. Это доказывает, что q 2 , q 4 , q 5
Из таблицы автомата V теперь нетрудно получить таблицу
приведённого автомата € − для этого
достаточно взять по одному представителю в каждом классе разбиения σ ∩ τ . Таким образом, мы получаем таблицу 3.7:
Задачи для самостоятельного
3. Автомат V задан диаграммой Мура. Построить диаграмму Мура
приведённого автомата V
2) Автомат V задан таблицей. Построить таблицу приведённого
§3.5. Периодичность выходной последовательности конечного автомата
Мы докажем, что любой конечный автомат перерабатывает периодическую входную последовательность в периодическую выходную, период которой не превышает n τ , где τ − период входной
последовательности, а n = | Q | − количество состояний автомата.
Доказательство будет основываться на следующем (легко доказываемом) замечании: если входная последовательность имеет
период τ 1 , а последовательность состояний автомата – период τ 2 , то
выходная последовательность будет иметь период НОК ( τ 1 , τ 2 ), где
НОК обозначает наименьшее общее кратное.
В теореме этого раздела и во многих других вопросах теории автоматов будет удобно использовать сокращённые обозначения для функций ϕ
и ϕ . А именно, пусть V = ( A , Q , B , ϕ , ψ ) − автомат, q Q , a A и w A . Если q ′ = ϕ ( q , a ), то этот факт мы будем записывать просто: q ′ = qa . Аналогично этому вместо записи q ′′ = ϕ ( q , w ) будем использовать сокращённую запись q ′′ = qw .
Теорема. Если входная последовательность конечного автомата является периодической, то выходная последовательность также периодическая.
Доказательство . Пусть V = ( A , Q , B , ϕ , ψ ) − конечный автомат.
Предположим, что на вход автомата поступает периодическая последовательность a (1) a (2) a (3). Если τ − её период, то
a ( t + τ ) = a ( t ) при t ≥ t 0 , где t 0 − момент времени, с которого начинается период. Введём в рассмотрение следующие слова:
w = a (1) a (2) . a ( t 0 − 1) −
предпериод входной последовательности и
u = a ( t 0 ) a ( t 0 + 1) . a ( t 0 + τ − 1) −
период . Пусть q 0 − начальное состояние автомата. Положим q = q 0 w .
Рассмотрим последовательность состояний q , qu , qu 2 , . qu n . Так как число членов этой последовательности равно n + 1 > | Q |, то среди них есть совпадающие, т.е. существуют различные i , j ≤ n такие, что
qu i = qu j . Можно считать, что j > i . Тогда j = i + m , где m > 0 и