Теория вычислительных процессов

В том случае, когда слова совпадают, МКА остановится в заключительном состоянии q01 (именно в этом состоянии поступит символ ?) и набор будет допущен. Если слова не совпадут хотя бы в одном символе, МКА перейдет в состояние q32, из которого не выйдет до появления символа ?, который и зафиксирует отсутствие совпадения слов, т.е. не допустит искаженный набор.

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

1.4.3 Двухголовочные автоматы

Рисунок 1.7. пометками нарисована одна дуга со всеми этими пометками.

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

Двухголовочный конечный автомат (ДКА) имеет одну ленту и две головки, которые могут независимо перемещаться вдоль ленты в одном направлении. Множество состояний Q разбито на два непересекающихся множества. В состояниях Q1 активна первая головка, а в состояниях Q2 - вторая.

Двухголовочный автомат можно рассматривать как такой двухленточный автомат, который работает с идентичными словами на обеих лентах.

Приведем пример ДКА, который проверяет равенство двух последовательно записанных слов в алфавите V = {0, 1}. Признаком окончания каждого из слов сделаем вспомогательный символ *, не входящий в V. Автомат должен допускать только слова вида

а * а *,

где а О V^*.

Мы возьмем

A = (V И {*}, Q₁ И Q₂, R, q₀¹, #, I),

Где Q₁ = {q₀¹, q₁¹, q₂¹, q₇¹} - множество состояний, в которых активна первая головка;

Q₁ = {q₃², q₄², q₅², q₆²} - множество состояний, в которых активна вторая головка;

R = { q₇¹} - множество, содержащее единственное заключительное состояние. Граф автомата показан на рисунке 1.7, на котором вместо многих «параллельных» дуг с разными

Находясь в состоянии g01, автомат передвигает первую головку к началу второго слова и, обнаружив его, переходит в состояние q11. Если конец ленты # встречается раньше символа *, автомат переходит в незаключительное состояние q62. Если же автомат приходит к состоянию q11, он считывает поочередно символы второго слова первой головкой (состояние q11), а символы первого слова -- второй головкой (состояния q32 и q52), сравнивая эти символы. Автомат возвращается каждый раз в состояние q11, если символы одинаковы. Если же обнаружится несовпадение символов или первая головка встречает конец слова раньше символа *, автомат уходит в состояние q62. Попав в это состояние, автомат не может выйти из него; перемещая вторую головку к концу слова на ленте, он достигает #, находясь в незаключительном состоянии, так что слово на ленте отвергается. Если первая головка достигнет конца второго слова, а вторая головка обнаружит, что первое слово тоже просмотрено до конца, то автомат перейдет в заключительное состояние q71. В противном случае автомат перейдет в состояние q62, отвергая слово.

Этот пример легко обобщить на случай произвольного алфавита V, увеличивая количество состояний множества Q.

Проблемы пустоты и эквивалентности.

Будем говорить, что ДКА моделирует работу машины Тьюринга над некоторым начальным словом, если автомат допускает единственное слово -- конечный протокол paботы машины над ним.

Лемма (Розенберг). Существует алгоритм, который для любой машины Тьюринга и для любого начального слова строит двухголовочный автомат, моделирующий ее работу над этим словом.

Теорема. Проблема пустоты ДКА не является частично разрешимой.

Теорема. Проблема эквивалентности ДКА не является частично разрешимой.

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

1.4.4 Двоичный двухголовочный автомат

Cтандартные схемы могут моделировать (в уточненном ниже смысле) двухголовочные автоматы, что позволяет свести проблему пустоты этих автоматов к проблеме пустоты схем. Такое моделирование можно осуществить более простым способом, если использовать специальный класс двухголовочных автоматов, а именно класс двоичных автоматов, работающих со словами над алфавитом {0, 1}. Следующая лемма устанавливает связь между классом всех двухголовочных автоматов и подклассом двоичных автоматов специального вида.

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

Лемма. Существует алгоритм преобразования двухголовочных автоматов в двоичные двухголовочные автоматы (ДДКА), сохраняющий пустоту автоматов (построенный двоичный автомат Аb пуст тогда и только тогда, когда пуст исходный автомат А).

Доказательство. Пусть ДКА А над алфавитом V = {a1, a2, ...an} имеет множество состояний QА={q1k, q2k, …, qkk}, где верхний индекс (k = 1, 2) определяет номер активной головки. Преобразование этого автомата в двоичный начнем с кодировки символов и слов из V* словами в алфавите {0, 1} по следующему правилу:

код (#) = 0;

код (a_i) = 11....10 (i = 1, …, n);

код (aa_i) = код (a) код (a_i).

Так как символ ? кодируется нулем, то любому непустому слову на ленте автомата А соответствует двоичное слово на ленте автомата Аb, оканчивающееся двумя нулями. Автомат останавливается, прочитав два нуля подряд (или 0, означающий пустое слово).

Автомат A преобразуется в двоичный автомат Ab так, как показано на графах рисунка 1.8. Каждый фрагмент графа А (рисунок 1.8, а) заменяется фрагментом (рисунок 1.8, б) для Аb.

После замены добавляются фрагменты (рисунок 1.8 в, г).

Множество состояний автомата Аb включает:

а) все старые состояния из QА;

б) для каждого старого состояния qjk n новых состояний, n - число символов алфавита V;

