Теория вычислительных процессов (стр. 10 )

Наглядным способом задания ОКА служат графы автоматов. Автомат представляется графом, множество вершин которого – множество состояний , и из вершины в вершину ведет дуга, помеченная символом , тогда и только тогда, когда программа автомата содержит команду . Работе автомата над заданным словом соответствует путь из начальной вершины . Последовательность проходимых вершин этого пути – это последовательность принимаемых автоматом состояний, образ пути по дугам – читаемое слово. Любой путь в графе автомата, начинающийся в вершине и заканчивающийся в вершине , порождает слово, допустимое автоматом.

Пример ОКА , допускающего слова , задается графом (рисунок 1.6).

Программа содержит команды:

;

;

;

;

;

;

;

.

Рис. 1.6 Пример ОКА

Автомат называется пустым, если . Автоматы и эквивалентны, если .

Для ОКА доказано:

1)  Проблема пустоты ОКА разрешима. Доказательство основано на проверке допустимости конечного множества всех слов, длина которых не превышает числа состояний ОКА - . Если ни одно слово из этого множества не допускается, то ОКА «пуст».

2)  Проблема эквивалентности ОКА разрешима. Доказательство основано на использовании отношения эквивалентности двух состояний и ': если состояния и эквивалентны, то для всех состояния и также эквивалентны.

1.4.2 Многоленточные автоматы

Многоленточный (детерминированный, односторонний) конечный автомат (МКА) задается так же, как ОКА. Отличие состоит в том, что множество состояний разбивается на непересекающихся подмножеств . «Физическая» интерпретация -ленточного автомата отличается тем, что он имеет лент и головок, по головке на ленту. Если автомат находится в состоянии , то -я головка читает -ю ленту так же, как это делает ОКА. При переходе МКА в состояние -я головка останавливается, а -я начинает читать свою ленту. МКА останавливается, когда головка на одной из лент прочитает символ #.

Пример. Рассмотрим функционирование МКА с (рисунок 1.7) на примере сравнения пар слов в алфавите и допуске только совпадающих слов.

Здесь , где ; ; ; , начальное состояние ‑ . МКА обрабатывает наборы слов , где слово записано на первой ленте, а ‑ на второй. Допустимое множество наборов ‑ это все возможные пары одинаковых слов, т. е. наборы, где . Например, набор может быть и т. п.

Рис. 1.7 Пример МКА

В том случае, когда слова совпадают, МКА остановится в заключительном состоянии (именно в этом состоянии поступит символ #) и набор будет допущен. Если слова не совпадут хотя бы в одном символе, МКА перейдет в состояние , из которого не выйдет до появления символа #, который и зафиксирует отсутствие совпадения слов, т. е. не допустит искаженный набор.

1.4.3 Двухголовочные автоматы

Двухголовочный конечный автомат (ДКА) имеет одну ленту и две головки, которые могут независимо перемещаться вдоль ленты в одном направлении. Множество состояний разбито на два непересекающихся множества. В состояниях активна первая головка, а в состояниях ‑ вторая.

Двухголовочный автомат можно рассматривать как такой двухленточный автомат, который работает с идентичными словами на обеих лентах.

Пример. ДКА проверяет равенство двух последовательно записанных слов в алфавите . Признаком окончания каждого из слов является вспомогательный символ , не входящий в . Автомат должен допускать только слова вида , где . , где ‑ множество состояний, в которых активна первая головка; ‑ множество состояний, в которых активна вторая головка; ‑ множество, содержащее единственное заключительное состояние. Граф автомата показан на рисунке 1.8, на котором вместо многих «параллельных» дуг с разными пометками нарисована одна дуга со всеми этими пометками.