В.А. Кутыркин, А.Ю. Бушуев Элементы теории автоматов и формальных языков. (В.А. Кутыркин, А.Ю. - Бушуев Элементы теории автоматов и формальных языков. 2014), страница 5

Такие способы задания и рассматриваются в настоящем разделе насоответствующих наглядных примерах.Пример 4.1 (табличный способ задания конечного автомата Мили). Рассмотрим конечныйавтомат МилиB( A, B,V , , ) , где Vv1, v2– словарь его состояний, Aa, b, c и0,1 – алфавиты его входа и выхода, соответственно. Его функции перехода посостояниям:A VV и выхода:A VB имеют вид:(a, v1 ) v2 , (b, v1 ) v1, (c, v1 ) v2 , (a, v2 ) v1, (b, v2 ) v2 , (c, v2 ) v1;(a, v1 ) 1, (b, v1 ) 1, (c, v1 ) 1, (a, v2 ) 0, (b, v2 ) 0, (c, v2 ) 0.Работа такого автомата Мили( A, B,V , , ) определяется таблицей:Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю.

Бушуев25abcv1v2 ,1v1, 1v2 , 0v2v1, 0v2 ,0v1,1Такая таблица удобна для её использования в компьютерной программе.►Пример 4.2 (графический способ представление автомата его диаграммой).Работа автомата Мили( A, B,V , , ) из примера 4.1 наглядно представляется в видеего диаграммы, показанной на рис. 10. Из этой диаграммы видно, что она являетсядиаграммой мульти-орграфа, который можно задавать с помощью набора матрицсмежности, индуцирующих соответствующий набор его бинарных отношений.►Рис.10Пример4.3.На( A, B,V , , ) ,A0 0 11, , , , B0 1 01Рис.11рис. 11представленареализующегодиаграммадвоичныйсумматор,состояния01011010101011вход.►01100автоматавМиликотором:> .

Протокол работы этого автомата на входное слово0,1 , V=<O,010 1101имеет вид:011 01011конечного0выходОглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев264.2. Минимизация конечного автомата Мили по состояниямВсилуопределения4.1,каждоесостояние( A, B,V , , ) ( A, B,V , , ) индуцирует отображениеv ( x)Такоеv:AавтоматаМилиB , для которого:x v , если x A .( x, v )отображениеv Vv(4)B называется:Aиндуцированным состоянием v V автоматаавтоматнымотображением,.Определение 4.2 (автоматно-эквивалентных состояний, приведённого автомата).

Пусть( A, B,W , , ) ( A, B,W , , ) – ещё один автомат Мили с той же сигнатуройалгебраических операций, что и автомат Милиситуация, когда. Как и для автомата. Для этого автомата не исключается и, для автомата, его состояния w W ибуквы a A используются обозначения:( a, w) a w;(5)( a, w) a w.Если состояния v V и w W автоматовv:ABиw:ABисовпадают, т.е.таковы, что автоматные отображенияvw,то состояния v V и w Wназываются автоматно-эквивалентными состояниями и используется обозначение:v ~ a w .

Если в автоматедля каждого его состояния нет других состояний, емуавтоматно-эквивалентных, то автоматЛемма 4.1. В автоматеназывается приведённым автоматом.►отношение автоматной эквивалентности на совокупности егосостояний является бинарным отношением эквивалентности, разбивающее совокупность егосостояний на непересекающиеся классы автоматно-эквивалентных состояний.►Замечание 4.1 (об автоматной эквивалентности). Минимизировать автоматсостояниямэтозначитсоздатьтакойприведенный( A, B,W , , ) ( A, B,W , , ) , что для каждого состояния автоматапоавтоматв автоматеесть автоматно-эквивалентное ему состояние и, наоборот.

Следовательно, такойприведённый автоматт.е.w:w Wимеет тот же набор автоматных отображений, что и автоматv:v V ,новавтоматесостояний.►Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуевнет,автоматно-эквивалентных27Лемма 4.2 (о конгруэнтности автоматной эквивалентности). Если состояния v1 , v2 Vавтоматно-эквивалентны, т.е.

