5.4.Контекстно-свободные грамматики (КС- грамматики)

В правилах НС-грамматик по определению заменяется только один символ, левая же часть правила не обязательно состоит из одного символа w

( А®w).

В правилах могут присутствовать и другие символы, то есть контекст:

jАy®jwy.

Разрешается заменять А на w только в контексте j и y. Сам контекст при этой записи просто переписывается.

Правила, использующие контекст, называются контекстно-связанными, а правила, не имеющие контекста – контекстно-свободными(КС-правилами).

НС-грамматики, содержащие только КС-правила вида А®w, называется контекстно-свободными грамматиками (КС-грамматиками).

Языки, порожденные КС-грамматиками, называются КС-языками.

КС-грамматики представляют собой важный частный случай НС-грамматик. Их ценность обусловлена двумя обстоятельствами:

-отказ от контекста делает грамматику более простой;

-хотя в естественных языках запись одних единиц другими часто допустима только в определенных контекстах, целесообразно исследовать возможность описывать языки, отвлекаясь от этого факта, то есть в терминах КС-грамматик, хотя описание может усложниться.

Например, могут потребоваться новые категории, правила.

В самых общих чертах такая замена делается следующим образом :

пусть элементы класса Х ведут себя по-разному в соседстве с элементами класса Y и класса Z, то есть имеют место правила:

YX®YAB;

ZX®ZCD.

Введем новые символы Х1 и Х2.

Элемент Х в позиции после Y обозначим Х1, а Х после Z – через Х2, тогда приходим к КС-правилам:

X1®AB,

X2®CD.

Однако не всякая контекстно-связанная НС-грамматика может быть заменена эквивалентной ей КС-грамматикой.

Существует НС-языки, не являющиеся КС- языками, например, язык, состоящий из всевозможных цепочек вида: (aba,aabbaa,…) или цепочек вида .

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

До сих пор мы занимались введением ограничений на левые части правил грамматик.

Сначала потребовали, чтобы число символов в правой части было бы не меньше, чем в левой и получили неукорачивающие грамматики, затем потребовали, чтобы замене подвергался только один символ, и получили НС-грамматики. Наконец, мы потребовали, чтобы в левой части правила вообще был один символ, и получили КС-грамматики.

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

Начнем с части символов в правой части. В зависимости от числа символов в правой части КС-грамматики можно разделить на два класса:

-бинарные и

-небинарные.

КС-грамматики будем называть бинарными, если правая часть любого правила КС-грамматики содержит не более двух символов.

Например:

A®BC,

A®bB,

A®B,

где A,B,C Î VH , b Î VT .

КС-грамматики будем называть небинарными, если правая часть любого правила содержит более двух символов.

Например:

A®Aab,

В®ABC,

A®w,

где A,B,C Î VH, a,b Î VT, w – непустая цепочка из более чем двух символов.

В С-маркерах, соответствующих бинарным КС-грамматикам из каждой вершины исходит не более двух ветвей. Это значит, что любая сложная составляющая всегда состоит ровно из двух непосредственно вложенных в нее составляющих.

В зависимости от числа входящих в правую часть нетерминальных символов КС-грамматики подразделяются на линейные и нелинейные.

Линейные грамматики – такие КС-грамматики, правые части которых содержат не более чем по одному вхождению нетерминального символа.

Таким образом, для бинарных КС-грамматик это правило вида :

А®aB, A,BÎVH, aÎ VT,

для небинарных КС-грамматик:

A®aBab, A®acB,

A,BÎ VT , a, b, c Î VT.

Соответственно языки, порождаемые этими грамматиками, будем называть линейными и нелинейными.

КС-грамматика называется металинейной , если правая часть ее правил не содержит цели грамматики и все правила, левые части которых отличны от цели , имеют такой же вид, как правила линейной грамматики.

Примером металинейной грамматики может служить следующая грамматика:

G=( {a,b,c}, {S,T}, {SàTT, TàaTa, TàbTb, Tàc},S).

Язык называется металинейным, если существует порождающая его металинейная грамматика.

Накладывая ограничения на состав символов правой части привил КС- грамматик, Флойд выделил следующие подклассы небинарных нелинейных грамматик:

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

Напрмер, AàBbC,

Aà BbcC, где A,B,C- нетерминальные символы, а b,c- терминальные символы.

Грамматики предшествий – это грамматики, правые части которых могут содержать два рядом стоящих терминальных символа.

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

Например, Aà BaaB, где А,В – нетерминальные символы, а – терминальный символ.

