Эквивалентность автоматов. Минимизация

 

Рассмотрим два автомата:

,

.

Состояния из множества автомата и соответственно из множества автомата В называются неразличимыми, если .

Автоматы и называются неразличимыми, если для любого состояния существует состояние , такое, что , и наоборот, .

Рассмотрим изменения состояний и выходов автомата с изменением времени. На каждом такте подается входной сигнал (символ), преобразуется внутреннее состояние, возникает сигнал выхода. Рассмотрим следующий такт. Действия аналогичны:

, .

Итак, автомат преобразует слова (как и машина Тьюринга, частным случаем которой является конечный автомат).

Рассмотрим состояние автомата . Состояние называется достижимым из состояния , если существует такое слово , что . Достижимые состояния образуют класс достижимых состояний (рис. 4.4).

а б

Рис. 4.4. Достижимое состояние (а) и класс достижимых состояний (б)

 

Рассмотрим два автомата , и состояния . Автоматы называются эквивалентными, если

Иными словами, автоматы называются эквивалентными, если для каждого состояния существует эквивалентное ему состояние автомата . Эквивалентные автоматы обладают одинаковым внешним поведением, т.е. на одинаковые входные слова выдают одинаковые внешние слова. Автоматы могут различаться сложностью внутренней структуры, например, мощностью множеств и . Среди всех эквивалентных автоматов имеется минимальный. Одной из основных задач является следующая: найти автомат, эквивалентный данному, но обладающий наименьшим количеством внутренних состояний. Такие задачи решаются последовательно путем выявления одного неразличимого состояния, двух неразличимых состояний,…, неразличимых состояний, которые объединяются в классы неразличимых состояний.

Пример:

Автомат	Состояния	Классы состояний
A											1,5,8
	6/1	6/2	1/2	5/2	6/1	6/2	8/2	6/1	6/2		2,9
	3/1	7/1	3/2	3/2	7/1	7/2	7/2	4/1	4/1		3,4,6,7
	6/2	3/2	9/1	2/1	6/2	6/1	2/1	6/2	4/2		–

На начальном этапе отыскиваем классы -эквивалентных неразличимых состояний (при ):

 

A				Классы
										1,5,8
	6/1	6/1	6/1	6/2	6/2	½	5/2	6/2	8/2		2,9
	3/1	7/1	4/1	7/1	4/1	3/2	3/2	7/2	7/2		3,4,7
	6/2	6/2	6/2	3/2	4/2	9/1	2/1	6/1	2/1

 

Приходим к автомату, внутренние состояния которого отождествляются с найденными классами эквивалентных состояний:

 

	3/1	3/2	1/2	4/2
	3/1	3/1	3/2	3/2
	3/1	3/2	2/1	4/1

 

У полученного и исходного автоматов внешнее поведение одинаково.

 

Контрольное задание

 

Воспользовавшись данными, приведенными в табл. 4.2, выполнить следующее:

а) построить граф для каждого из заданных автоматов (рекомендуется использовать VISIO);

б) минимизировать автоматы, построить графы, проверить правильность минимизаций на словах длиной 20;

в) установить, эквивалентны ли заданные автоматы, проверить на слове длиной 20.

 

Таблица 4.2

Варианты задания

 

Номер варианта

А

В

8/1

8/2

8/1

5/2

8/1

3/2

1/2

8/2

8/2

4/2

7/2

4/2

2/1

4/2

4/2

3/1

7/1

6/1

4/1

7/2

6/1

6/2

7/2

6/2

4/1

1/1

2/1

6/1

5/2

6/1

3/1

2/2

8/2

7/2

8/2

2/1

8/2

2/1

9/1

8/1

4/2

7/1

1/1

1/1

1/2

1/1

1/1

1/2

Окончание табл. 4.2

 

Номер варианта

А

В

3/1

3/2

3/2

5/2

3/1

1/2

8/2

3/1

3/2

6/2

7/2

6/2

6/2

7/2

7/1

7/2

6/1

7/1

7/2

6/2

7/1

6/2

7/2

4/1

4/1

1/2

1/1

4/2

3/2

3/1

3/1

1/2

3/2

6/2

3/1

2/1

3/2

9/1

2/1

3/2

4/2

5/1

4/2

2/1

2/1

1/2

7/2

7/1

3/2

8/1

7/1

2/2

3/2

3/2

3/2

2/2

8/1

7/2

6/2

7/2

7/2

6/2

6/2

6/1

4/1

7/2

7/2

1/1

5/1

1/1

7/1

8/1

8/2

1/2

