§ 8.4. Синтез конечных автоматов и последовательностных машин при задании, сформулированном на языке регулярных выражений

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

Задача такого рода по существу решена уже в гл. VII. Действительно, первая теорема Клини была доказана в этой главе эффективно, т. е. доказательство теоремы содержало метод построения автомата, представляющего любое событие, заданное регулярным выражением. Если задано несколько регулярных выражений, то этим же методом можно построить для каждого из них свой представляющий автомат, а выходы этих автоматов подать на вход общего преобразователя. Однако мы сталкиваемся здесь с ситуацией, подобной той, которая встречалась нам уже в § 8.2: решение задачи нам известно, но оно не удовлетворяет нас, так как при этом решении синтезируемая машина имеет чрезмерно большое число k состояний, и поэтому она неудобна для последующей минимизации.

Ниже кратко описывается иной метод построения конечного автомата, представляющего одно или несколько событий, заданных регулярными выражениями. Этот метод является естественной графической интерпретацией метода, предложенного В. М. Глушковым [252], и приводит к автоматам с меньшим числом состояний, чем метод, использованный в гл. VII при доказательстве первой теоремы Клини.

Начнем со случая, когда задано одно регулярное выражение. Форма записи регулярных выражений, которая удобна нам здесь, несколько отличается от формы записи, введенной в гл. VII. Именно, исходными элементами при составлении регулярного выражения в гл. VII служили конечные куски входных лент (т. е. конечные последовательности входных символов ), которые мы обозначали там первыми буквами латинского алфавита: . Здесь удобно в качестве исходных элементов принимать сами входные символы , т. е. только входные последовательности длины .

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

Поэтому по регулярному выражению с исходными элементами немедленно составляется соответствующее регулярное выражение с исходными элементами — символами .

Так, например, регулярное выражение, которое в обозначениях гл. VII имело вид

при приобретает вид

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

Следующим этапом построения автомата, представляющего соответствующее регулярное событие, является изображение этого регулярного выражения в форме графа.

Построение графа определим индуктивно следующим образом:

1. Для исходных скобок, т. е. скобок

графы представлены на рис. 8.1.

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

Рис. 8.1.

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

Итерация изображается (рис. 8.1, в) стрелкой, замкнутой «на себя» и несущей надпись . Точка замыкания считается одновременно началом и концом этого графа.

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

Тогда граф выражения получается путем объединения начал графов .

В полученном графе началом служит точка, полученная объединением начал , концами — все концы как графа так и графа Граф выражения получается путем объединения всех концов графа с началом (так что стрелки в графе , которые вели в его , ведут теперь в начало ). Началом графа служит начало графа концами — все концы графа .

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

Рис. 8.2.

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

Определив эти операции над графами, мы теперь можем для каждого регулярного выражения построить соответствующий ему граф. Приведем примеры. Регулярное выражение

имеет граф, показанный на рис. 8.2, где приведены также и промежуточные графы.

Регулярное выражение

имеет граф, показанный на рис. 8.3.

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

Рис. 8.3.

Графы, изображенные на рис. 8.2 и 8.3, этому условию удовлетворяют. Однако нетрудно указать регулярные выражения, для которых графы, построенные по указанным выше правилам, уже не будут удовлетворять этим условиям:

Так, например, для выражения

соответствующий граф (рис. 8.4) имеет «ложные пути». Действительно, путь, соответствующий входной последовательности , показанный на рис. 8.4 жирной линией, соответствует выражению

т. е. не соответствует наступлению события .

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

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

соответствует граф, показанный на рис. 8.6. На графе существует путь от начала к концу, однако событие не наступает.

Рис. 8.4.

Рис. 8.5.

Приведенные три примера (рис. 8.4 — 8.6) характеризуют все три случая, которые могут привести к появлению на графе ложных путей. Такие случаи возможны при выполнении следующих операций:

Рис. 8.6.

1) умножение слева на дизъюнкцию, если хотя бы один из дизъюнктивных членов заканчивается итерацией

2) операция дизъюнкции, если хотя бы один из дизъюнктивных членов начинается с итерации

3) умножение двух итераций

Рис. 8.7.

Рис. 8.8.

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

Рис. 8.9.

Расстановку пустых стрелок продемонстрируем, исправляя с их помощью графы приведенных трех примеров (рис. 8.4 — 8.6). Исправленные графы показаны соответственно на рис. 8.7, 8.8 и 8.9. В первом случае пустая стрелка ведет из конца итерации; во втором случае пустая стрелка ведет из общей начальной вершинц в начало итерации; в третьем случае пустая стрелка ведет из конца первой итерации в начало второй итерации.