v1 ~ a v2 , то для любой любого слова xавтоматасостояния( x, v1 )x v1и( x, v2 )такжеx v2автоматно-эвивалентны,Aт.е.x v1 ~ a x v2 .►Замечание 4.2. Согласно лемме 4.2 при любом входе автоматно-эквивалентные состоянияавтоматапереходят в автоматно-эквивалентные. Следовательно, можно корректноопределить автоматW( A, B,W , , ) ( A, B,W , , ) , котором совокупность состоянийV ~a состоит из классов автоматной эквивалентности состояний автоматаимеют для входной буквы aи функциииA и состояния v a W V ~a ( v a – класс автоматнойэквивалентности с представителем v V ) принимают значения:( a, v a )a( a, v )Такой автоматобозначение:a vaa vw, где wa(a, v);(a, v).( A, B,W , , ) ( A, B,W , , ) будет приведенным,для него используется~a и он называется фактор-автоматом для автоматаавтоматной эквивалентности состояний автоматаотносительно.

Очевидно, что такой фактор-автомат~a является приведённым и, кроме того, этот автомат можно рассматривать в качествепо состояниям.►результата решения задачи минимизации автомата4.3 Алгоритм минимизации конечного автомата Мили по состояниямДля конечного автомата( A, B,V , , ) ( A, B,V , , ) алгоритм его минимизацииформулируется следующим образом.Первый шаг. На совокупности состояний V вводим автоматаэквивалентности ~ e , полагая, что (v1 ~e v2индуцирует разбиение( 1,...,( aAa v1отношениеa v2 )) .

Это отношениесовокупности состояний V на классы ~ e -эквивалентности вида:k( )) .Второй шаг. Для компонентыj, гдеэквивалентности ~ , полагая, что состояния v1 , v2Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуевj 1, k ( ) , вводим отношениеj~ -эквивалентны только в том28случае, когда для любой буквы aодной компоненте разбиения, зависящей только от буквы( j)индуцируется разбиениеA состояния a v1 и a v2 принадлежат некоторойкомпонентырезультате образуется разбиениеТретий шаг.

Если:((1),...,aна классы ~ -эквивалентности. Вj( k ( ))) совокупности V ., то присваиваем разбиениюзначение разбиения) и переходим ко второму шагу алгоритма. Еслиразбиениюзначение разбиенияA . Тем самым(, то присваиваем) и переходим к четвёртому шагу( :алгоритма.~aЧетвёртый шаг. Создаём автоматсостояния vj( a, v a )a va( a, v a )a vaиз компонентыw, где wj( A, B, , , ) ( A, B, , , ) , где для:(a, v);(a, v).Пятый шаг. Выходим из алгоритма с результатом в виде приведённого автомата~a .Замечание4.3.Посколькуавтоматконечен,описанныйвышеалгоритмрезультативен.►Пример 4.4. Конечный автомат Мили( A, B, C , A, B, C , 1, 2,3, 4,5,6,7,8 , , ) задантаблицей 1.

В этом автомате входной и выходной алфавиты совпадают и имеют вид:A, B, C . Кроме того, V1, 2,3, 4,5, 6, 7,8 – словарь его состояний.Таблица 1A1234567833163541BBBABBAAA45215263CCCBCCBBB76578122Далее для минимизации рассматриваемого автоматауказанный выше алгоритм минимизации.Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. БушуевAACAACCCпо состояниям применяется29Первый шаг.

Отношение эквивалентности ~ e индуцирует разбиениесовокупность состояний V11, 2, 4,5 и2( 1,2)на классы ~ e -эквивалентности1, 2,3, 4,5, 6, 7,8 автомата3, 6, 7,8 , в каждом из которых буква выхода автомата определяетсявходной буквой, не зависящей от состояния автомата из рассматриваемого классаэквивалентности. Таблица 2 иллюстрирует полученное разбиение( 1,2) .Таблица 2A1245367833631541BBBBBAAAA45152263CCCCCBBBB76785122AAAACCCC12Второй шаг. Отношение эквивалентности ~ индуцирует разбиения(2)(2,3)на каждом из классовв каждом из классов11, 2, 4,5 ,1, 2, 4,5 и13, 622и3(1)1)7,8буква входа автомата1,зависящего только от этой входной буквы.

