Синтез алгоритмов программ регулярными выражениями алгебры событий

Размещено на http://www.allbest.ru/

Пензенский филиал научно-технического центра «Атлас»

Пензенский государственный университет)

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

Чижухин Г.Н., Кулагин О.В.

1. Введение

Равносильные преобразования алгоритмов [2] - это формальные преобразования, позволяющие переводить заданный алгоритм в алгоритм, эквивалентный ему в расширенном смысле. Под последним понимается свойство алгоритмов перерабатывать исходные данные в эквивалентные результаты и сущность его определяется конкретно для каждого класса алгоритмов. Например, графическое тождество исходных данных является частным случаем их эквивалентности, а эквивалентность алгоритмов - частным случаем равносильности алгоритмов, ибо каждый преобразуемый алгоритм рассматривают в совокупности с областью его задания, которая может составлять часть области его применения.

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

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

В работе вводится понятие регулярного выражения алгоритма (РВА), т.е. уравнения алгоритма, составленного на основе алгебры событий [1, 3].

2. Схемы представления алгоритмов и алгебра событий

Рассмотрим различные представления алгоритма, исходя из схемы, заданной ГСА. На рис.1а приведена ГСА, а на рис. 1б и 1в - тот же алгоритм, но в виде других графов.

Рис. 1 Различные схемы представления алгоритма: а) ГСА; б) ориентированный общепринятый граф; в) ориентированный инверсный граф

Согласно существующей методике переход от ГСА к схеме ориентированного общепринятого графа осуществляется так: в описании последнего каждому линейному оператору ГСА соответствует вершина этого графа, а условным и безусловным переходам - его ребра (рис. 1б). Обозначение операторов алгоритма разными элементами графа делает схему общепринятого графа неудобной для выполнения равносильных преобразований алгоритма.

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

Алгебра событий [1, 3] определяет для множества всех событий операции дизъюнкции, произведения и итерации. Дизъюнкцией двух событий S₁ Ъ S₂ называется теоретико-множественное объединение событий S₁ и S₂, означающее наступление одного из событий S₁ и S₂. Произведением (или конкатенацией) двух событий S₁· S₂ (или S₁ S₂) называется событие, состоящее из всех слов вида pq, где p любое слово события S₁, а q любое слово события S₂. При этом произведение означает поочередное наступление событий S₁ и S₂ в указанном порядке, причем S₁S₂ № S₂S₁. Итерация события S (обозначается {S}) есть событие, состоящее из пустого слова e и всевозможных слов вида p₁ p₂...p_n, где p₁, p₂,..., p_n произвольные слова события S, а n любое натуральное число n = 1, 2,.... В выражениях алгебры событий определен следующий порядок выполнения операций итерация, произведение, дизъюнкция (если отсутствуют круглые скобки, изменяющие порядок вычислений). Операции алгебры событий удовлетворяют целому ряду известных свойств алгебры логики (идемпотентности и коммутативности дизъюнкции; левой и правой дистрибутивности произведения по отношению к дизъюнкции; закону нейтральности пустого слова из правил грамматики).

Для описания инверсного графа при помощи алгебры событий будем использовать следующие виды событий: 1) событие при определенном условии а (для существующих условных переходов); 2) событие, определяемое оператором (для линейных операторов); 2) безусловное событие l, состоящее из одного пустого слова е (для безусловных переходов либо для обозначения сохранения состояния); 3) невозможное событие, обозначенное 0 (для несуществующих переходов). Безусловное событие l можно считать всегда происходящим подобно тому, как в теории множеств пустое множество Ж определяется подмножеством всякого множества. Невозможное событие 0 есть событие, которое не содержит ни одного ( в том числе и пустого) слова, т.е. это событие никогда не происходит. В табл. 1 приведено соответствие событий переходам в инверсном графе.

Таблица 1

Соответствие событий переходам в инверсном графе

Отдельно следует определить операции дизъюнкции и конкатенации в алгебре событий для тех случаев, когда хотя бы одним операндом является безусловное событие l или невозможное событие 0. К ним относятся следующие выражения: lЪS, 0S, S0, 0ЪS, lS, Sl, lЪ0, l0, 0l (где под S понимается либо событие по условию а, либо событие, определяемое оператором, например А3). Для этих выражений в табл. 2 представлены графические интерпретации, а также результаты, полученные на основе этих интерпретаций, причем. результат выражений lS и Sl определяется законом нейтральности пустого слова:

l S = S l = S

Таблица 2

Графические интерпретации и результаты, полученные на основе этих интерпретаций

