§ 4.2. Отличимость состояний автомата

4.2.1 Продолжение функций и

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

Произведением слов называется слово, полученное приписыванием к слову справа слова Таким образом, если то Нетрудно проверить, что произведение слов ассоциативно, т.е. для любых Вообще, произведение слов не зависит от расстановки скобок (но зависит от порядка сомножителей). В частности,

Произведение слов некоммутативно, так как в общем случае

Множество, на котором задана ассоциативная операция, называется полугруппой. Полугруппа в которой есть единица, т.е. такой элемент е, что для всех называется моноидом. Множества и являются полугруппами. Кроме того, – моноид (так как для всех то пустое слово является единицей). Полугруппа моноидом не является; это можно доказать так: ввиду того, что для любых то равенство в невозможно.

Функции и можно продолжить до функций и следующим образом. Положим

при

при

при

при

Функция несёт информацию о том, в какое состояние перейдёт автомат, если на его вход будут поступать последовательно несколько букв из алфавита Действительно, если в какой-либо момент автомат находится в состоянии а на его вход поступают буквы то будут осуществляться следующие переходы в другие состояния:

т.е. в конце концов автомат окажется в состоянии Аналогичным образом интерпретируется функция А именно, где буква, которая будет выдана автоматом на -м шаге.

Упражнение 5. Автомат задан таблицей

	a	b	c
	0	0	1
	0	1	1

Определить:

Решение.

поэтому

поэтому

Упражнение 6. Автомат задан диаграммой Мура, изображённой на рисунке 4.10. Найти:

Решение. Имеем: поэтому

4.2.2. Приведённый автомат

Назовём состояния и автомата неотличимыми, если для всех Состояния и отличимы, если при некотором Положим если и неотличичимы. Нетрудно видеть, что отношение неотличимости ~ на множестве состояний автомата является отношением эквивалентности. Это отношение вызывает разбиение множества на непересекающиеся классы эквивалентности: При этом любые два состояния лежащие в одном классе, неотличимы, а любые два состояния из разных классов отличимы.

Множество классов отношения ~ (фактор-множество обозначим через Построим новый автомат В качестве входного и выходного алфавитов автомата возьмём те же множества и которые были у автомата а в качестве множества состояний возьмём множество Надо определить теперь функции и

Пусть Наиболее естественным является следующее определение значения взять какой-нибудь элемент принадлежащий классу найти а затем класс, в котором лежит элемент объявить значением То есть считать, что

(1)

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

Функцию определим на по формуле

(2)

По определению неотличимости состояний мы имеем поэтому определение (2), как и (1), корректно.

Автомат называется приведённым автоматом, соответствующим автомату

У приведённого автомата любые два различных состояния отличимы друг от друга.

Автомат и приведённый автомат работают одинаково: для любой входной последовательности последовательность на выходе автомата и автомата одна и та же: и т.д. (здесь – начальное состояние).

Упражнение 7. Построить приведённый автомат для автомата, заданного диаграммой Мура, изображённой на рисунке 4.11.

Решение. Вычислим: Следовательно, состояние отличимо от всех остальных. Мы получаем (пока) следующее разбиение множества на классы, т.е. непересекающиеся подмножества: (далее это разбиение будет измельчаться).

Далее вычисляем: Отсюда следует, что не может лежать в одном классе с или с или и т.д. Разбиение, полученное ранее, измельчается до следующего: Положим Покажем, что это окончательное разбиение. Имеем: поэтому Аналогично получаем и т.д., т.е. функция “не разбивает” классы. Следовательно, классы можно считать состояниями нового автомата. Это и есть приведённый автомат, его диаграмма Мура изображена на рисунке 4.12.

Упражнение 8. Построить приведённый автомат для автомата , заданного следующей таблицей:

0	1	1	0	1	1
1	1	0	1	0	0

Решение. Верхняя строка таблицы 11011 определяет разбиение нижняя строка  разбиение Их пересечение это разбиение Докажем, что состояния неотличимы друг от друга. В столбцах таблицы, соответствующих этим состояниям, мы имеем: значит, функция на состояниях принимает одинаковые значения. Кроме того, другая часть столбцов: такова, что лежат в одном классе разбиения. Это доказывает, что неотличимы. Из таблицы автомата теперь нетрудно получить таблицу приведённого автомата – для этого достаточно взять по одному представителю в каждом классе разбиения Таким образом, мы получаем:

0	1	1	0
1	1	0	1