Таблица 4 иллюстрирует эти переходы.Таблица 3ABC12122212421252123111611171218121Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуеви3, 6, 7,8 , соответственно, гдепереводит состояние автомата из этого класса в состояние одного из этих классов2,(ПП1П2П3или30Таким образом, на втором шаге алгоритмы индуцируется разбиениесовокупности состояний V1, 2,3, 4,5, 6, 7,8 автоматаТретий шаг. Посколькузначение разбиения1,122Второй(1)(1,(ишаг.2),(2)3) .2,(3)эквивалентности(4)где2 ,11разбиения1, 2, 4,5 ,23, 6 и1, 4,5 ,33, 6 и2буква входа автомата переводит состояние автомата из этого класса в7,842, 3) ,( 1,индуцирует~на каждом классов7,8 , соответственно, где в каждом из классов23)и повторяем второй шаг алгоритма.и3)2,.Следовательно, полагаем, чтоОтношение(1,, то, согласно алгоритму, присваиваем символу1,3,3(состояние одного из этих классов2 или1,3,зависящего только от этой входнойбуквы.

Таблица 4 иллюстрирует эти переходы.Таблица 4.А21453678Такимобразом,(2,2,3,на4)В212213213213111111121121этомвторомТретий шаг. Посколькугде1,12(2,шагесовокупности состояний Vзначение разбиения3С1,П2П3П4алгоритмыиндуцируется1, 2,3, 4,5, 6, 7,8 автоматаразбиение., то, согласно алгоритму, присваиваем символу2,3ПП1и3,4) .4,4Следовательно, полагаем, что( 1,и повторяем второй шаг алгоритма.Второй шаг. Отношение эквивалентности ~ индуцирует разбиения(2)(2) ,(3)(3)и(4)(4)2 , 3, 4 ) ,на каждом классовОглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю.

Бушуев12 ,21, 4,5 ,(1)3(1) ,3, 631и7,8 , соответственно, где в каждом из классов4и7,842 ,121, 4,5 ,3, 63буква входа автомата переводит состояние автомата из этого класса всостояние одного из этих классов1,3 или2,4,зависящего только от этой входнойбуквы. Таблица 5 иллюстрирует эти переходы.Таблица 5.А21453678Таким(образом,1,2,3,2С323324324324212212231231этомвторомсовокупности4)Поскольку(наВшагеПП1П2П3П4алгоритмысостоянийиндуцируется1, 2,3, 4,5, 6, 7,8 автоматаV, то, согласно алгоритму, присваиваем символу2,2,2,34) ,3,3иследовательно, полагаем, что44,j( 1,.значение разбиения2 , 3, 4 ) ,где11,и переходим к четвёртому шагу алгоритма.~aЧетвёртый шаг. Создаём автоматсостояния vразбиение( j 1, 4 ) из компоненты:j( a, v a )a va( a, v a )a va( A, B, , , ) ( A, B, , , ) , где дляw, где w(a, v);(a, v).Пятый шаг.

Выходим из алгоритма с результатом в виде приведённого автомата~a , работу которого иллюстрирует Таблица 6.Таблица 6A13233242BBBAA2213Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. БушуевCCCBB3421AACC32Согласно таблицам 1 и 6, иллюстрирующим работу автоматов~a настоящегоипримера, соответственно, на входное слово AABCCABBC эти автоматы, начиная сначальных состояний 1 V и(122и 1, 4,5 ~a2), отвечают одинаковым выходнымсловом BACACBBCA . Аналогично подтверждается автоматная эквивалентность и другихсостояний автоматови~a ( 2 ~ a1,3, 6 ~ a3и 7,8 ~a4 ).►5. Дискретные преобразователиК одним из простейших конечных детерминированных автоматов относятся дискретныепреобразователи, т.е.