1/1

4/2

3/2

4/1

1/2

4/1

9/1

1/2

6/2

3/1

9/1

2/1

1/1

4/1

6/2

5/1

3/2

2/1

2/1

1/2

6/1

6/2

3/1

3/2

3/2

5/2

3/1

1/2

8/2

3/1

3/2

7/2

6/2

7/2

7/2

6/2

6/2

6/1

6/1

7/1

7/2

6/2

7/1

6/2

7/2

4/1

4/1

1/2

1/1

4/2

3/2

4/1

1/2

4/1

3/2

6/2

3/1

2/1

3/2

9/1

2/1

3/2

4/2

5/1

3/2

2/1

2/1

1/2

6/1

6/2

6/1

6/2

1/2

5/2

6/1

6/2

8/2

6/1

6/2

6/2

6/2

4/2

6/1

4/2

6/2

4/2

3/1

7/1

3/2

3/2

7/1

7/2

7/2

4/1

4/1

7/1

5/1

7/2

7/1

5/2

5/2

3/2

6/2

6/2

9/1

2/1

6/2

6/1

2/1

6/2

4/2

5/2

3/2

2/1

6/2

1/1

6/1

2/1

3/2

7/1

8/1

2/2

9/2

3/2

3/3

3/2

7/1

7/2

4/2

4/2

1/1

4/2

4/2

3/1

4/1

8/2

8/2

1/1

5/1

1/1

7/1

8/1

7/2

1/1

2/1

6/1

5/2

6/1

3/1

1/2

9/1

1/2

6/2

3/1

9/1

2/1

4/1

1/1

6/2

2/1

7/1

2/1

2/2

2/1

2/1

2/2

3/1

3/2

3/2

5/2

3/1

8/2

1/2

3/1

3/2

7/2

2/2

7/2

7/2

2/2

2/2

2/1

7/1

6/1

6/2

7/2

6/1

6/2

7/2

4/1

4/1

1/2

1/2

4/2

3/2

3/1

1/1

3/1

3/2

7/2

3/1

2/1

3/2

2/1

9/1

3/2

4/2

5/1

2/1

6/1

6/1

1/2

4/2

2/2

8/2

3/1

2/2

2/2

8/2

8/2

9/2

5/1

3/1

7/2

4/2

4/2

1/1

4/2

4/2

3/1

4/1

5/2

3/1

1/1

5/1

1/1

7/1

5/2

3/2

1/1

2/1

6/1

5/2

6/1

3/1

1/2

9/1

1/2

4/1

8/1

1/1

2/1

9/1

6/2

6/2

2/1

7/1

2/1

2/2

2/1

2/1

2/2

1/2

1/2

1/1

5/2

1/1

8/2

3/2

1/1

1/2

5/2

2/2

5/2

5/2

2/1

2/2

2/2

6/2

6/1

7/1

7/2

6/1

6/2

7/2

4/1

4/1

1/2

1/2

4/2

3/2

4/1

1/1

4/1

1/1

7/2

1/2

2/1

1/2

2/1

9/1

1/2

4/2

7/1

2/1

6/1

6/1

2/2

3/2

1/2

6/2

4/2

5/2

4/2

4/1

4/1

8/2

4/1

4/2

5/2

6/2

5/2

5/2

6/1

6/2

6/2

1/2

7/1

1/2

7/2

7/1

1/1

7/2

3/1

3/1

3/2

4/1

1/2

4/2

1/1

4/2

1/1

9/1

1/2

2/1

4/1

4/2

4/2

2/1

4/2

3/2

2/1

3/2

2/1

7/1

6/2

6/1

4/2

Автоматы Мили и Мура. Размеченные графы

Рассмотренные ранее автоматы – это классические автоматы Мили. Автомат Мура – это автомат, выходы которого зависят только от текущего состояния:

,

 

где – алфавит входных сигналов; – алфавит выходных сигналов; , , .

Автомат Мура – частный случай автомата Мили.

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

При табличном задании автомата Мура вместо двух таблиц рассматривается одна, которая называется размеченной функцией перехода:

 

 

Несколько изменяется представление графа. Обозначение выхода ставится возле каждого узла (рис. 4.5).

 

Рис. 4.5. Графическое представление автомата Мура

 

Автоматные языки

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

Частные случаи практически важных КА (конечных автоматов):

– сумматор;

– задержка (автомат задержки – это автомат Мура);

– счетчик.

Автоматы подразделяются на преобразователи и распознаватели. Иногда вместо распознавателя употребляется термин «акцептор». Все предыдущие автоматы являлись преобразователями. В настоящее время одно из основных применений автомата – установление факта принадлежности подстроки данной строке.