Этим графам соответствуют приведенные выше регулярные выражения, однако ложных путей графы уже не содержат.

В качестве основного примера, на котором будет демонстрироваться описываемый метод синтеза автомата, рассмотрим выражение

Граф, соответствующий регулярному выражению (8.1), с введением пустых стрелок везде, где это необходимо, изображен на рис. 8.10. На этом рисунке надписи над стрелками имеьг и верхние индексы. Их смысл поясняется ниже.

Рис. 8.10.

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

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

Так, например, регулярное выражение (8.1) нашего основного примера после простановки номеров у перепишется так:

Обращаясь теперь к графу, проставим верхние индексы (номера) у всех символов , надписанных над стрелками, в соответствий с перенумерованным регулярным выражением. В нашем примере, над стрелками графа, показанного на рис. 8.10, выписаны верхние символы в соответствии с выражением (8.2).

Выпишем теперь у каждого узла графа верхние индексы всех входящих в него стрелок, а у начального узла, кроме того, выпишем индекс 0. Все индексы узла, из которого выходит пустая стрелка, приписываются к индексам узла, к которому эта пустая стрелка подходит (но не наоборот!). Одинаковые индексы дважды у одного и того же узла не выписываются. На рис. 8.11 показан граф нашего примера с выписанными индексами у всех узлов.

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

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

Рис. 8.11.

В нашем примере таблица с залолненными двумя строками имеет вид табл. 8.51.

Таблица 8.50

Таблица 8.51

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

Таблица 8.52

Таблица 8.53

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

1, 7, 12 и столбца , вписываются верхние индексы к всех символов , надписанных над стрелками, которые выходят из всех узлов графа, среди индексов которых содержится хотя бы один из индексов 1 либо 7, либо Если таких выходящих стрелок нет, в клетку вписывается символ.

В табл. 8.53 показано заполнение введенных трех строк.

Далее вновь дополним табл. 8.53 столькими строками, сколько содержится новых, не встречавшихся ранее заполнений во введенных ранее трех строках. Соответственно вводятся новые строки и в их клетки вписываются индексы по указанным выше правилам. Этот процесс наращивания таблицы закончится в конечное число шагов, так как общее число различных сочетаний индексов конечно. Если N — число букв в заданном регулярном выражении, то всего имеется индексов и возможно не более чем различных сочетаний индексов, т. е. различных заполнений клеток таблицы, и, следовательно, в таблице может быть не более чем строк.

Отметим «галочками» слева все строки, содержащие в леврм столбце индексы, которые приписаны конечным узлам (концам графа).

Результат построения таблицы для нашего примера приведен в табл. 8.54.

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

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

Поясним это обстоятельство, используя рассмотренный пример. Подадим на вход нашего автомата при начальном состоянии входную последовательность Автомат придет в состояние . Символом (сравните табл. 8.54 и 8.55) обозначено множество индексов 7, 12. Но тогда из самого способа построения тафь 8.54 следует, что на графе (рис. 8.11) существует путь (возможно, проходящий через пустые стрелки), ведущий из начала графа и такой, что символом служит или . Поставим теперь вопрос: означает ли последовательность наступление заданного события? Применительно к графу этот же вопрос можно сформулировать так: существует ли путь рфзрь ведущий по графу из начального узла в один из конечных? Табл. 8.54 позволяет ответить на этот вопрос: поскольку путь может канчиваться символом , а стрелка с таким символом ведет к конечному узлу (а именно, к тому, которому приписан индекс 12), то искомый путь существует.

Таблица 8.54

Таблица 8.55

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

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

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

Соответствующий граф изображен на рис. 8.12. Применение описанного алгоритма приводит к построению таблиц 8.56 и 8.57.

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

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

Рис. 8.12.

Таблица 8.57

Таблица 8.56

Однако построение с помощью графа нагляднее и поэтому более удобно для этой книги.

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

Пусть заданы определенные события . Рассмотрим формулу

Эта формула не содержит итераций (так как события определенные) и, следовательно, граф не будет содержать петель (т. е. ни один путь не пройдет два раза через один и тот же узел). Формулу можно преобразовать к такому виду , что: 1) граф будет деревом, т. е. в каждый узел будет вести только одна стрелка и, следовательно, разные пути всегда приведут в разные узлы; 2) из одного узла не могут выходить две стрелки с одной и той же буквой входного алфавита. Формула S эквивалентна формуле , но может отличаться от нее числом букв. Обозначим число букв в формуле через . Тогда можно построить автомат, представляющий систему событий , число состояний которого не превышает .

Практически при использований описанного метода получаются автоматы с гораздо меньшим числом состояний.