Элементы теории конечных автоматов

относительно операции склеивания, так как последняя обладает

свойством ассоциативности: .

Понятие склеивания позволяет расширить действие автомата с множества букв на множество слов .

Определение Расширенными функциями переходов и выходов автомата называются отображения , определяемые рекуррентными формулами:

.

Следующее замечание дает развернутый алгоритм вычисления значений (представления) расширенных функций на слове.

ЗАМЕЧАНИЕ (свойства расширенных функций)

1) .

2)

Определение Реакцией состояния автомата Мили называ ется вход-выходное отображение , определяемое по правилу . Реакцией автомата называется совокупность реакций всех состояний этого автомата.

ЗАМЕЧАНИЕ Реакция состояния совпадает с сужением

расширенной функции выходов на множество .

Обратно, совокупность реакций всех состояний определяет

расширенную функцию выходов.

­­­­­_____

Определение Состояния автомата называются эквива

лентными, если их реакции совпадают: , то есть .

Определение Состояния автомата называются эквива лентными, если их реакции совпадают на словах длины :

.

Обозначение или, что все равно,

ТЕОРЕМА 12.6 1) Множество состояний разбивается на

максимальные классы эквивалентных состояний. Совокупность

таких классов обозначается .

2) .

3) Если , то .

4) (теорема Хаффмана-Мили) . То есть, если

реакции совпадают на словах длины , то

состояния эквивалентны

Понятие эквивалентных состояний очевидным образом обобщает

ся на состояния из разных автоматов, у которых одинаковы соответст

венно входные и выходные алфавиты. Это позволяет дать такое

Определение Два автомата с одинаковыми входными и выход ными алфавитами называются эквивалентными автоматами, если каждое состояние одного из них эквивалентно некоторому состоянию другого автомата, и наоборот.

Определение Автомат называется приведенным (минимальным или сокращенным), если все его состояния попарно не эквивалентны.

СЛЕДСТВИЕ Согласно теореме Хаффмана-Мили, начиная с

разбиения пространства все состояния, попавшие в один

класс, имеют одинаковые реакции. Если отождествить все

состояния, попавшие в один класс, то получаем новый автомат,

который является приведенным по построению. Он эквивалентен

исходному автомату, что следует из определения.

АЛГОРИТМ (построения приведенного эквивалентного

автомата). 1) По таблице выходов строим разбиение .

2) По таблице переходов последовательно строим разбиения ,

используя пункт 2) теоремы. В силу пункта 4) таких шагов будет не

более .

3) В силу пункта 3) первое разбиение, для которого ,

определяет классы эквивалентных состояний.

_____

Определение Автомат Мили называется частичным, если функции перехода или выхода определены не всюду. В этом случае в таблице состояний автомата ставят прочерки.

Для формулировки алгоритма построения минимального конечного автомата «покрывающего» произвольный частичный автомат, нам понадобится ряд понятий.

Определение Слово называется применимым к состоянию , если функция перехода может оказаться неопределенной лишь после считывания последней буквы этого

слов

Определение Дополним алфавиты неопределенным симво лом «-». Слово покрывает слово той же длины, если получается из заменой некоторых букв на прочерк. называются совместимыми словами, если существует слово , покрывающее и и .

Определение Состояния частичного автомата называются совместимыми, если для любого применимого к ним слова выходные слова совместимы.

АЛГОРИТМ (построения всех попарно совместимых состояний)

1) Всевозможные пары состояний изображают в виде клеток. Клетку вычеркивают, если хотя бы для одной буквы . В невычеркнутую клетку вписывают все те пара определенных состояний, в которые может перейти .

2) Во множестве полученных таким образом невычеркнутых клеток вычеркивают те, в которые вписаны вычеркнутые на первом шаге пары.

3) Шаг 2) повторяется до тех пор, пока будет что вычеркивать. Полученное множество невычеркнутых клеток дает все пары совместимых состояний автомата.

Этот алгоритм имеет наглядный вид при .