Так как безусловное событие l можно считать всегда происходящим, а дизъюнкция двух событий S = S₁ Ъ S₂ означает наступление хотя бы одного из них, то при S₁ = l или S₂ = l событие S также будет всегда происходить. То есть,

l--Ъ--S = l.

Невозможное событие 0 не происходит никогда. Для дизъюнкции получим:

0 Ъ S = S

Поскольку, конкатенация двух событий S=S₁S₂ означает событие, которое произойдет только в случае наступления в указанном порядке событий S₁ и S₂, то в случае, когда хотя бы одно событие - S₁ или S₂ - равно нулю, получим

0 S = S 0 = 0

Выражения для дизъюнкции и конкатенации событий l и 0 могут быть получены из выражений (3), (4) путем замены события S на событие l.

3. Регулярное выражение алгоритма

Под РВА будем понимать алгебраическую запись алгоритма в виде регулярного выражения с использованием алгебры событий [1, 3]. Прежде всего необходимо провести уточнение некоторых конструкций регулярных выражений для более четкого описания алгоритмов. Условным и линейным операторам алгоритма в РВА будут соответствовать переменные, последовательности операторов - операция их конкатенации, параллельным ветвям алгоритма - операция дизъюнкции переменных, циклам - операция итерации переменных. Условные операторы алгоритма будут указываться в квадратных скобках для того, чтобы отличить их от линейных операторов, при этом условный оператор [а=1] соответствует безусловному событию l, а условный оператор [а=0] - невозможному событию 0. То есть, если в последовательности операторов содержится условие, которое не выполнится в процессе исполнения программы, то выполнение всей последовательности прервется. Поэтому, условная конструкция представляется в виде двух параллельных ветвей: одна ветвь для ложного условия, другая ветвь - для истинного. Цикл с заранее заданным числом повторов n и телом цикла А обозначается как {A}ⁿ (так как повторение тела цикла n раз аналогично операции возведения в степень n значения А) или как {A}<n>, где n - константа (обозначение с угловыми скобками вводится для более удобного представления этого выражения в виде текстовой строки в ПЭВМ). Цикл с предусловием обозначается как [a=1]Ъ{[a=0](A)}, а цикл с постусловием - {(A)[a=0]}. Для этих циклов внутри фигурных скобок располагается тело цикла, в котором указываются: условные операторы (в квадратных скобках), определяющие продолжение цикла, и остальные операторы цикла (заключенные в круглые скобки). Для цикла с предусловием в РВА операция дизъюнкции показывает, что цикл выполняется только при a=0, а при a=1 осуществляется переход к следующему оператору. Эти уточнения регулярных выражений не нарушают алгебру событий.

Согласно теореме о структуре программы [4], для построения программы любой сложности достаточно трех типов алгоритмических конструкций: линейной, условной и циклической. В табл. 3 приведены стандартные программные конструкции в трех видах: в виде ГСА, в виде записей на языке программирования высокого уровня (ЯВУ) и в виде алгебраических регулярных выражений. Между ГСА и регулярными выражениями существует взаимно-однозначное соответствие, суть которого видна из табл. 3. При конкатенации приведенных регулярных выражений отдельных алгоритмических конструкций будет получаться регулярное выражение алгоритма.

Таблица 3

Стандартные программные конструкции

4. Регулярные выражения и алгебра матриц

В работе [5] доказаны две теоремы, определяющие возможности: 1) построения по любому регулярному выражению соответствующего ему конечного автомата ( КА); 2) построения по любому КА соответствующего ему регулярного выражения. Поскольку конструкции алгоритмов программ могут быть описаны при помощи регулярных выражений, то согласно упомянутым выше теоремам алгоритм любой программы может быть представлен в виде КА.

Абстрактный КА осуществляет однозначное отображение (в общем случае частичное) некоторого множества входных слов в соответствующие им выходные слова той же длины, причем, согласно условиям автоматности на каждом такте своей работы, КА воспринимает одну букву входного слова и выдает одну букву выходного слова [1]. Говорят также [5], что КА реализует некоторый оператор, перерабатывающий входные слова в выходные. Однако, описывать алгоритмы программ в терминах операторных отображений (т.е. в виде абстрактных КА) неудобно, поскольку в этом случае: 1) входным словом такого КА будут не только исходные данные алгоритма, но и все промежуточные значения, получающиеся в процессе его выполнения; 2) выходным словом этого КА будут не только выходные данные алгоритма, но опять-таки и все его промежуточные значения. Более того, промежуточное значение, в зависимости от использования его конкретным оператором алгоритма, будет принадлежать как входному (для входных данных оператора), так и выходному слову КА (для выходных данных оператора).

