Дискретная математика:
логика, группы, графы, фракталыАкимов О.Е.
3.3. Кодирование, автоматы и группы на графах
Автоматы задержки и распознавания символов
Рассмотрим рис. 3.39, где изображено бесконечное бинарное дерево, переводящее входную последовательность из нулей и единиц в выходную. Дерево имеет два типа вершин — 0 и 1, а каждое ребро снабжено дробью: числитель означает входной символ, знаменатель — выходной; концевые ребра оканчиваются стрелками, указывающими на возможное продолжение ветвей. Жирной линией выделена входная последовательность x = 1010, которая преобразуется в выходную y = 1100.
Рис. 3.39
Бесконечным бинарным деревом задается автомат A, который в зависимости от входного символа может оказаться в одном из двух состояний. Начальным состоянием является q = 0. Если на входе автомата окажется x = 0, он не меняет своего первоначального состояния q = 0, а на выходе появляется y = 0. Если на входе x = 1, автомат переходит в состояние q = 1, а на выходе будет y = 1. Оказавшись в состоянии q = 1, автомат ведет себя следующим образом: если x = 0, то y = 1 и q = 1; если x = 1, то y = 0 и q = 0.
В общем случае автомат A можно задать четырьмя способами:
1) Один из способов как раз изображен на рис. 3.39, т.е. с помощью достаточного фрагмента бесконечного дерева, вершинами которого являются состояния автомата, а на ребрах указываются входные и выходные символы. Это наиболее громоздкое представление автомата.
2) Бесконечному дереву отвечает более компактный сильно связанный орграф (рис. 3.40).
Рис. 3.40
3) Аналитическая форма задания автомата осуществляется двумя функциями:
функцией переходов q' = φ(x, q); функцией выходов y = f(x, q).
Конкретный вид этих функций в нашем случае прост — сложение аргументов по mod (2):
q' = x + q, y = x + q.
4) Функции можно задать с помощью таблицы, где в заголовке указываются: по горизонтали — входные символы x, по вертикали — исходное состояния автоматов q; в клетках таблицы на первом месте — новое состояния q', на втором месте после запятой — выходной символ y. Для нашего примера будем иметь табл. 3.18.
Таблица 3.18
q/x 0 1 0 0,0 1,1 1 1,1 0,0 Наш конкретный автомат A обладает одним замечательным свойством: он реагирует на четность числа единиц, поданных на его вход. Пусть в качестве начального состояния будет q = 0, а на вход подается бесконечная последовательность x из 0 и 1 (табл. 3.19).
Таблица 3.19
x 0 0 1 1 0 1 0 0 0 1 0 1 1 ... y0 0 0 1 0 0 1 1 1 1 0 0 1 0 ... y1 1 1 0 1 1 0 0 0 0 1 1 0 1 ... Тогда нечетное количество единиц на входе автомата A будет отмечаться единицами на выходе (y0). Если же в качестве начального состояния выбрать q = 1, то нечетное число единиц на входе будет отмечаться уже нулями на выходе (y1).
Рассмотрим еще один пример автомата, когда функция переходов принимает значение входного символа (q' = x), а функция выходов — значение состояния (y = q). Таблица функций такого автомата представлена табл. 3.20, а реакция на входную последовательность для различных начальных его состояниях — табл. 3.21.
Таблица 3.20
q/x 0 1 0 0,0 1,0 1 0,1 1,1 Таблица 3.21
x 0 0 1 1 0 1 0 0 0 1 0 1 1 ... y0 0 0 0 1 0 0 1 1 1 1 0 0 1 ... y1 1 0 0 1 0 0 1 1 1 1 0 0 1 ... Из табл. 3.21 видно, что автомат на выходе независимо от начального состояния просто сдвигает все входные символы на одну позицию вправо. Его называют автоматом задержки на один такт. Сильно связанный орграф такого автомата показан на рис. 3.41.
Рис. 3.41
Как видно из рисунка, орграф автомата задержки обладает элементарной группой симметрии относительно перестановки состояний, а также входных и выходных символов 0 и 1. Любопытно построить автомат задержки на два такта: будет ли его орграф обладать симметричными свойствами? Ответ окажется утвердительным (рис. 3.42), хотя число его состояний возрастает до 4, а число дуг — до 8 (табл. 3.22).
Рис. 3.42
Таблица 3.22
q/x 0 1 0 0,0 1,0 1 2,1 3,0 2 0,1 1,1 3 2,1 3,1 Автомат задержки на три такта также обладает элементарной симметрией и состоит уже из 8 состояний и 16 дуг (рис. 3.43). Симметрия означает неизменность рисунка при действии на состояния элементарной подстановкой (07)(16)(25)(34) и при одновременной смене входных и выходных символов на противоположные. При этом направление дуг остается прежним, т.е. дуга, идущая из вершины 3 в вершину 7, сохраняет свое направление и после перестановки состояний, но ей присваивается характеристика вход/выход 0/1 вместо 1/0 и т.д.
Рис. 3.43
Три последних орграфа являются эйлеровыми, так как для них существуют полные контуры, включающие все дуги по одному разу. Причина в том, что для каждой вершины число выходящих и входящих дуг четно. Этого факта достаточно, чтобы орграф был эйлеровым. Обход орграфа, изображенного на рис. 3.41, по эйлерову контуру сопровождается выходной последовательностью 0011, если обход начать с петли, или 0110, если сначала идти к вершине 1. Однако это две одинаковых последовательности, сдвинутые на позицию относительно друг друга. Поэтому их принимают за одну и считают, что в этом графе существует только один эйлеров контур. Для орграфа, изображенного на рис. 3.42, существует два эйлеровых контура с выходными последовательностями 00010111 и 00011101. Орграф, изображенный на рис. 3.43, имеет уже 16 таких обходов (табл. 3.23)
Таблица 3.23
0000101001101111 0000111100101101 0000101101001111 0000111101001011 0000101100111101 0000111101011001 0000100110101111 0000111101100101 0000110111100101 0000100111101011 0000110101111001 0000101111001101 0000110100101111 0000101111010011 0000110010111101 0000101001111011Если величину задержку обозначить как t, то получим следующие комбинаторные формулы: число вершин в орграфе автомата задержки равно n = 2t ; число ребер — m = 2t + 1; число эйлеровых контуров — N = 2n/m. Три последних орграфа соответствуют значениям t = 1, 2, 3. При отсутствии задержки, т.е. при t = 0, орграф представлен одной вершиной с двумя петлями — 0/0 и 1/1. Для этого орграфа выполняется одно из важнейших свойств всего ряда автоматов задержки, а именно: для каждой вершины (а здесь она одна) имеются две входящие и две выходящие дуги. Если орграф без задержки (t = 0) обозначим как Г0, а с задержками (t = 1, 2, 3 ...) как Г1, Г2, Г3 и т.д., то в этих обозначениях каждый последующий орграф Гt +1 является реберным по отношению к предыдущему Гt. Условимся орграф Гt +1 называть реберным, если каждой дуге ej орграфа Гt соответствует вершина qj в Гt +1. Кроме того, если e1 — дуга орграфа Гt , начало которой есть конец дуги e0, то в Гt +1 имеется дуга q01 с началом в вершине q0 и концом в вершине q1. Именно при этих условиях из орграфа Г0 путем удвоения числа вершин и дуг получается орграф Г1; из Г1 строится Г2 и т.д.
Теперь перейдем от автоматов задержки к автоматам другого типу. До сих пор рассмотренные нами автоматы имели сильно связанные орграфы, т.е. эти автоматы могли из любого своего состояния перейти в любое другое, минуя промежуточные. А возможно ли создать автомат, когда какое-либо состояние становится недостижимым, например, из начального? Да, возможно. Таков, в частности, автомат со следующими функциями переходов и выходов:
q' = x ∧ q, y = x ∨ q.
Данный автомат описывается просто связанным орграфом, для которого вершина 1 является недостижимой из вершины 0 (рис. 3.44).
|
|