Определение Множество попарно совместимых состояний

частичного автомата называется группой совместимости.

Определение Конечное число групп совместимости автомата называется группировкой, если любое состояние автомата попадает хотя бы в одну из этих групп.

Определение Группировка называется замкнутой, если для любой группы совместимости , либо хотя бы одно из значений не определено, либо принадлежат одной группе совместимости этой группировки.

Пусть автоматы , имеют одинаковые входные и выходные алфавиты.

Определение Состояние автомата покрывает состояние автомата , если любое слово, применимое к состоянию , будет так же применимо к состоянию , а слово покрывает слово .

Определение Автомат покрывает автомат , если каждое состояние последнего покрывается некоторым состоянием автомата .

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

:	A \ S			:	A \ S
	(0,0)				(0,0)
	(0,1)				(0,1)
	(1,0)				(1,0)
	(1,1)				(1,1)

При сложении, например, двоичных чисел и берем

последовательно пары одноименных разрядов

.

С помощью таблиц убеждаемся, что сумматор "перерабатывает" это слово побуквенно в слово .

Инициальные автоматы можно охарактеризовать одним

специальным отображением.

Определение Пусть есть конечные алфавиты. Отображение называется автоматным оператором, если оно обладает свойствами:

1) ;

2) если у слов совпадают первые букв: , и , то .

ЗАМЕЧАНИЕ 1 Автоматный оператор всегда реализуется в виде некоторого инициального автомата по правилу . Обратно, каждый инициальный автомат порождает автоматный оператор по правилу

.

ЗАМЕЧАНИЕ 2 Если автоматный оператор задан на одном слове , то с помощью алгоритма покрывающего автомата строится

приведенный автомат, переводящий слово в слово .

Определение Состояние инициального автомата называется достижимым из , если .

СЛЕДСТВИЕ Состояние не достижимо из , если

.

АЛГОРИТМ ( нахождения множества достижимых состояний

инициального автомата)

1) Положим

.

По построению каждое последующее множество содержит предыду

щее.

2) Так как после первого совпадения все последующие множе

ства будут совпадать с и , то первое совпа

дение произойдет при . Поэтому есть множество

достижимых состояний.

Определение Инициальные автоматы с ,

называются эквивалентными, если их реакции совпадают, то есть .

Для формулировки алгоритма эквивалентности инициальных автоматов нам понадобится

Определение Прямым произведением автоматов

называется автомат , где

.

ЗАМЕЧАНИЕ Достижимость состояния из в

прямом произведении равносильна тому, что

.

ТЕОРЕМА 12.8 (Мура) Инициальные автоматы

эквивалентны тогда и только тогда, когда для любого достижимого

состояния инициального автомата имеет место равенство .

ЗАМЕЧАНИЕ Из определения достижимости следует, что если

из пространства состояний инициального автомата выбросить все

недостижимые состояния, то получится инициальный автомат,

который будет эквивалентен исходному.

_____

Определение Параллельным соединением двух автоматов с преобразователем информации называется автомат , функции которого определяются по правилу

,

.

Он имеет следующее схематическое обозначение

двух и более автоматов.

Определение Декомпозицией автомата называется представле ние его в виде композиции автоматов с более простой структурой.

Для формулировки алгебраического метода декомпозиции нам понадобится ряд понятий.

Определение Автомат с таблицей переходов

называется триггером.

ЗАМЕЧАНИЕ Триггер порождает три унарных отображения

пространства состояний: . Они

входят во множество всех отображений вида , и это

множество замкнуто относительно операции композиции отображе

ний. Оно называется полугруппой триггера. Аналогично строится

полугруппа для произвольного автомата без

выходов . Она называется полугруппой автомата.

Определение Подгруппа группы называется нормальной, если . Группа называется простой, если у нее нет нетривиальных (= ) нормальных подгрупп.

Определение Автомат называется автоматом простой группы, если его полугруппа является простой группой.

Определение Группа делит полугруппу , если существует