Тем не менее существует один класс КА, который, являясь частным случаем абстрактных КА, в то же самое время не описывается в терминах операторных отображений. Эти КА названы в [5] настроенными конечными автоматами без выходов (НКАБВ). Любой НКАБВ есть совокупность пяти объектов [5] - множества входных слов Х, множества состояний Q, функции переходов Y; начального состояния q₀ и некоторого подмножества конечных (финальных) состояний Q' (причем Q'М Q). Множество всех входных слов НКАБВ, переводящее его из начального состояния в одно из конечных, называется языком, представленным в НКАБВ. Задание такого языка равносильно заданию НКАБВ.

Линейные и условные операторы алгоритма могут быть представлены буквами слов этого языка, а порядок следования операторов, т.е. порядок следования букв в слове языка, будет соответствовать адресам операторов. Поэтому, язык, представимый в НКАБВ, можно использовать для описания алгоритма программы (причем граф переходов этого НКАБВ должен соответствовать инверсному графу алгоритма рис. 1в.), а поскольку НКАБВ является частным случаем абстрактного КА, то теорию КА можно использовать для формирования РВА.

Одним из способов описания КА является квадратная автоматная таблица [1], в которой строки столбцы обозначены различными состояниями КА, а элементы таблицы, стоящие на пересечении i-строки и j-го столбца, есть множество всех входных сигналов, вызывающих переход КА из состояния i в состояние j. Такое множество может не содержать ни одного слова, даже пустого.

Квадратная автоматная таблица при фиксации нумерации состояний натуральными числами 1, 2, 3,… и при расположении строк и столбцов ее в соответствии с этой нумерацией превращается в квадратную автоматнуюматрицу ччa_ijч?, в которой строки и столбцы соответствуют различным состояниям автомата, а элемент матрицы a_ij есть условие перехода, определяемое тем множеством входных сигналов, например х₁,…х_n, которое переводит автомат из состояния i в состояние j. Поэтому, алгоритм любой программы может быть описан некоторой квадратной матрицей A=ззa_ijзз, элементами которой будут линейные и условные операторы алгоритма.

Теорема: Если построить квадратную автоматную матрицу А для инвер-сного графа любого алгоритма, имеющего m вершин (из них одна начальная - 1 и одна конечная - m), где циклы представлены в виде «черного ящика» с одним входом и одним выходом (для каждого из которых уже имеются регулярные выражения соответствующих частей алгоритма), то после возведения матрицы А с этими регулярными выражениями в степень (m-1), элементом а_1m новой матрицы А ^(m -¹⁾ будет являться регулярное выражение всего алгоритма.

Доказательство: Произведение двух квадратных матриц определяет мультиграф, любые две вершины которого i и j соединяются некоторым множеством путей, каждый путь составлен из двух ребер, причем первое ребро пути принадлежит первому графу, а второе ребро - второму графу. Иными словами, любое множество таких путей образовано двумя группами ребер - ребрами, исходящими из вершины i, и ребрами, заходящими в вершину j. Они соединяются между собой через общие вершины. Следовательно, в результате произведения символьных матриц А=ззa_ijзз и B=ззb_ijзз должна получиться другая символьная матрица С=ззс_ijзз, в которой любой ее элемент с_ijдолжен определять то же множество путей, но в символьном виде, в данном случае в виде регулярного выражения. Так как последовательному соединению событий соответствует операция конкатенации, а параллельному - операция дизъюнкции, то с учетом того, что ребра, исходящие из вершины i, составляют i-ю строку символьной матрицы, а ребра, заходящие в вершину j, образуют j-й столбец такой матрицы, то может быть определено произведение (конкатенация) двух символьных матриц С=АВ согласно следующему выражению:

(или )

При умножении двух одинаковых символьных матриц А согласно выражению (5) получится матрица, которая, по аналогии с алгеброй числовых матриц, может быть названа второй степенью матрицы А, и обозначена через А². В матричной форме можно записать:

алгоритм матрица алгебра событие

А² = АА

Определим последующие степени символьных матриц как последовательность следующих произведений:

A² = AA, A³ = A²A,... A^m = A^(m-1) A

В матрице А² содержатся пути в графе, состоящие из двух дуг. За счет дальнейшего присоединения к ним связанных с этими путями ребер исходного графа можно получить пути, состоящие из трех ребер. Подобные рассуждения аналогич-ны и для путей произвольной длины. То есть, справедливы выражения (5) - (7). Поскольку инверсный граф алгоритма имеет m вершин, то самый длинный путь в нем не может иметь больше (m -1) ребер. Так как в этом графе циклы представлены в виде «черного ящика» с одним входом и одним выходом, то процесс нахождения РВА завершится нахождением матрицы A^(m-1) и поскольку начальная вершина инверсного графа обозначена через 1, а конечная через m, то РВА будет являться элементом a_1m матрицы A^(m-1). Теорема доказана.

Рассмотрим пример, иллюстрирующий использование этой теоремы. Возьмем некоторый алгоритм, его ГСА на рис. 2а, его инверсный граф - на рис. 2б.

Рис. 2 Пример алгоритма: а) ГСА; б) инверсный граф

