§ 7.5. Регулярность представимых событий

В настоящем параграфе будет доказана теорема, обратная доказанной выше.

Вторая теорема Клини. В конечном автомате представимы только регулярные события.

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

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

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

могут следовать лишь триады, у которых в левой нижней клетке вписан символ , например

И не могут следовать триады с иным символом в этой, например

От точки, соответствующей триаде проведем стрелки ко всем точкам, соответствующим триадам, которые могут следовать после (рис. 7.7), и так поступим со всеми триадами .

В результате (пример на рис. 7.8) на плоскости будет изображен граф, который мы назовем лабиринтом триад.

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

а путь

невозможен, так как после триады не может следовать триада (в лабиринту триад на рис, нет стрелки от ).

Рис. 7.7.

Рассмотрим теперь последовательности (цепочки) триад вне связи с каким-либо конкретным автоматом и его лабиринтом триад. Введем понятие о регулярном, множестве цепочек триад, определив его по индукции так: по определению всякое множество, содержащее только одну триаду, регулярно; если А и В — регулярные множества цепочек триад, то регулярны и:

а) их объединение , т. е. множество, содержащее как цепочки А, так и цепочки В;

б) произведение , т. е. множество цепочек, которое получается приписыванием справа к каждой цепочке из А любой цепочки из В и

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

Рис. 7.8.

Лемма. Множество всех путей, ведущих от триады к триаде в лабиринте триад любого конечного автомата, является регулярным множеством цепочек триад.

Лемму докажем индукцией по q, где q — число различных триад в пути от к .

Для лемма очевидна. В этом случае совпадает с и возможны только два подслучая:

а) если символы в нижней строке этой триады различны, то множество путей состоит только из одного пути, содержащего лишь эту одну триаду ,

б) если , имеет в нижней строке одинаковые символы , то множество путей включает все цепочки триад содержащие повторение одной и той же триады , т. е. итерацию . Следовательно, это множество регулярно.

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

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

Пусть . Тогда весь рассматриваемый путь от к можно представить себе состоящим из триад между которыми расположены регулярные множества .

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

Поэтому все пути, ведущие из в , являются элементами итерации этого произведения

т. е. составляют регулярное множество цепочек триад.

Если , то аналогично множество всех путей, ведущих из в , есть

т. е. также регулярно. Лемма доказана.

Лемму удобно пояснить, воспользовавшись нашим геометрическим образом — лабиринтом триад;

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

Прежде всего, есть выбор из двух путей:

и

Далее, первый путь может быть удлинен обходом петель, например

Петли можно обходить любое конечное число раз, например

либо еще более усложнять путь движением по «петлям внутри петель», например

Рис. 7.9.

Ситуация такого рода имеет место не только в рассмотренном примере, но является общей. Всякое Множество путей из может содержать прежде всего несколько вариантов простых путей , при этом оно состоит из стрелок, проходимых одна после другой , либо из обхода любое конечное число раз любой встречающейся на пути в лабиринте триад петли (итерация!). Каждый путь из в может быть составлен из этих трех элементов. Этот факт, почти очевидный при рассмотрении нашего геометрического образа — лабиринта триад — и утверждается леммой. Из доказанной леммы немедленно следует и доказательство второй теоремы Клини.

Доказательство второй теоремы Клини. Рассмотрим какой-либо конечный автомат. Выпишем все его триады (их число конечно).

Пусть М — множество некоторых из символов и (элемент этого множества обозначим через ), и автомат представляет событие на входе появлением какого-либо состояния из множества М при начальном состоянии .

Выберем какую-либо триаду так, чтобы символ к, вписанный в ее правой нижней клетке, принадлежал множеству М (остальные два символа в ней произвольны).

Выберем также какую-либо триаду , у которой в левой нижней клетке вписан символ и, а остальные два символа произвольны

В силу доказанной леммы множество всех путей, ведущих из в , является регулярным множеством цепочек триад.

Рассмотрим множества А и А всех возможных триад . Множество всех путей, соединяющих какую-либо триаду из с какой-либо триадой из , является объединением множеств путей, ведущих от фиксированной триады , к фиксированной триаде , т. е. регулярно.

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

Если некоторое множество цепочек триад является регулярным множеством, то множество соответствующих последовательностей символов является регулярным множеством последовательностей в том смысле, который был определен в § 7.3.

Действительно, при составлении новых путей из заданных с помощью трех операций (объединение, произведение и итерация) над цепочками триад мы над последовательностями в этих цепочках совершили лишь операции, аналогичные введенным в § 7.3, для получения регулярных множеств последовательностей.

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