Рассмотрим задачу: установить наличие в заданной строке слова «резец». Синтез соответствующего автомата начинается с построения графа (рис. 4.6).

 

Рис. 4.6. Граф распознавания заданного слова

 

По графу строим таблицу, описывающую работу автомата-распознавателя:

 

р	/0	н/0	н/0	н/0	н/0
е	н/0	/0	н/0	/0	н/0
з	н/0	н/0	/0	н/0	н/0
ц	н/0	н/0	н/0	н/0	н/1
S	н/0	н/0	н/0	н/0	н/0

 

Далее подаем некоторую строку. Подстрока считается выявленной, если на выходе появляется единица:

 

а

с

б

л

к

р

р

е

з

а

р

е

з

е

ц

у

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

 

Полученные таблицы для реализации функции допускают сжатие путем составления массива номеров строк и столбцов, отличных от н/0. Количество операций имеет порядок длины слова при автоматном распознавании.

В качестве задания осуществить проверку наличия какого-нибудь слова (или предложения) в произвольно выбранном тексте. Например, рассмотреть исходный текст некоторой программы на алгоритмическом языке PASCAL и проверить наличие выражения «for I:=» в этом тексте.

Основной технический аппарат при изучении автоматных языков – акцепторы, автоматы-распознаватели. Распознаватели осуществляют выделение всех входных предложений, принадлежащих языку. Автоматные языки – очень узкий класс всех возможных языков.

Словарь – это конечное множество.

Элементы словаря – символы (буквы).

Предложение – все конечные последовательности символов из заданного словаря.

– множество всех цепочек, построенных по данному словарю.

Множество содержит бесконечное количество элементов.

Грамматика – конечный механизм задания языка.

Существует два вида грамматик – порождающая и распознающая: первая – это механизм, позволяющий строить все допустимые предложения, вторая – отсеивает из множества те предложения, которые не принадлежат языку.

Синтаксис – правила построения языка.

Возможности автоматов

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

Счетчик. Требуется создать устройство, которое на каждом такте выдает целое число, большее предыдущего на единицу; при достижении некоторого предельного значения серия выводимых значений повторяется. Пусть предельное значение равно шести. Автомат, реализующий алгоритм, является автоматом Мура и может быть описан в стандартном виде:

 

	1/0	2/1	3/2	4/3	5/4	6/5	0/6

 

Предположим, что вслед за этим счетчиком предполагается разместить еще один, который бы отсчитывал количество шестерок. В таком случае достаточно в качестве выходного алфавита принять следующий набор: . Первая из цифр выводится на экран, вторая подается на выход, являющийся входом для следующего счетчика. Если на вход второго счетчика подается 0, то его состояние не меняется и на выход подается пустой символ. Если же подается единица, то он изменяет состояние так же, как и рассмотренный выше счетчик:

 

	0/-	0/-	0/-	0/-	0/-	0/-
	1/0	2/1	3/2	4/3	5/4	0/5

 

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

Счетчик является примером так называемых автономных автоматов, входной алфавит которых содержит единственный символ. Если считать, что в каждой вершине графа имеется один выход, причем выходной сигнал совпадает с номером состояния, то он является эквивалентом отношения порядка, а граф автономного автомата – это простой ориентированный граф [2, 3]. Для входного слова достаточной длины выходное слово автономного автомата содержит периодически повторяющееся подслово.

Проверка четности. Пусть входной алфавит содержит два символа – ноль и единицу. Требуется построить алгоритм, согласно которому на выходе повторяется входное слово, но после каждого подслова, содержащего три символа, должен быть вставлен символ «0», если количество единиц в подслове четно, и символ «1» в противном случае.

Прежде всего отметим, что выходной алфавит конструируемого автомата не может состоять только из нуля и единицы, так как количество символов во входном и выходном словах должно быть одно и то же (требование автоматности).

Это требование удовлетворяется введением такого выходного алфавита: . Выход после третьего символа состоит из двойки символов: «00», «01», «10», «11». Обозначим состояния автомата как «-», «0», «1», «00», «01», «10», «11», подразумевая под «-» стартовое состояние. После этого оказывается возможным построение автомата проверки четности в следующем виде:

 

	-
	0/0	00/0	10/0	-/00	-/01	-/01	-/00
	1/1	01/1	11/1	-/11	-/10	-/10	-/11

 

