АЛГЕБРЫ СОБЫТИЙ

— алгебры универсальные, элементы которых представляют собой множества слов на некотором алфавите, т. е. события. Так как понятие события совпадает с понятием языка в теории языков формальных, то можно говорить и об алгебре языков. К осн. операциям А. с. относят операции объединения, умножения и итерации (см. Регулярные события и выражения). При изучении различных классов событий, напр., представимых в автоматах того или иного вида, очень часто оказывается полезным выяснить следующий вопрос; является ли данный класс событий некоторой А. с., обладающей теми или иными хорошо описываемыми свойствами. Поэтому для теории автоматов характерным является ряд теорем, устанавливающих замкнутость или незамкнутость различных классов событий относительно указанных выше, а также других операций над событиями. Одной из наиболее изученных алгебр является алгебра регулярных событий. Она обладает рядом интересных свойств: она конечно-порождаема, является макс. алгеброй, содержащей все конечные события (т. е. события, состоящие из конечного числа слов) и др. Класс контекстно-свободных языков, который играет важную роль в теории формальных языков, также является А. с. Однако свойства этой алгебры не описываются так хорошо, как свойства алгебры регулярных событий, являющейся в данном случае подалгеброй алгебры контекстно-свободных языков. В качестве дополнительных операций в алгебру регулярных событий часто вводят также операции пересечения и дополнения, относительно которых класс регулярных событий оказывается замкнутым.

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

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

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

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

где , выводимо и и наоборот. Это правило вывода появляется не случайно; оно связано с большими возможностями, которые дает аппарат решения уравнений. Проблему решения уравнений можно поставить для любой универсальной алгебры, но она не только в общей постановке, но и относительно отдельных классов уравнений обычно бывает весьма сложной. В произвольной алгебре уравнение имеет вид , где выражения, построенные из переменной элементов алгебры и операций алгебры. Если уравнение имеет решение и при том единственное, то оно служит средством неявного задания некоторой, вообще говоря, новой операции для элементов алгебры. Так, уравнение (1) при задает итерацию события S. Существенным является то, что уравнение (1) относится к т. н. линейным уравнениям. Рассмотрение систем линейных уравнений в А. с. дает новые средства для изучения алгебраических и теоретико-автоматных зависимостей, в частности, дает возможность осуществлять анализ конечных автоматов. Система линейных уравнений имеет вид:

где коэффициенты — элементы данной алгебры событий.

При некоторых ограничениях на вхождение пустого слова в коэффициенты — такая система имеет единственное решение, причем, если все и регулярны, то и все также регулярны. Существует алгоритм решения системы (2), аналогичный алгоритму Гаусса для систем обычных линейных уравнений.

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

Кроме систем уравнений, в А. с. изучали и системы уравнений вида

где — события, а выражения в правых частях понимаются как суперпозиции. Такая система всегда имеет решения (среди ее решений одно является минимальным в смысле теоретико-множественного включения); при некоторых ограничениях, связанных с вхождением пустого слова в система (3) имеет единственное решение. Для теории формальных языков представляют интерес системы, у которых конечные события. Решением такой системы (единственным или минимальным) будет кортеж из контекстно-свободных языков Системы вида (3) тесно связаны со средством описания (задания) различных формальных языков, в частности с помощью контекстно-свободных грамматик (см. Грамматика порождающая).

Лит.: Глушко» В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464-469]; Ginzbuгg A. Algebraic theory of automata. New York - London, 1968 [библиогр. с. 157—160].