Односторонние линейные грамматики – это грамматики, правые части правил которых содержат терминальные символы, только с одной стороны от нетерминального символа.

Односторонние линейные грамматики подразделяются также на левосторонние и правосторонние.

Левосторонние грамматики имеют правила следующего вида: Aà xB, Aà x, а правосторонние, соответственно, правила вида: А-->Bx, A-->x. Здесь A,B – нетерминальные символы, а x – непустая цепочка терминальных символов.

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

Взаимосвязь рассмотренных классов порождающих грамматик можно представить в виде следующей схемы:

Таким образом, КС – грамматики представляют собой наиболее важный подкласс НС – грамматик. Это объясняется четырьмя основными причинами:

-КС- грамматики является основой определения почти всех известных языков программирования;

-Все действия системы синтаксического анализа для естественных языков основаны на КС- грамматиках;

-Это единственный тип грамматик, теория которых изучена и практически проверена;

-Все трансформационные грамматики построены на основе КС- грамматик.

Рассмотренные типы грамматик порождают НС – язык, КС – язык, линейный язык, А – язык, не считая языка, порождаемого самым общим типом грамматики неограниченными правилами вывода – грамматикой типа 0 .

Взаимосвязь между языками, порождаемыми рассмотренными типами грамматик будет следующей:

.

5.3. Однозначные и неоднозначные НС-грамматики

Довольно часто в живых языках могут быть предложения, совпадающие по написанию, но допускающие неоднозначную синтаксическую трактовку. Например «пальто испачкало окно».

Здесь не ясно, что является подлежащим, а что дополнением. В таких примерах существенным является не «статическое» написание, а «динамика» процесса грамматического вывода.

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

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