Выполним кодирование состояний и выходов, сопоставляя состояние «-» и номер 0, «0» – номер 1, «1» – 2, «00» – 3, «01» – 4, «10» – 5, «11» – 6; выход «0» и номер элемента алфавита 0, выход «1» и номер 1, «00» – 2, «01» – 3, «10» – 4, «11» – 5. Тогда таблица построенного автомата примет такой вид:

 

	1/0	3/0	5/0	0/2	0/3	0/3	0/2
	2/1	4/1	6/1	0/5	0/4	0/4	0/5

 

Граф этого автомата изображен на рис. 4.7.

Отметим, что состояния 3 и 6 эквивалентны. Это же относится и к паре состояний 4 и 5. Поэтому в данном случае имеется возможность минимизировать найденный автомат, объединив состояния 3, 6 в класс 3 эквивалентных состояний, а классы 4, 5 – в класс 4. Минимизированный автомат, эквивалентный исходному, в таком случае можно изобразить графически (рис. 4.8) и в виде таблицы:

 

	1/0	3/0	4/0	0/2	0/3
	2/1	4/1	3/1	0/5	0/4

 

Если поставлена задача проверить четность в словах длиной n, то граф неминимизированного автомата будет содержать вершин, а минимизированного – .

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

Рис. 4.7. Граф автомата проверки четности

 

Рис. 4.8. Минимизированный автомат проверки четности

 

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

Напрямую автомат построить в этом случае невозможно, поэтому требуется ввести в рассмотрение входной алфавит, состоящий из пар цифр.

Учитывая, что слагаемые можно переставлять, кодировщик представим в виде матрицы X:

 

	0 (0+0)	1 (0+1)	2 (0+2)
	1 (1+0)	2 (1+1)	3 (1+2)
	2 (2+0)	3 (2+1)	4 (2+2)

 

Например, пара цифр (1,2) кодируется как элемент X[1,2] = 3, как и пара цифр (2,1). Автомат суммирования может быть задан в виде матрицы :

 

	0/0 (0+0 = 0·3 + 0)	0/1 (0+1= 0·3 + 1)
	0/1 (1+0 = 0·3 + 1)	0/2 (1+1= 0·3 + 2)
	0/2 (2+0 = 0·3 + 2)	1/0 (2+1= 1·3 + 0)
	1/0 (3+0 = 1·3 + 0)	1/1 (3+1= 1·3 + 1)
	1/1 (4+0 = 1·3 + 1)	1/2 (4+1= 1·3 + 2)

 

Собственно, сложение производится поразрядным (начиная с младшего разряда) пропусканием двух слов a и b (т.е. чисел, представленных в троичной системе счисления) через цепочку (рис. 4.9).

Рис. 4.9. Автоматное суммирование

 

Достоинством автоматного суммирования является то, что все действия ограничиваются нахождением элементов матриц X и А.

 

Автоматное декодирование. Рассмотрим основную идею на примере. Пусть задана таблица кодов, получаемых как пути в дереве (рис. 4.10). С движением от узла влево сопоставим символ «а», прямо – «б», вправо – «в». Таблица кодов имеет следующий вид:

 

Р	а	Т	ва	Л	бба
К	ба	Ы	ббб	С	вб
О	бв	У	вв	М	ббв

 

В качестве номеров состояний автомата примем номера узлов, не являющихся листами; корень дерева имеет номер 0.

Рис. 4.10. Дерево кодирования

 

Выходной алфавит содержит буквы, соответствующие листам, а также пустой символ «-». В результате получаем таблицу автомата следующего вида:

 

а	0/Р	0/К	0/Т	0/Л
б	1/-	3/-	0/С	0/Ы
в	2/-	0/О	0/У	0/М

 

Для проверки работоспособности построенного автомата предлагается самостоятельно получить выходное слово, если на вход подается слово «бабвабвббвбббвбббабв». Входное слово следует подавать в порядке слева направо (первый входной символ – б, второй – а, третий – б и т.д.).

По каждой из рассмотренных задач желательно самостоятельно сконструировать автоматы, реализующие различные частные случаи.

С помощью конечных автоматов решается огромное количество задач. Тем не менее, имеется множество задач, для которых не существует алгоритмического решения и, следовательно, нельзя построить автомат.

Краткий перечень задач, для которых отсутствует алгоритм решения, таков [1]:

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

2. Проблема эквивалентности алгоритма. По двум произвольным алгоритмам определить, будут ли они выдавать одинаковые выходные результаты при одинаковых входных данных.

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

4. Проблема тотальности. По произвольному заданному алгоритму определить, будет ли он завершаться во всех возможных наборах.