в) два новых состояния r11 и r21.

Заключительными состояниями автомата А являются заключительные состояния автомата Аb.

Вершины Sa (останов допускающий) и Sr (останов отвергающий) носят на графе вспомогательный характер в графе Аb. Они отмечают тот факт, что автомат прочитал два нуля подряд и остановился в заключительном состоянии (случай Sa) или в незаключительном состоянии (случай Sr).

Легко убедиться, что автомат Аь допускает двоичное слово р тогда и только тогда, когда оно является двоичным кодом слова из V*, допускаемого автоматом А. Таким образом, из пустоты автомата А следует пустота автомата Аь, и наоборот.

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

На рисунке 1.9, а приведен граф ДКА A допускающий только те слова в алфавите V = {a, b, c}, в которых символ a встречается не меньшее число раз, чем символы b и c, вместе взятые. Заключительное состояние R={q01}. На рисунке 1.9, б приведен граф ДДКА, построенный по автомату А (10 - код символа a, 110 - код b, 1110 - код c).

По заданному ДДКА возможно построить ССП и наоборот, что позволяет решить задачу разрешимости (не разрешимости) свойств ССП, так как эта задача для ДДКА решена.

1.4.5 Построение схемы, моделирующей автомат

Двоичное слово b1b2 … bn согласовано со свободной интерпретацией базиса B, если для любого i, 1Ј i Ј n, I(p) (`fⁱa') = b_i, где p - единственный предикатный символ базиса B.

Пример 1.3. Слово 101010100 согласовано с любой свободной интерпретацией I такой, что для всех i Ј 9 I(p) (`f<sup>i</sup>a') = 1 если i нечетно и меньше 9, и I(p) (`fⁱa') = 0, если i четно или равно 9. Свободная интерпретация I такая, что для всех i I(p) (`fia') = 0, согласована с любым словом, не содержащим 1.

Для того чтобы свести проблему пустоты ДДКА к проблеме пустоты стандартных схем покажем, что для любого двоичного автомата А можно построить схему S, которая моделирует автомат А в следующем смысле. Если на ленту автомата А подано произвольное двоичное слово а, то программа (S, I), где I -- любая свободная интерпретация базиса В, согласованная с а, останавливается в том и только в том случае, когда автомат допускает слово а.

Лемма. ДДКА пуст в том и только в том случае, если пуста моделирующая его стандартная схема.

Лемма. Для любого ДДКА можно построить моделирующую его стандартную схему.

Теорема (Лакхэм - Парк - Патерсон). Проблема пустоты, стандартных схем не является частично разрешимой.

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

Теорема (Лакхэм - Парк - Патерсон). Проблема тотальности стандартных схем частично разрешима.

Теорема (Патерсон). Проблема свободы, стандартных схем не является частично разрешимой.

1.5 Рекурсивные схемы

1.5.1 Рекурсивное программирование

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

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

Примером рекурсивно определяемой функции является факториальная функция FACT: Nat > Nat:

FACT(х) = 1,если х = 0, FACT(х) = х ґ FACT(х -- 1), если х > 0.

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

FACT(a),

FACT(х) = if х = 0 then 1 else х ґ FACT(х - 1),

где а -- некоторое целое неотрицательное число.

Выполнение этой программы для некоторого значения а (пусть а = 4) может быть осуществлено следующим образом. В обе части рекурсивного определения вместо х подставляется 4, после чего вычисляется правая часть определения. Вычисление правой части начинается с вычисления логического выражения. Если его значение 1 (истина), то вычисляется левое функциональное выражение (стоящее после то), а если его значение 0 (ложь) -- вычисляется правое выражение (стоящее после else). Вычисление функционального выражения сводится к его упрощению, т. е. выполнению всех возможных вычислений. Если в упрощенном выражения остается вхождение символа определяемой функции FACT, то осуществляется переход к новому шагу выполнения программы. На этом шаге вхождение FACT(m), где m -- значение внутри скобок после упрощения, заменяется левым (т = 0) или правым (m > 0) функциональным выражением, в котором все вхождения х заменены на m. Упрощения продолжаются до тех пор, пока не будет получено выражение, не содержащее FACT (в нашем случае это выражение -- число).

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

1.5.2 Определение рекурсивной схемы

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

Множества переменных и предикатных символов ничем не отличаются от ССП. Множество специальных символов - другое, а именно: {if, то, else, (, ), ,}. Отличие множества функциональных символов состоит в том, что оно разбито на два непересекающиеся подмножества: множество базовых функциональных символов и множество определяемых функциональных символов (обозначаются для отличия прописными буквами, например, F(1),G(2), и т.д.).

В базисе РС нет множества операторов, вместо него - множество логических выражений и множество термов.

Простые термы определяются так же, как термы-выражения в СПП. Среди простых термов выделим базовые термы, которые не содержат определяемых функциональных символов, а также вызовы-термы вида F⁽ⁿ⁾(t₁,t₂,…t_n), где t₁,t₂,…t _n n - простые термы, F(n) - определяемый функциональный символ.

Логическое выражение - слово вида

p⁽ⁿ⁾(t₁,t₂,…t_n),

где p(n) - предикатный символ, t₁,t₂,…t_n - базовые термы.

Терм - это простой терм, или условный терм, т.е. слово вида if p then t₁ else t₂,

где p - логическое выражение, t₁, t₂ - простые термы, называемые левой и соответственно правой альтернативой.

Примеры термов:

f(x, g(x, y)); h(h(a)) - базовые термы;

f(F(x), g(x, F(y))); H(H(a)) - простые термы;

F(x); H(H(a)) - вызовы;

if p(x, y) then h(h(a)) else F(x) - условный терм.

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

if pxy then hha else Fx - условный терм.

Расширим в базисе В множество специальных символов символом "=".

Рекурсивным уравнением, или определением функции F назовем слово вида

F⁽ⁿ⁾(x₁,x₂,…x_n) = t(x₁,x₂,…x_n),,

где t(x₁,x₂,…x_n) - терм, содержащий переменные, называемые формальными параметрами функции F.

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

Примеры РС:

RS1: F(x); F(x) = if p(x) then a else g(x, F(h(x))).

RS2: A(b, c); A(x, y) = if p(x) then f(x) else B(x, y);

B(x, y) = if p(y) then A(g(x), a) else C(x, y);

C(x, y) = A(g(x), A(x, g(y))).

RS3: F(x); F(x) = if p(x) then x else f(F(g(x)), F(h(x))).

Пара (RS, I), где RS - PC в базисе В, а I - интерпретация этого базиса, называется рекурсивной программой. При этом заметим, что определяемые функциональные символы не интерпретируются.

Протоколы выполнения программы (RS1, I1) и (RS1, I2), где I1 и I2 - интерпретации из п. 1.2.3 (рисунок 1.2, б, в), выглядят следующим образом:

№ п/п	Значение терма для (RS1, I1)	Значение термадля (RS1, I2)
1 2 3 4 5 6	F(4) 4*F(3) 4*(3*F(2)) 4*(3*(2*F(1))) 4*(3*(2*(1*F(0)))) 4*(3*(2*(1*1)))=24	F(a,b,c) CONSCAR(abc, F(b,c)) CONSCAR(abc, CONSCAR(bc, F(c))) CONSCAR(abc, CONSCAR(bc, CONSCAR(c, F(?)))) CONSCAR(abc, CONSCAR(bc, CONSCAR(c, ?)))=abc

1.6 Трансляция схем программ

1.6.1 О сравнении класс сов схем

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

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

Схема S1 из класса W и схема S2 из класса W' функционально эквивалентны, если для любой интерпретации I согласованных базисов классов W и W' программы (S1, I), (S2, I) или обе зацикливаются, или обе останавливаются с одним и тем же результатом.

Говорят, что класс схем W мощнее класса схем W', или класс W' транслируем в класс W, если для любой схемы из W' существует эквивалентная ей схема в классе W. Классы W и W' равномощны, если W' мощнее W и W мощнее W'.

Доказано, что класс ССП транслируем в класс РС и класс РС не транслируем в класс ССП.

Рассмотренные примеры подтверждают первое утверждение для одинаковых интерпретаций I базисов. В этом случае РС RS1 эквивалентна ССП S1. При разных интерпретациях ССП и РС результаты будут различаться и следовательно программы (RS1, I1) и (S1, I2) будут различны.

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

Существуют некоторые классы РС, транслируемые в ССП. К ним относится класс линейных унарных РС, имеющих базис с единственной переменной x и одноместными функциональными и предикатными символами. Например, линейная унарная РС

RS4: F(x); F(x)=if p(x) then x else f(x, F(g(x))) транслируема в ССП.

1.6.2 Схемы с процедурами

Схемы с процедурами строятся в объединенном базисе классов стандартных и рекурсивных схем. Она состоит из двух частей - главной схемы и множества схем процедур. Главная схема - это стандартная схема, в которой имеются операторы присваивания специального вида x:= F(n)(y1,y2,…yn), называемые операторами вызова процедур. Схема процедуры состоит из заголовка и тела процедуры, разделенных символом равенства. Заголовок имеет тот же вид, что и левая часть рекурсивных уравнений. Тело процедуры - это стандартная схема того же вида, что и главная схема. Заключительный оператор тела процедуры всегда одноместен (stop(х)). Ниже приведен пример схемы с процедурами.

Главная схема	Множество схем процедур
(start(x), 1: z:=x, 2: u:=a, 3: x:=F(x, z, u), 4: u:=b, 5: z:=F(z, x, u) 6: stop(z))	F(y, v, w) = start, 1: if p(y) then 2 else 4, 2: y:=h(y), 3: v:=G(v, w) goto 1, 4: if q(w) then 5 else 6, 5: y:= v, 6: stop(y)) G(t, r) = (start, 1: if q(r) then 2 else 3, 2: t := f(t), 3: stop(t);

Доказано, что класс РС транслируем в класс схем с процедурами и наоборот.

1.7 Обогащенные и структурированные схемы

1.7.1 Классы обогащенных схем

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

Классы счетчиковых и магазинных схем образован добавлением в базис ССП счетного множества счетчиков и магазинов с их интерпретированными операторами.

Счетчик -- интерпретированная переменная, у которой областью значений является множество Nat; начальное значение счетчика равно 0.

Интерпретированные операторы имеют следующий вид:

c := c + 1 -- оператор прибавления единицы;

c := c - 1 -- оператор вычитания единицы;

c = 0 -- условный оператор проверки равенства счетчика нулю.

При значении счетчика равном 0 оператор вычитания единицы не изменяет его, оно остается равным 0.

К интерпретированным операторам может быть добавлен оператор пересылки значения счетчика с2 := с1, который может быть получен при помощи стандартных операторов.

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

Рисунок 1.10

Магазин -- неинтерпретированная переменная сложной структуры. В процессе выполнения интерпретированной схемы состояние магазина -- это конечный набор элементов (d1,d2,…,dn) из области интерпретации, где dn -- верхушка магазина.

Интерпретированные операторы имеют следующий вид:

М := x -- запись в магазин;

х := М -- выборка из магазина;

М = Ж -- условный оператор проверки пустоты магазина,

где М - магазин, х -- обычная переменная. Первый оператор меняет состояние (d1,d2,…,dn) магазина М на состояние

(d1,d2,…,dn+1),

где dn+1 -- значение переменной х. После выполнения этого оператора элемент dn+1 становится новой верхушкой магазина. Второй оператор присваивает переменной х значение, равное верхушке магазина, состояние которого меняется с

(d1,d2,…,dn-1,dn) на (d1,d2,…,dn-1),

при этом dn.1 становится новой верхушкой магазина. Если магазин М пуст, то применение второго оператора оставляет его пустым, а переменная х не меняет своего значения. Третий оператор-- предикат проверки магазина на пустоту; если магазин пуст, то значение предиката М = 0 равно 1, в противном случае -- 0.

Класс схем с массивами -- это расширение класса счетчиковых схем за счет добавления счетного множества массивов и операторов над ними.

Массив -- неинтерпретированная переменная сложной структуры. При выполнении интерпретированной схемы состояние массива -- бесконечная последовательность (d1,d2,…,di,…) элементов из области интерпретациии.

Интерпретированные операторы имеют следующий вид:

А[c]:= x -- запись в магазин;

х:= А[c] -- выборка из магазина,

где А -- массив, [c] -- целое число, равное текущему значению счетчика с.

На рисунке 1.10. приведены четыре схемы: стандартная (а), счетчиковая (б), магазинная (в) и схема с массивами (г). Все они эквивалентны друг другу и рекурсивной схеме:

F(x), F(x)=if p(x) then x else f(x, F(g(x))).

1.7.2 Трансляция обогащенных схем

Диаграмма на рисунке 1.11 дает полную информацию о возможности трансляции одного класса схем в другой, классы имеют следующие обозначения:

Y -- стандартные схемы;	Y(М) -- магазинные схемы;
Y(R) -- рекурсивные схемы;	Y(А) -- схемы с массивами;
Y(с) -- счетчиковые схемы;	Y(P) -- схемы с процедурами.

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

Диаграмма показывает, что классы Y(М) и Y(А) являются универсальными в том смысле, что схемы всех других классов транслируемы в них. В то же время, в класс Y не транслируются схемы ни одного другого класса. Следует отметить, что класс Y(с) достигает полной мощности при количестве счетчиков не менее 2, т.е. класс Y(с) с одним счетчиком равномощен классу Y.

1.7.3 Структурированные схемы

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

Класс cтруктурированных схем Y(S) определяется в том же (полном) базисе В, который был введен для ССП Y.

Различие между Y и Y(S) проявляется на уровне структур схем. Вместо специальных символов Y вводятся специальные символы: if , then, else, while, do, end. Вместо инструкций с метками вводятся три типа схемных оператора в базисе В: простой оператор, условный оператор и оператор цикла.

Простой оператор -- это начальный (заключительный) оператор и оператор присваивания.

Условный оператор -- это оператор вида

if p then s₁ else s₀ end,,

где ? -- логическое выражение, s₁ ,s₀ -- последовательности (может быть, пустые) схемных операторов, среди которых нет ни начального, ни заключительного.

Операторы цикла имеют вид

while p do s end или until p do s end

где p,s имеют тот же смысл, что и выше.

Ниже приведен пример эквивалентных схем Y и Y(S).

Стандартная схема программ Y	Структурированная схема программ Y(S)
start(х), 1: y := f(x), 2: if p(y) then 7 else 3, 3: y := f(y), 4: if p(y) then 5 else 7, 5: if p(x) then 6 else 7, 6: x := h(x) goto 5, 7: stop(х, y).	start(х), y := f(x), if p(y) then else y := f(y), if p(x) then while p(x) do x := h(x) end else end end, stop(х, y).

Доказано, что класс Y мощнее класса Y(S), т.е. схемы Y(S) транслируемы в Y, но не наоборот.

Усилить класс Y(S) можно за счет усложнения логических выражений в условных операторах и операторах цикла Y(SL), введением символов логических операций NOT, OR, AND и атомарных формул, которыми являются логические выражения в старом смысле, например:

NOT p(x) AND q(y,x);

p(g(x, t)) OR q(h(x), x).

В этом случае справедлива

Теорема (Ашкрофт - Манн) Класс стандартных схем Y транслируем в класс схем с логическими операциями Y(SL).

2. Семантическая теория программ

2.1 Описание смысла программ

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

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

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

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

2.1.1 Операционная семантика

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

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

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

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

Семантику конструкции for языка С можно описать в терминах следующих простых команд.

Пример 2.1. Оператор языка С Операционная семантика

for (expr1; expr2; ехргЗ){ exrp1

... loop: if expr2 = 0 goto out

} …

ехргЗ;

goto loop

out:

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

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

ident := var

ident := ident - 1

goto label

if var relop var goto label

Здесь relop-одни из операторов отношений из набора {= , <>, >, <, >=, <=}, ident - идентификатор, a var - идентификатор или константа. Все эти операторы просты и легки для понимания и реализации.

Незначительное обобщение приведенных выше трех операторов присваивания позволяет описывать более общие арифметические выражения и операторы присваивания. Например:

ident := var bin_op var

ident := un_op var

Здесь bin_op - бинарный арифметический оператор, a un_op - унарный оператор. Многочисленные арифметические типы данных и автоматическое преобразование типов, конечно, несколько усложняют это обобщение. Введение небольшого количества новых относительно простых команд позволит описывать семантику массивов, записей, указателей и подпрограмм.

Описание операционной семантики функций рассмотрим на примере системы равенств:

f1(x1, x2, ... , xk)= E1,

f2(x1, x2, ... , xk)= E2,

. . . . . . . . . . . . . (2.1)

fm(x1, x2, ... , xk)= Em,

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

Операционная семантика интерпретирует эти равенства как систему подстановок. Под подстановкой <s, E, ?> терма ? в выражение E вместо символа s (в частности, переменной) будем понимать переписывание выражения E с заменой каждого вхождения в него символа s на выражение ?. Каждое равенство fi(x1, x2, ... , xk)= Ei задает в параметрической форме множество правил подстановок:

< x₁, x₂, ... , x_k; f_i(t₁, t₂, ... , t_k) > E_i; t₁, t₂, ... , t_k>

где t₁, t₂, ... , t_k - конкретные аргументы (значения или определяющие их выражения) данной функции. Это правило допускает замену вхождения левой его части в какое-либо выражение на его правую часть.

Интерпретация системы равенств (2.1) для получения значений определяемых функций в рамках операционной семантики производится следующим образом. Пусть задан набор входных данных (аргументов) d1, d2, ... , dk. На первом шаге осуществляется подстановка этих данных в левые и правые части равенств с выполнением там, где это возможно, предопределенных операций и с выписыванием получаемых в результате этого равенств. На каждом следующем шаге просматриваются правые части полученных равенств. Если правая часть является каким-либо значением, то оно и является значением функции, указанной в левой части этого равенства. В противном случае правая часть является выражением, содержащим вхождения каких-либо определяемых функций с теми или иными наборами аргументов. Если для такого вхождения соответствующая функция с данным набором аргументов имеется в левой части какого-либо из полученных равенств, то либо вместо этого вхождения подставляется вычисленное значение правой части этого равенства, либо не производится никаких изменений. В том же случае, если эта функция с данным набором аргументов не является левой частью никакого из полученных равенств, то формируется (и дописывается к имеющимся) новое равенство. Оно получается из исходного равенства для данной функций подстановкой в него вместо параметров указанных аргументов этой функции. Такие шаги осуществляются до тех пор, пока все определяемые функции не будут иметь вычисленные значения.

Пример 2.2. Рассмотрим систему равенств, определяющую функцию FACT(n)=n!

FACT(0)=1,

FACT(n)=nґFACT(n-1)?.

Для вычисления значения FACT(3) осуществляются следующие 6 шагов.

1-й шаг: 2-й шаг: 3-й шаг:

FACT(0)=1, FACT(0)=1, FACT(0)=1,

FACT(3)=3ґFACT(2)?. FACT(3)=3ґFACT(2)?, FACT(3)=3ґFACT(2)?

FACT(2)=2ґFACT(1). FACT(2)=2ґFACT(1),

FACT(1)=1ґFACT(0).

4-й шаг: 5-й шаг: 6-й шаг:

FACT(0)=1, FACT(0)=1, FACT(0)=1,

FACT(3)=3ґFACT(2)?, FACT(3)=3ґFACT(2)?, FACT(3)=6,

FACT(2)=2ґFACT(1), FACT(2)=2, FACT(2)=2,

FACT(1)=1. FACT(1)=1. FACT(1)=1.

Первым и самым значительным использованием формальной операционной семантики было описание семантики языка PL/I. Эта абстрактная машина и правила трансляции языка PL/I были названы общим именем Vienna Definition Language (VDL) в честь города, в котором они были созданы корпорацией IBM.

Операционная семантика является эффективной до тех пор, пока описание языка остается простым и неформальным. К сожалению, описание VDL языка PL/I настолько сложно, что практическим целям оно фактически не служит.

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

2.1.2 Аксиоматическая семантика

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

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

Аксиоматическая семантика основана на математической логике. Будем называть предикат, помещенный в программу утверждением. Утверждение, непосредственно предшествующее оператору программы, описывает ограничения, наложенные на переменные в данном месте программы. Утверждение, следующее непосредственно за оператором программы, описывает новые ограничения на те же (а возможно, и другие) переменные после выполнения оператора.

Введем обозначение (триада Хоара)

{Q} S {R}, (2.2)

где Q, R - предикаты, S - программа (оператор или последовательность операторов). Обозначение определяет следующий смысл: «Если выполнение S началось в состоянии, удовлетворяющем Q, то имеется гарантия, что оно завершится через конечное время в состоянии, удовлетворяющем R».

Предикат Q называется предусловием или входным утверждением S, предикат R - постусловием или выходным утверждением. Следовательно, R определяет то, что нужно установить. Можно сказать, что R определяет спецификацию задачи. В предусловии Q нужно отражать тот факт, что входные переменные получили начальные значения.

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

Пример 2.3. Рассмотрим оператор присваивания для целочисленных переменных и постусловие:

sum := 2 * х + 1 {sum > 1}

Одним из возможных предусловий данного оператора может быть {х > 10}.

Слабейшими предусловиями называются наименьшие предусловия, обеспечивающие выполнение соответствующего постусловия. Например, для приведенного выше оператора и его постусловия предусловия {х > 10}, {х > 50} и {х > 1000} являются правильными. Слабейшим из всех предусловий в данном случае будет {х > 0}.

2.1.2.1 Преобразователь предикатов

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

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

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

Если S - некоторый оператор (последовательность операторов), R - желаемое постусловие, то соответствующее слабейшее предусловие будем обозначать wp(S, R).

Аббревиатура wp определяется начальными буквами английских слов weakest (слабейший) и precondition (предусловие). Предполагается, что известно, как работает оператор S (известна семантика S), если можно вывести для любого постусловия R соответствующее слабейшее предусловие wp(S, R).

Определение семантики оператора дается в виде правила, описывающего, как для любого заданного постусловия R можно вывести соответствующее слабейшее предусловие wp(S, R).

Для фиксированного оператора S такое правило, которое по заданному предикату R вырабатывает предикат wp(S,R), называется «преобразователем предикатов»: {wp(S, R)} S {R}.

Это значит, что описание семантики оператора S представимо с помощью преобразователя предикатов. Применительно к конкретным S и R часто бывает неважным точный вид wp(S,R), бывает достаточно более сильного условия Q, т.е. условия, для которого можно доказать, что утверждение Q => wp(S, R) справедливо для всех состояний. Значит, множество состояний, для которых Q - истина, является подмножеством того множества состояний, для которых wp(S, R) - истина. Возможность работать с предусловиями Q, не являющимися слабейшими, полезна, поскольку выводить wp(S, R) явно не всегда практично.

Сформулируем свойства (по Э. Дейкстра) wp(S, R).

Свойство 1. wp (S, F) = F для любого S. (Закон исключенного чуда).

Свойство 2. Закон монотонности. Для любого S и предикатов P и R таких, что P => R для всех состояний, справедливо для всех состояний wp(S, P) => wp(S, R).

Свойство 3. Дистрибутивность конъюнкции. Для любых S, P, R справедливо

wp(S, P) AND wp(S, R) = wp(S, P AND R).

Свойство 4. Дистрибутивность дизъюнкции. Для любых S, P, R справедливо

wp(S, P) OR wp(S, R) = wp(S, P OR R).

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

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

2.1.2.2 Аксиоматическое определение операторов языка программирования в терминах wp

Определим слабейшее предусловие для основных операторов: оператора присваивания, составного оператора, оператора выбора и оператора цикла.

Оператор присваивания имеет вид: x := E, где x - простая переменная, E - выражение (типы x и E совпадают).

Определим слабейшее предусловие оператора присваивания как

Q = wp(x := E, R),

где Q получается из R заменой каждого вхождения x на E, что обозначим

Q = RxЕ.

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

Составной оператор имеет вид: begin S1; S2; ... ; Sn end

Определим слабейшее предусловие для последовательности двух операторов:

wp(S1;S2, R) = wp(S1, wp(S2, R)).

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

Оператор выбора определим так: if B1 > S1 П B2 > S2 ... П Bn > Sn fi

Здесь n і 0, B₁, B₂, ..., B_n - логические выражения, называемые охранами, S1, S2, ..., Sn - операторы, пара Bi > Si называется охраняемой командой, П - разделитель, if и fi играют роль операторных скобок.

Выполняется оператор следующим образом.

Проверяются все Bi. Если одна из охран не определена, то происходит аварийное завершение. Далее, по крайней мере, одна из охран должна иметь значение истина, иначе выполнение завершается аварийно.

Выбирается одна из охраняемых команд Bi > Si, у которой значение Bi истина, и выполняется Si.

Определим слабейшее предусловие:

wp(if, R) = BB AND (B1 => wp(S1, R)) AND ... AND (Bn => wp(Sn, R)),

где BB = B1 OR B2 OR ... OR Bn.

Предполагается, что охраны являются всюду определенными функциями (значение их определено во всех состояниях).

Естественно определить wp(if, R) с помощью кванторов:

wp(if, R) = ($ i: 1 Ј i Ј n : Bi ) AND ("i: 1 Ј i Ј n : Bi => wp(Si, R))

Пример 2.4. Определить z = |x|.

С использованием оператора выбора

if x і 0 > z := x П x Ј 0 > z := -x fi.

К особенностям оператора выбора следует отнести, во-первых, тот факт, что он включает условный оператор (if... then..), альтернативный оператор (if… then... else...) и оператор выбора (case).

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

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

Оператор цикла. В обозначениях Э. Дейкстры цикл имеет вид: do B > S do.

Обозначим это соотношение через DO и представим его в следующем виде:

DO: do B1 > S1 П B2 > S2 ... П Bn > Sn od,

где n і 0, Bi > Si - охраняемые команды.

Выполняется оператор следующим образом. Пока возможно выбирается охрана Bi со значением истина, и выполняется соответствующий оператор Si. Как только все охраны будут иметь значение ложь, выполнение DO завершится.

Выбор охраны со значением истина и выполнение соответствующего оператора называется выполнением шага цикла. Если истинными являются несколько охран, то выбирается любая из них.

Следовательно, оператор DO эквивалентен оператору

do BB > if B2 > S1 П B2 > S2 ... П Bn > Sn fi od или do BB > IF od,

где BB - дизъюнкция охран, IF - оператор выбора.

Пример 2.5. Алгоритм Евклида.

Вариант 1.

задать (N, M);

if N > 0 AND M > 0 >n, m := N, M;

do n ? m > if n > m > n := n - m П m > n > m := m - n fi od;

выдать (n)

fi

Вариант 2.

задать (N, M);

if N > 0 AND M > 0 > n, m := N, M;

do n > m > n := n - m П m > n > m := m - n od;

выдать (n)

fi

Дадим формальное определение слабейшего предусловия для оператора цикла DO.

Пусть предикат H0(R) определяет множество состояний, в которых выполнение DO завершается за 0 шагов (в этом случае все охраны с самого начала ложны, после завершения R имеет значение истина):

H0(R) = NOT BB AND R

Другими словами, требуется, чтобы оператор цикла DO завершил работу, не производя выборки охраняемой команды, что гарантируется первым конъюнктивным членом предиката H0(R): NOT BB = T. При этом истинность R до выполнения DO является необходимым условием для истинности R после выполнения DO.

Определим предикат Hk(R) как множество состояний, в которых выполнение DO заканчивается за k шагов при значении R истина (Hk(R) будет определяться через Hk-1(R)):

Hk(R) = H0(R) OR wp(IF, Hk-1(R)), k > 0 > wp(DO, R) = (? k: k ? 0: Hk(R)).

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

Определение DO. Если предикаты Hk(R) задаются в виде

Hk(R) = NOT B AND R, k = 0

Hk(R) = wp(IF, Hk-1(R)), k > 0, > wp (DO,R)=(? k: k ? 0: Hk(R))

Основная теорема для оператора цикла. Пусть оператор выбора IF и предикат P таковы, что для всех состояний справедливо

(P AND BB) => wp(IF, R). (2.3)

Тогда для оператора цикла справедливо:

(P AND wp(DO, T)) => wp(DO, P AND NOT BB).

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

Поясним смысл теоремы. Условие (2.3) означает, что если предикат P первоначально истинен и одна из охраняемых команд выбирается для выполнения, то после ее выполнения P сохранит значение истинности. После завершения оператора, когда ни одна из охран не является истиной, будем иметь:

P AND NOT BB.

Работа завершится правильно, если условие wp(DO, T) справедливо и до выполнения DO. Так как любое состояние удовлетворяет T, то wp(DO,T) является слабейшим предусловием для начального состояния такого, что запуск оператора цикла DO приведет к правильно завершаемой работе.