РЕГУЛЯРНЫЕ СОБЫТИЯ И ВЫРАЖЕНИЯ

— события, представимые в автоматах конечных, и соответствующие выражения в специальном алгебраическом языке, задающие эти события. Событием наз. произвольное мн-во слов в некотором алфавите. Естественно, что при изучении теорией автоматов различных вопросов, связанных с понятием события (см. Алгебраическая теория автоматов), обычно предполагается наличие каких-либо средств для описания (задания) событий. Таким конструктивным средством может быть формальный язык, выражения которого задают события над некоторым алфавитом (т. е. формальный язык интерпретируется в мн-ве событий). Если обозначить этот язык через его правильно построенные выражения можно называть Л-выражениями, а события, которые они задают, -событиями. Очевидно, что mh-bq всех Л-событий для любого языка L не более чем счетно, т. к. мн-во соответствующих выражений не более чем бчетно. Поскольку мощность мн-ва всех событий континуальна, то нет такого языка L, для которого все события являются Л-событиями.

Для теории автоматов характерен следующий подход. Фиксируется некоторый класс автоматов К. Ставится задача: построить язык L (обычно не использующий непосредственно автоматных понятий, удобный в том или ином отношении, удовлетворяющий определенным требованиям и т. д.), такой, что все -события и только они представимы в автоматах кдасса К. Решение этой задачи включает в себя доказательство двух теорем — теоремы синтеза (каждое -событие представимо в некоторрм автомате класса К) и теоремы анализа (каждое событие, представимое в автомате класса К, является -событием). Обычно теорема синтеза сразу предполагает наличие алгоритма синтеза, т. е. алгоритма построения автомата по заданному событию, а теорема анализа — алгоритма анализа, т. е. алгоритма построения Л-выражения по заданному автомату.

Впервые такой подход в теории автоматов применил амер. математик С. К. Клинч

(p. 1904) для класса конечных автоматов. Для событий, представимых в конечных автоматах, он построил спец. язык — язык регулярных выражений. Этот язык стал одним из осн. языков для задания условий функционирования автомата, в особенности после совершенствования его (а также соответствующих алгоритмов синтеза и анализа) в работах сов. математика В. М. Глушкова, амер. математика Р. Ф. Мак-Нотона и др. авторов.

Алгебр, язык строится как язык выражений некоторой алгебры (см. Алгебры универсальные). В данном случае рассматривается язык для описания событий, поэтому мн-во всех событий представляет собой некоторую универсальную алгебру, т. е. над событиями определяются алгебр, операции (см. Алгебры событий). Для построения языка регулярных выражений были использованы три операции над событиями (две бинарные и одна унарная): 1) А V В - дизъюнкция или объединение - (обозначаются также ); 2) - умножение (конкатенация); 3) - итерация (обозначается также . Дизъюнкция — теоретико-множественная операция: событие А у В представляет собой обычное объединение мн-в А и В. Умножение событий определяется через умножение слов. Произведением слов слово , образованное в результате дописывания слова q справа к слову . Событие состоит из тех и только тех слов, которые имеют вид q, где принадлежит A, a q принадлежит В.

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

Выражение, построенное из букв алфавита X (символов элементарных событий) и из символов операций дизъюнкции, умножения и итерации с использованием соответствующим образом круглых скобок, наз. регулярным выражением в алфавите X. Всякое регулярное выражение R определяет некоторое событие S (S получается в результате выполнения всех операций, входящих в выражение R). События, определяемые т. о., наз. регулярными событиями над алфавитом X. Др. словами, регулярным событием наз. событие, полученное из элементарных с помощью применения конечного числа фаз операций дизъюнкции, умножения и итерации. Напр., в алфавите из трех букв х, у, z регулярное выражение задает событие (регулярное), состоящее из всех слов, которые начинаются буквой х и заканчиваются буквой у или z. Регулярные события и только они представимы в конечных автоматах.