В следующей табл. 4. приведем его квадратную автоматную матрицу.

Таблица 4

Квадратная автоматная матрица

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

В алгоритме рис.2 содержатся два цикла - с предусловием (рис.3а) и пост-условием (рис.3б). На рис.3 показаны инверсные графы этих циклов, а также инверсный граф всего алгоритма, в котором тело цикла Спредставлено в виде «черного ящика» с одним входом и одним выходом (рис.3в).

Рис. 3 Инверсные графы частей алгоритма: а) цикл с предусловием B; б) тело цикла с постусловием С; в) алгоритм с «укрупненным» представлением циклов

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

Теперь необходимо найти регулярное выражение для цикла В. Проведенная в инверсном графе цикла «упаковка», в квадратной автоматной матрице сведется к замене безусловного перехода l между вершинами 3 и 1 (обратная связь в цикле) переходом l между вершинами 3 и 4 (выход из цикла). В результате получится исходная квадратная автоматная матрица, представленная на рис.4а.

Так как в инверсном графе цикла В содержится четыре вершины, то в матрице для него будет столько же столбцов и строк, и возводить ее надо в 3-ю степень. Все степени этой матрицы для цикла В приведены на рис.4.

а) степень 1 (исходная матрица)

б) степень 2

в) степень 3

Рис. 4 Квадратные автоматные матрицы для цикла В при разных степенях

В первой строке и последнем столбце матрицы 3-й степени получается регулярное выражение для цикла В, в котором необходимо отметить при помощи фигурных скобок тело цикла:

В = [a₁ = 1] Ъ {[a₁ = 0](A4)}

Для получения регулярного выражения тела цикла С (рис. 3б) используются квадратные автоматные матрицы с шестью строками и столбцами, так как в инверсном графе этого цикла шесть вершин. Исходная квадратная матрица приведена в табл. 5, а ее последующие степени - в табл. 6-10. В них на место цикла В подставлено его регулярное выражение (8).

Таблица 5

Степень 1 (исходная квадратная автоматная матрица)

Таблица 6

Степень 2

Таблица 7

Степень 3

Таблица 8

Степень 4

Таблица 9

Степень 5

Таблица 10

Степень 6

В строке 1 и столбце 7 табл. 10 содержится регулярное выражение для тела цикла С:

С = A1[a₀ = 0] A2 A3 Ъ A1[a₀ = 1]([a₁ = 1] Ъ {[a₁ = 0](A4)})

Инверсный граф алгоритма, изображенный на рис.3в, также содержит четыре вершины. Регулярное выражение для него находится с использованием квадратной автоматной матрицы, все степени которой приведены на рис. 5.

Р = {(С)[a₂ = 0]}[a₂ = 1] А5

а) степень 1

б) степень 2

в) степень 3

Рис. 5 Квадратные автоматные матрицы для «укрупненного» инверсного графа алгоритма

Подстановкой (9) в (10) получается общее РВА:

Р={(A1[a₀=0]A2A3ЪA1[a₀=1]([a₁=1]Ъ {[a₁=0](A4)}))[a₂=0]}[a₂=1]А5

5. Заключение

В статье введено и обосновано понятие регулярного выражения алгоритма.

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

Список литературы

1. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962.

2. Чижухин Г.Н. Лекции по основам математической логики и теории алгоритмов. Учеб. пособие. Пенза: Издательство ПГУ, 1999.

3. Глушков В.М. Кибернетика, вычислительная техника, информатика. Избранные труды. Т.1: Математические вопросы кибернетики. Некоторые проблемы синтеза цифровых автоматов. Киев: Наукова думка, 1990. с. 103 - 139.

4. Герасименко В.А., Гудинович Г.И. Математические основы структурного программирования // Зарубежная радиоэлектроника, 1977, № 12. с.14 - 33.

5. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы (поведение и синтез). М.: Наука, 1970.

Размещено на Allbest.ru