Algebras of languages associated with labelled graphs.pdf В теории конечных автоматов одним из важнейших результатов является теоре-ма Клини, в которой утверждается, что класс языков, распознаваемых конечнымиавтоматами, совпадает с классом рациональных языков, представимых регулярнымивыражениями алгебры Клини [1].В данной работе определяется понятие языка, допустимого в отмеченном графе,вводится система операций на формальных языках, которая, в частности, может ис-пользоваться в биологии, генетике, а также ДНК-вычислениях [2], и понятие регуляр-ных выражений для этой системы операций.Исследованы основные свойства семейства алгебр языков, допустимых в отмечен-ных графах; доказано, что язык допустим в отмеченном графе тогда и только тогда,когда он описывается регулярным выражением во введенной системе операций; разра-ботаны методы анализа и синтеза языков, ассоциированных с отмеченными графами.Пусть X - конечный алфавит; X* -множество всех слов конечной длины в алфа-вите X; Xn - множество всех слов длины n в алфавите X; X- множество всех словконечной длины в алфавите X, длина которых больше или равна n.Определим на множестве X * частичную бинарную операцию о склеивания двухслов с параметром n следующим образом: для всех w1 ,w2 G X*если w1 = xy, w2 = yz, y G Xn;не определено в противном случае.Введем на языках L, R С X* следующие операции:1) L U R = {w : w G L или w G R};2) L о R = |wi о w2 : wi G L и w2 G R};n OO 3) L+ = U L* , где L1 = L; Li+1 = L* n L для всех i ^ 1.i=1Рассмотрим семейство алгебр (2х*, о, и, +, 0). В случае, когда n = 0, операция осовпадает с операцией конкатенации, а рассматриваемая алгебра является алгебройрегулярных языков.Регулярные выражения в алгебре (2х , о, U, +, 0) определим следующим образом:1) 0 является регулярным выражением и представляет язык L(0) = 0;2) x является регулярным выражением и представляет язык L(x) = {x} для всехx G U X*;0 < i < n + 13) если R и Q - регулярные выражения, представляющие языки L(R) и L(Q) соот-n nветственно, то выражения (R о Q), (R U Q), (R+) также являются регулярными,n n n n nпричем L(R о Q) = L(R) о L(Q), L(R U Q) = L(R) U L(Q), L(R+) = (L(R))+.Графом с отмеченными дугами (вершинами) назовем четверку G = (Q, E, X, гдеQ - конечное множество вершин; E С Q х Q - множество дуг; X - конечное множе-ство отметок дуг; ^ : E ^ X (р, : Q ^ X) -функция отметок дуг (вершин). Отметкойпути будем называть последовательность отметок входящих в этот путь дуг (вершин).Пусть I С Q - множество начальных вершин графа G с отмеченными дугами илис отмеченными вершинами, F С Q - множество финальных вершин. Отметки всехпутей в графе G, начальные вершины которых принадлежат множеству I, а конеч-ные - множеству F, назовем языком, допускаемым графом G, и обозначим L(G).Теорема 1. Язык L С X* допустим в графе с отмеченными дугами (вершинами)тогда и только тогда, когда он описывается регулярным выражением любой алгебры, X * из семейства (2х , оn, U, n+ , 0.) .Эта теорема в некотором смысле аналогична широко известной теореме Клини дляконечных автоматов. В случае, когда n = 0 и рассматриваются только графы с от-меченными дугами, теорема 1 совпадает с теоремой Клини. На основе доказательстватеоремы разработаны методы анализа и синтеза языков, представимых в отмеченныхграфах.

Скачать электронную версию публикации