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

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

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

Первая операция — объединение. Множество С, содержащее все последовательности, как те, что входят в множество А, так и те, что входят в множество В, назовем объединением А и В и обозначим .

Так, например, если множество А состоит из четырех последовательностей а множество В — из двух последовательностей

то множество С в этом случае состоит из всех шести выписанных выше последовательностей, т. е.

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

назовем произведением множеств А и В, а операцию получения С — умножением А на В и запишем эту операцию так

Если, например, множество А состоит из четырех, а множество В — из двух последовательностей, рассмотренных в предыдущем примере, то множество . В состоит из следующих восьми последовательностей:

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

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

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

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

Даже если множество В конечно, множество бесконечно. Так, в нашем примере множество В состояло из двух элементов

Элементами бесконечного множества являются, наппимео. последовательности

и т. д.

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

С помощью введения трех операций из множеств А и В образуются новые множества. Эти новые множества сами могут быть приняты за исходные, и из них с помощью тех же трех операций могут быть опять образованы новые множества и т. д.

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

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

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

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

Назовем регулярным множеством входных последовательностей:

1) любое исходное множество,

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

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

Пример 1.

В этом случае регулярное множество — объединение трех исходных последовательностей.

Пример 2.

Регулярное множество — множество всех последовательностей, начинающихся с b и содержащих затем лишь повторенный любое число раз элемент (последовательность) , например:

Заметим, что благодаря введению пустой последовательности в определение , в множество R входит также символ b сам по себе.

Пример 3.

Это множество содержит все последовательности, состоящие из последовательностей и , повторяющихся в любом порядке любое число раз и заканчивающихся последовательностью с, например: с, abc, aabc, baabc, baaaabbc и т. д.

Пример 4.

Здесь R — множество всех последовательностей, заканчивающихся последовательностью а.

Пример 5.

Это множество содержит все последовательности, которые заканчиваются непосредственно следующими друг за другом последовательностями а и b.

Пример 6.

В этом случае R содержит все последовательности, начинающиеся с а, заканчивающиеся последовательностью b и содержащие где-либо внутри последовательность с.

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

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

Наибольшее число «скобок в скобках» в регулярном выражении (с учетом наружных скобок) называется глубиной регулярного выражения. В приведенных примерах глубина равна единице только в примере 4, равна двум в примерах 1, 2, 5 и равна трем в примерах 3 и 6.

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

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

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

Заметим также, что подмножество регулярного множества входных последовательностей не обязательно регулярно. Это следует, например, просто из того, что универсальное множество регулярно по определению, а нерегулярные множества существуют (пример нерегулярного множества см. далее, в § 7.6).

Напомним, что в этом параграфе рассматривались входные последовательности, «обезличенные» в отношении номеров тактов.

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

превращается в множество, состоящее из трех входных лент

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

Теперь можно приступить к классификации событий на входе автомата.

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

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

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

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

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