грамматике G=(VT, VH, S,P) c правилами j1®y1, j2®y2, … jk®yk поставим в соответствие грамматику G¢=(VT¢, VH¢, S¢,P¢), у которой VH¢= VH, S¢= S, VT¢= VT È {(_j1,(_j2…,(_jk)}, то есть для каждого правила ji®yi системы правил P к терминальному символу соответствию добавляется (_ji .

Система P¢ получается из системы P заменой некоторого правила ji®yi правилом ji®(_jiyi).

Очевидно, что каждому выводу цепочки Х в L(G) однозначно соответствует вывод цепочки Х¢ в L(G¢).

Эта цепочка Х¢ совпадает с Х, если в ней опустить все скобки.

Скобки, таким образом, сохраняют «динамику» вывода.

Пример.

G=({0,1},S, S, P)

P={S®0, S®S1S}

G¢=({0,1},S, S, P¢)

P¢={S®(_s0), S®(_sS1S)}

Цепочка 01010 языка L(G) может быть выведена различными способами:

S®S1S®01S®01S1S®0101S®01010

S®S1S®S10®S1S10®01S10®01010.

Им соответствует разные структурные описания, полученные в L(G¢):

(_s(_s0)1(_s(_s0)1(_s0)));

(_s(_s(_s0)1(_s0)1(_s0)).

Выводы цепочки Х в некотором языке L(G) называются существенно- различными, если структурные описания Х¢, соответствующие этим выводам, отличаются друг от друга.

Если задается конкретная грамматика G одного из типов и нужно установить, является ли она неоднозначной, то алгоритмическая разрешимость такой задачи устанавливается следующей теоремой.

Теорема 5.3.1.

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

Язык данного типа называется существенно-неоднозначным, если любая грамматика G этого типа, порождающая этот язык, неоднозначна, то есть если в заданном классе грамматик нельзя найти грамматику без неоднозначностей, эквивалентную заданной.

В противном случае язык L называется языком без неоднозначностей или однозначно выводимым.

Две следующие теоремы относятся к вопросу о существовании существенно-неоднозначных языков различных типов.

Теорема 5.3.2 Хомского и Миллера

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

Теорема5.3.3. Парика

Существуют существенно- неоднозначные бесконтекстные языки.

Для зыков типа 1 (контекстных) этот вопрос не решен.

Следующая теорема рассматривает алгоритмическую разрешимость распознавания существенной неоднозначности.

Теорема5.3.4. Гладкого

Не существует алгоритма для решения задачи о том, является ли заданный язык типа 2D существенно-неоднозначным.

Однако в некоторых случаях этот вопрос может быть решен.

5.2. Грамматики непосредственно составляющих

Грамматики непосредственно составляющих относятся к классу неукорачивающих грамматик.

Неукорачивающие грамматики – грамматики, у которых для любого правила вида: j à y справедливо соотношение |j| £ |y| .

Примером неукорачивающей грамматики может служить грамматика

G=(Vт, Vн,P,S),

где Vт={a, b};

Vн={S};

P={F1, F2, F3, F4};

F1: Sàaa F3: SàaSa,

F3: Sàbb F4: SàbSb.

Пусть дано слово bSb. В результате подстановки любого из четырех правил мы получим новое слово, длина которого не меньше длины исходного словаря: baab, bbbb, baSab, bbSbb.

Грамматики непосредственно составляющих (НС-грамматики) – грамматики с правилами вида:

jАyàjwy или Аàw,

где А – нетерминальный символ,

w - произвольная непустая цепочка.

Таким образом, в НС – грамматиках на каждом шаге вывода можно заменить только один символ.

Очевидно, что НС – грамматика является неукорачивающей.

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

Пусть в неукорачивающей грамматике имеет место правило вида:

ABàBA, где A и B – нетерминальные символы.

Такое правило может быть заменено четырьмя правилами НС – грамматики:

ABà1B;

1Bà12;

12àB2;

B2àBA,

где 1,2 – новые нетерминальные символы, которые не встречались ни в каких старых правилах.

Последовательное применение этих правил равносильно применению правила АВàВА, причем такая замена не может привести к появлению “лишних” выводов, поскольку символы 1 и 2 – новые.

Языки, порождаемые НС – грамматиками называются НС – языками.

По используемому контексту грамматики могут быть классифицированы следующим образом:

где А – нетерминальный символ,

j и w - цепочки в алфавите V = Vт ÚVн

Язык, порожденный левоконтекстной грамматикой G, будем называть левоконтекстным языком L(G); язык, порожденный правоконтекстной грамматикой G’, будем называть правоконтекстным языком L(G’).

По правилам использования контекста НС- грамматики могут иметь следующую классификацию:

где а Î V.

Для изучения свойств НС – грамматик рассмотрим маленький фрагмент грамматики русского языка, заданного следующими правилами:

F1: ;

F2: ;

F3: ;

F4: (маленький, шаловливый, красивый);

F5: (мяч, мальчик);

F6: (потерял, ударил, бросил);

F4 - F6 – группа правил, так как указывают некоторые возможности для символа П , С, Г.

Vт – {маленький, шаловливый, красивый, мяч, ударил, бросил}.

Vн – ,

- группа глагола,

- группа существительного,

Г – глагол, С – существительное, П – прилагательное, - предложение.

Начальный символ – понятие предложения.

Выводимые терминальные цепочки – правильные предложения данного языка.

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

Структурное дерево(C-маркер) – это помеченный граф (помеченные ребра и узлы), где узлам соответствуют грамматические типы или синтаксические единицы, а ребра различаются своим порядковым номером.

Каждый С – маркер содержит в виде меток при конечных узлах перечень слов, из которых составлено данное предложение.

В рассматриваемом предложении составляющими являются – “мяч”, “красивый мяч”, “уронил красивый мяч”, а “уронил красивый” – не является составляющей.

Каждая составляющая возводится к некоторому узлу дерева. Если этот узел, допустим, помечен С, то говорят, что составляющая принадлежит типу С.

Те составляющие, из которых конструкция непосредственно образована, являются непосредственными составляющими.

Например, и - непосредственные составляющие предложения. Для - это П и С, для - и и т. д.

Грамматика должна обеспечивать С – маркером каждое из бесконечного числа предложений.

Два С – маркера тождественны, если они имеют одинаковую структуру ветвей и одинаковые метки при соответствующих узлах.

Дерево С – маркера характеризуется определенным упорядочиванием ветвей слева направо в соответствии с порядком элементов в цепочке.

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

Синтаксический элемент называется рекурсивным элементом, если для некоторого фиксированного n найдется структурное дерево, цепь которого содержит этот символ как наименование узла более чем n раз.

Выделяются три вида рекурсивных элементов:

Элемент А- самовставленный, то есть подчиненное ему дерево содержит А во внутренней цепи.

Грамматика G = (VT, VH, S,P) называется грамматикой с самовставлением, если для некоторого AÎ VH существует вывод АÞjАy, где j и y - непустые слова в V.

4.Алгоритмически неразрешимые задачи

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

Таким образом, всякий алгоритм можно рассматривать как некоторое универсальное средство для решения целого класса задач.

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

Таким образом, задачи ( проблемы ) можно разделить на алгоритмически разрешимые алгоритмически неразрешимые.

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

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

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

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

Существуют самоприменимые и несамоприменимые алгоритмы. Примером самоприменимого алгоритма является так называемый тождественный алгоритм в любом алфавите А,содержащем две или более буквы.

Этот алгоритм применим к любому слову Р в алфавите А и перерабатывает любое входное слово в себя. Примером несамоприменимости алгоритма является так называемый нулевой алгоритм в любом конечном алфавите В.

Это алгоритм задается схемой, содержащей единственную подстановку

àу , где у- любая буква алфавита В.

По своему определению он не применим ни к одному входному слову, а значит и к своему изображению.

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

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

Пусть в машине Тьюринга МТ зафиксирована какая-нибудь конфигурация.

Возможны два случая:

машина применима к этой конфигурации, то есть после конечного числа тактов она завершает работу в заключительной конфигурации;

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

Предположим, что на информационной ленте (ИЛ) МТ изображен ее собственный шифр (то есть шифр таблицы соответствия и исходной конфигурации), записанной в алфавите машины.

Если МТ применима к такой конфигурации, то будем называть ее самоприменимой, в противном случае - несамоприменимой.

Проблема распознавания самоприменимости состоит здесь в следующем: по любому заданному шифру требуется установить, к какому классу относится машина, зашифрованная им - к классу самоприменимых или несамоприменимых?

Доказательство:

Предположим, что такая машина М существует. Тогда в М всякий самоприменимый шифр перерабатывается в некоторый символ С, несамоприменимый – в символ Н.

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

Итак, М1 применима ко всякому несамоприменимому шифру

( вырабатывает при этом символ Н) и не применима к самоприменимым шифрам. Однако, это приводит к противоречию.

Действительно:

Пусть М1 самоприменима, тогда она применима к своему шифру М1’ и перерабатывает его символ Н, но появление этого символа должно означать, что машина несамоприменима;

Пусть М1 несамоприменима, тогда она применима к М1’, что должно означать, что М1- самоприменима.

Полученные противоречия доказывают неразрешимость этой проблемы.

3. Формальные преобразования алгоритмов

3.1. Основные понятия. Эквивалентность алгоритмов

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

Напомним, что два алгоритма считаются эквивалентными, если они имеют одну и ту же область определения и реализуемые ими функции совпадают, а системы правил различны.

Можно определить сильную и слабую эквивалентность алгоритмов.

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

Два алгоритма будем называть слабо эквивалентными, если они имеют одну и ту же область определения и результаты переработки слов из этой области совпадают.

На формальном уровне понятие эквивалентности двух алгоритмов U1 и U2 будем определять следующим образом:

• для каждого алгоритма вводится понятие «входа» и «выхода»;

• для каждого входа, который имеет смысл для данного алгоритма, выполнение алгоритма может приводить к некоторому выходу.

Пусть Х1 и Х2 - входы алгоритмов U1 и U2 соответственно.

Алгоритмы U1 и U2 считаются эквивалентными, если из условия Х1=Х2 следует, что если алгоритм U1 имеет выход У1, то и другой алгоритм U2 имеет выход У2=У1.

На практике большое значение имеет определение эквивалентности с точностью до изоморфизма.

Слово «изоморфизм» происходит от греческих слов: «изо» - равный, одинаковый и «морфо» - форма.

Изоморфизм – это взаимно однозначное соответствие между двумя множествами каких-либо объектов.

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

В этом случае между некоторыми входами Х1 алгоритма U1 и входами X2 алгоритма U2 конструктивно задается некоторый изоморфизм i (в данном случае понимаемый как однозначное соответствие).

Аналогично задается некоторый изоморфизм j между выходами Y1 и Y2 алгоритма U1 и U2 соответственно.

Эквивалентность теперь будет определяться стандартным образом:

-алгоритмы U1 и U2 считаются эквивалентными, если из условия Х1ⁱ~ Х2 следует, что если хотя бы один алгоритм имеет выход Y1, то другой алгоритм имеет выход Y2, причем Y1^j~ Y2.

Разные виды эквивалентности отличаются тем, как определяются «входы» и «выходы» алгоритма, а также тем, как выбираются изоморфизмы i и j. Между различными видами эквивалентности можно ввести частичное отношение порядка, выражающиеся словами «сильнее» и «слабее».

Будем считать, что отношение эквивалентности Э1 слабее отношения эквивалентности Э2, если любые алгоритмы U1 и U2, эквивалентные в смысле Э2, эквивалентны и в смысле Э1, и в то же время есть хотя бы одна пара алгоритмов U1 и U2, таких, что U1 и U2 эквивалентны в смысле Э1 и не эквивалентны в смысле Э2.

Очевидно, чем слабее отношение эквивалентности, тем шире класс алгоритмов, эквивалентных согласно этому отношению.

С одной стороны такое расширение классов рассматриваемых алгоритмов – хорошо, однако, при слишком слабом определении эквивалентности алгоритмов проблема распознавания эквивалентности алгоритмов может оказаться неразрешимой.

С другой стороны, слишком сильное определение эквивалентности чрезмерно сужает классы эквивалентных алгоритмов.

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

На степень широты понятия эквивалентности наиболее существенно влияет выбор определения «выхода» алгоритма.

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

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

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

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

Исчерпывающую информацию о том, как происходило выполнение алгоритма, можно получить, рассматривая в качестве выхода алгоритма всю последовательность выполнявшихся операторов.

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

Целесообразно рассматривать нечто такое, что по количеству информации было бы чем-то средним между записью алгоритма и значением результативного переменного по окончании выполнения алгоритма. С этой точки зрения будем рассматривать в качестве выхода

S-представления тех переменных, значения которых нас интересуют в качестве результатов выполнения алгоритма.

В этом случае два алгоритма эквивалентны, если соответствующие переменные при совпадающих входах вычисляются по одинаковым формулам.

S – представление переменного есть явное выражение формулы, по которым вычислялось результирующее значение переменного для заданных исходных значений исходных значений функциональных переменных.

В программировании важную роль играют именно такие преобразования алгоритмов, которые оставляют расчетные формулы (S - представления) неизменными.

Такие приемы программирования, как: разбиение задачи на подзадачи;-расчленение формул; выделение промежуточных результатов; преобразование логических операторов и т.п. приводят к таким преобразованиям алгоритмов, которые сохраняют S-представления результативных переменных.

Для определения эквивалентности операторных алгоритмов рассмотрим два алгоритма - U1 и U2 из некоторого класса операторных алгоритмов.

Для каждого из алгоритмов выделим те переменные, которые нас интересуют в качестве результатов выполнения этих алгоритмов. Выделенные переменные могут быть различными у алгоритма U1 и алгоритма U2 , но число их должно быть одинаковым и между ними должно быть установлено взаимно однозначное соответствие. То же самое относится к функциональным переменным алгоритмов U1 и U2 и к параметрам этих алгоритмов, которые могут входить в S – представление.

Обозначим функциональные переменные, параметры и выделенные в качестве результатов переменные алгоритма U1 как:

X1,……,Xs , P1,…Pr,Y1,…Yn соответственно.

Соответствующие им переменные, играющие аналогичную роль в U2:

1,…s, 1,…r, 1,…n

Алгоритмы U1 и U2 эквивалентны по отношению к выделенным переменным Y1,…Yn и 1,…n, если для любого набора исходных данных 1,…s, имеет место следующее утверждение:

если какой-либо из этих алгоритмов, например, U1 имеет значение для исходных данных 1,…s и S – представления выделенных переменных имеет вид: T1(Xi11,…Xi1m1,Pj11,…Pj1l1)àY1;

T2(Xi21,…Xi2m2,Pj21,…Pj2l2)àY2;

……………………………………

Tn(Xin1,…Xinmn,Pjn1,…Pj1ln)àYn;

то другой алгоритм U2 также имеет значение для исходных данных 1,…s и S-представления выделенных переменных имеют вид:

T1(i11,… i1m1, j11,… j1l1)à 1;

T2(i21,… i2m2, j21,… j2l2)à 2;

…………………………….

Tn(in1,… inmn, jn1,… jnln)à n;

Можно также определить эквивалентность между двумя алгоритмами U1 и U2 из разных классов U1(j1,j1) и U2(j2,j2) .

Соответствия между функциональными переменными, параметрами и выделенными переменными устанавливается так же, как было показано выше. Но может оказаться, что список операций j1 и j2, а также значения функциональных переменных не совпадают буквально.

В этом случае между операциями из списков j1 и j2, а также между возможными значениями функциональных переменных из множеств j1 и j2, необходимо дополнительно задать определенные изоморфизмы и считать алгоритмы U1 и U2 эквивалентными в том случае, если изоморфные наборы исходных данных приводят к S-представлениям, совпадающим с точностью до изоморфизма образующих их операций.

Следует отметить, что если вводится понятие эквивалентности для алгоритмов из разных классов, то может оказаться, что алгоритмы, эквивалентные в смысле S-представления, будут неэквивалентны в смысле совпадения значений выделенных переменных. Это может произойти в том случае, если изоморфные операции не будут совпадать функционально. Например, в одном случае арифметические действия выполняются в двоичной системе, а в другом - в десятичной.