Математическая энциклопедия - регулярное событие

множество слов конечного алфавита, к-рое на алгебраич. языке может быть задано с использованием выражений специального вида р е г у л я р н ы х в ы р а ж е н и й. Пусть А - конечный алфавит и символы операций, наз. о б ъ е д и н е н и е м, к о н к а т е н а ц и е й и и т е р а ц и е й соответственно. Р е г у л я р н ы е в ы р а ж е н и я в алфавите Азадаются индуктивно: 1) каждая буква из алфавита Аесть регулярное выражение, 2) если R1, R2 и R - регулярные выражения, то суть также регулярные выражения. Язык регулярных выражений интерпретируется следующим образом.

Пусть A*-множество всех слов в алфавите A, . Символ любой буквы из Апонимается как множество, состоящее из одной буквы, а как обычное теоретико-множественное объединение. Множество состоит из всех слов, к-рые представимы в виде a1,a2 где , причем если и содержат пустое слово , то

. Пусть и для любого имеет место обозначение (праз). Тогда совпадает с т. е. если , то существует такое, что a представимо в виде a1 a2 . . . a m, где для любого i= = 1, . . ., т. Таким образом, множество слов конечного алфавита является р е г у л я р н ы м с о б ы т и е м тогда и только тогда, когда оно может быть получено из однобуквенных множеств с помощью применения конечного числа операций объединения, конкатенации и итерации. Р. с. могут быть заданы и с помощью других операций, сохраняющих регулярность (напр., пересечение, дополнение и т. п.), а также путем задания множества слов, выводимых в формальных системах типа систем полу-Туэ (см. Туэ система), грамматик и т. д.

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

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

См. также Автомат, Автоматов способы задания, Синтеза задачи.

Лит.:[1] К у д р я в ц е в В. Б., А л е ш и н С. В., П о д к о л з и н А. С., Элементы теории автоматов, М., 1978; [2] С а л о м а а А., "Проблемы кибернетики", 1966, в. 17, с. 237246; [3] Я н о в Ю. И., там же, 1964, в. 12, с. 253-58; 1966, в. 17, с. 255-58; [4] У ш ч у м л и ч Ш., "Докл. АН СССР", 1979, т. 247, № 3, с. 561-65. В. А. Буевич.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985