Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

3.3. Кодирование, автоматы и группы на графах

Автоматы-преобразователи

Существует большая группа автоматов, в частности, распознавательных, которые после первого входного символа уже не возвращаются в свое начальное состояние. Элементарным распознавателем будет автомат задержки, изображенный на рис. 3.41, если к нему добавить еще одну вершину без входящих в нее дуг (рис. 3.45). Этот автомат распознает четыре типа векторов: 00, 11, 10 и 01. Когда на входе автомата появляется последний символ вектора, на выходе формируется 1 или 0:

00 → 0, 11 → 1, 10 → 1, 01 → 0.

Рис. 3.45

Данный автомат можно переделать так, чтобы он распознавал только две последовательности — 11 и 00. Для этого нужно изменить характеристики дуг «вход/выход» 1/0 и 0/1 на 1/ * и 0/ *. Тогда на выходе получим следующую реакцию на входные векторы:

00 → 0, 11 → 1, 10 → *, 01 → *,

В частности:

	 x  =  0 0 1 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 ...
         y  =  * 0 * 1 * * * 0 0 * * * 1 1 * 0 * * 0 ... 

Распознаватель трех единиц (отмечается 1) и трех нулей (отмечается 0) задан табл. 3.24, а графически — с помощью рис. 3.46; на все другие входные последовательности этот автомат реагирует символом « * ». Орграф для распознавания четырех единиц и нулей будет состоять уже из семи вершин, но по-прежнему он будет подчиняться симметрии относительно вертикали и в свое начальное состояние q = 0 не возвратится.

Таблица 3.24

q/x	0	1
0	1,*	4,*
1	2,*	4,*
2	2,0	4,1
3	1,*	3,1
4	1,*	3,*

Рис. 3.46

Табл. 3.25 задает распознаватель следующей системы векторов: 000 → 0, 111 → 1, 001 → 1, 110 → 0, на все остальные последовательности из 0 и 1 автомат реагирует «*».

Таблица 3.25

q/x	0	1
0	1,*	4,*
1	2,*	4,*
2	2,0	4,1
3	1,0	3,1
4	1,*	3,*

Табл. 3.26 определяет автомат для распознавания таких последовательностей: 000 → 0, 111 → 1, 001 → 1, 1100 → 0, 1101 → 1. Имея определенный опыт в проектировании распознавателей, можно создать автомат для регистрации любой последовательности.

Таблица 3.26

q/x	0	1
0	1,*	4,*
1	2,*	4,*
2	2,0	4,1
3	2,0	3,1
4	1,*	3,*

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

y1 = A(10) = 01	y4 = A(001) = 101	y7 = A(01001) = 11110
y2 = A(000) = 101	y5 = A(011) = 110	y8 = A(11010) = 01010
y3 = A(111) = 011	y6 = A(1100) = 0101	y9= A(110110) = 010111

Построение автомата A начнем с вычерчивания бинарного дерева, отвечающего указанным входным и выходным символам (рис. 3.47).

Рис. 3.47

В этом дереве неизвестные пока состояния автомата A обозначены числами, начиная с 0 и кончая 19. Далее руководствуемся следующим правилом: если корень q дерева T_q поместить в вершину q' и при этом реберные характеристики «вход/выход» поддерева T_q' целиком совпадут с реберными характеристиками исходного дерева T_q (факт эквивалентности характеристик дуг двух деревьев обозначим как T_q ≈ T_q'), то будем считать состояния q и q' эквивалентными (q ≈ q'). Процедуру установления эквивалентных состояний начнем с корня 0 и продолжим согласно нумерации вершин.

Состояния 0, 1 и 2, судя по характеристикам дуг, явно неэквивалентны. Если в вершину 3 поместить корневую вершину 2, то совмещенные дуги рассматриваемых деревьев T₃ и T₂ будут иметь одинаковые характеристики «вход/выход», т.е. T₃ ≈ T₂, следовательно, состояние 3 ≈ 2. Это обстоятельство автоматически влечет за собой эквивалентность еще двух концевых вершин — 7 ≈ 5, 8 ≈ 6.

Рассмотрим вершину 4. На первый взгляд, она эквивалентна вершине 0, так как отходящие от нее две дуги имеют те же характеристики, что и корень, т.е. 0/1 и 1/0. Но следующие характеристики дуг, а именно: 0/1 (дуга, выходящая из вершины 9) и 1/0 (дуга, выходящая из вершины 13) не совпадают с характеристиками дуг: 0/0 (дуга, выходящая из вершины 1) и 1/1 (дуга, выходящая из вершины 3). Значит, состояния 4 и 0 неэквивалентны и все вершины поддерева T₄ (9, 10, 13, 16) оставляем пока под прежними номерами.

Пропустим вершину 5 и перейдем к вершине 6. Устанавливаем, что T₆ ≈ T₁ (рис. 3.48), следовательно, 11 ≈ 3 ≈ 2, 12 ≈ 4, 14 ≈ 7 ≈ 5, 15 ≈ 6 ≈ 1. Поскольку T₁₅ ≈ T₁, имеем: 17 ≈ 3 ≈ 2, 18 ≈ 4, 19 ≈ 9. Эта промежуточная фаза анализа эквивалентности состояний автомата-преобразователя A отображена на рис. 3.48.

Рис. 3.48

Концевые вершины 5 и 10 всегда совместимы с корнем 0, поэтому 10 ≈ 5 ≈ 0. Впрочем, состояние 10 можно было бы идентифицировать как состояние 1, 2 или 3, работа автомата A, как можно будет впоследствии проверить, от этого не меняется.

На последнем этапе устанавливаем эквивалентность: T₉ ≈ T₂; тогда 9 ≈ 2, 13 ≈ 0 и 16 ≈ 2. В заключение нашего анализа вершину 4 пометим как 3, чтобы не нарушать числовой последовательности в обозначениях. Окончательно, состояния бинарного дерева получат те номера, которые изображены на рис. 3.49.

Рис. 3.49

По этому дереву уже можно строить орграф преобразователя A (рис. 3.50) и таблицу переходов и выходов (табл. 3.27). Результат построения преобразователя A нелишне проверить на конкретных преобразованиях кодовых векторов x в y (табл. 3.28).

Рис. 3.50

Таблица 3.27

q/x	0	1
0	1,1	2,0
1	2,0	3,1
2	0,1	1,1
3	2,1	0,0

Таблица 3.28

x	10	000	111	...	01001	11010	110110
y	01	101	011	...	11110	01010	010111
q	20	123	213	...	13202	21212	212132

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