Регулярное Событие

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

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

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

Важнейшими среди таких алгебр являются алгебры Р. С. С операциями, позволяющими все Р. С. Получить из однобуквенных множеств. Наибольший интерес представляет вопрос о конечно-аксиоматизируемости алгебр Р. С., то есть вопрос о существовании в таких алгебрах конечных полных систем тождеств. В самой общей постановке ответ на этот вопрос отрицателен, хотя существуют важные подалгебры алгебр Р. С., в к-рых конечная полная система тождеств существует. См. Также Автомат, Автоматов способы задания, Синтеза задачи. Лит.:[1] К у д р я в ц е в В. Б., А л е ш и н С. В., П о д к о л з и н А. С., Элементы теории автоматов, М., 1978. [2] С а л о м а а А., "Проблемы кибернетики", 1966, в. 17, с. 237- 246. [3] Я н о в Ю. И., там же, 1964, в.

12, с. 253-58. 1966, в. 17, с. 255-58. [4] У ш ч у м л и ч Ш., "Докл. АН СССР", 1979, т. 247, № 3, с. 561-65. В. А. Буевич.