Дудаков С.М. Математическое введение в информатику

Подождите немного. Документ загружается.

4.3. Построение программ с метками 91

(Π)

. Определим

∼

(

, если λ

6∼ β,

α, если λ

∼ β.

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



, µ



j=0

является последовательностью расширенных состояний при работе Π на

σ. Используем индукцию по длине последовательности.

Базис индукции.

i = 0. Что σ

является начальным состоянием — очевидно. С метками

возможны две ситуации:

 1. λ

6∼ β и µ

= λ

. Так как λ

= Start



(Π)



, то µ

∼ λ

должна

быть и начальной меткой программы Π, потому что мы заменяем

только метку α на β.

 2. λ

∼ β. Тогда µ

∼ α, потому что метки β в программе Π отсут-

ствуют, они могут появиться в (Π)

только в результате замены.

Значит, Start (Π) ∼ α ∼ µ

Это доказывает базис утверждения.

Шаг индукции.

Пусть для i доказано, что последовательность расширенных состояний



, µ



j=0

является правильной и i < m. Рассмотрим i + 1. Возможны

следующие варианты:

 1. В программе (Π)

есть оператор вида

x = e; λ

i+1

Тогда в программе Π есть оператор

x = e; µ

i+1

отличается от σ

только тем, что σ

i+1

x = σ

(e). Это относится

и к (Π)

, и к Π. Следующей меткой для Π должна быть µ

i+1

. Значит,



i+1

, µ

i+1



— очередной элемент.

 2. В программе (Π)

есть оператор

if T then λ

i+1

else δ

и σ

|= T . Тогда в программе Π есть оператор

if T then µ

i+1

else δ

92 Глава 4. Программы с метками

Поэтому следующим элементом последовательности



, µ



будет



i+1

, µ

i+1



, где σ

i+1

= σ

 3. В программе (Π)

есть оператор

if T then δ else λ

i+1

и σ

6|= T . Тогда в программе Π есть оператор

if T then δ

else µ

i+1

Следовательно, за элементом



, µ



должен идти



i+1

, µ

i+1



, где

i+1

= σ

Рассмотрим µ

. Если в Π существует метка оператора µ

, то в про-

грамме (Π)

должна быть метка оператора λ

. Но последнее не выполня-

ется, так как λ

— заключительная метка. Значит, µ

является заключи-

тельной меткой программы Π. Таким образом, последовательность рас-

ширенных состояний



, µ



заканчивается элементом (σ

, µ

). То есть

Π (σ) определено и

Π (σ) = σ

= (Π)

(σ) .

Это доказывает наше утверждение.

Доказать утверждение в обратную сторону легко, если заметить, что

Π ∼



(Π)



и при этом метка α не встречается в программе (Π)

Согласно только что доказанному, из этого следует: если



(Π)



(σ)

определено, то (Π)

(σ) определено и



(Π)



(σ) = (Π)

(σ). А так как

Π ∼



(Π)



, то это и означает следование в обратную сторону.

Определение 4.6. (Эффективное построение) Мы скажем, что

по объекту A из некоторого класса можно эффективно построить объ-

ект B, если сущ ествует алгоритм, который выполняет такое постро-

ение для любого объекта A из этого класса.

Пример 4.5. Например, замена b ∼ (a)

— может быть эффективно

построена, потому что существует алгоритм, выполняющий такую

замену для любого слова a. В общих словах алгоритм замены следу-

ющий: идти по слову a и копировать все символы в слово b, кроме

символа x, вместо которого копируется y.

4.3. Построение программ с метками 93

Замечание 4.2. Не всякое построение эффективно. Например, для

всякого алгоритма A существует алгоритм M

, который имеет ми-

нимальную длину среди всех эквивалентных A алгоритмов. Однако по-

строение M

по A неэффективно. Не существует алгоритма, который

выполнял бы это построение для любого алгоритма A.

Теорема 4.1. (О построении программы с метками) По всякой

структурной программе Π

можно эффективно построить программу

с метками Π

такую, что Π

(σ) = Π

(σ) для любого состояния σ.

Доказательство. Докажем теорему индукцией по построению Π

Базис индукции.

Пусть

∼ x = e;

где x — переменная, e — выражение. Возьмем

∼ 1 x = e; 2.

Очевидно, что для всякого состояния σ имеет место Π

(σ) = Π

(σ).

Шаг индукции.

Возможны четыре варианта.

 1. Π

∼ Π

. По индукции для Π

и для Π

существуют програм-

мы Π

и Π

. Выберем для каждой метки α из программы Π

метку

ˆα, которая не встречалась бы ни в Π

ни в Π

. Построим

, заменив

в Π

все метки α на ˆα. Согласно лемме о замене метки Π

(τ) =

(τ)

для всякого состояния τ. Пусть γ — заключительная метка Π

, а δ —

начальная метка

. Пусть

∼





. Согласно лемме о замене мет-

ки Π

(σ) =

(σ) для всякого состояния σ. Построим Π

∼

Докажем, что Π

— искомая программа.

Пусть Π

(σ) определено. Тогда Π

(σ) определено. Пусть Π

(σ) = τ.

Согласно индукционному предположению

(σ) = Π

(σ) = τ. Пусть

(τ) = ρ. Согласно индукционному предположению

(τ) = Π

(τ) =

ρ. Рассмотрим последовательность расширенных состояний для Π

(σ).

Так как

(σ) определено, то последовательность расширенных состоя-

ний



, λ



для

(σ) является конечной. П усть (σ

, λ

) — ее послед-

ний элемент. Тогда σ

= τ и λ

= δ, так как δ — заключительная метка

программы

. Заметим, что (σ

, λ

) = (τ, δ) является первым расши-

ренным состоянием для

(τ). Так как

(τ) определено, то эта после-

довательность должна быть конечной:



, λ



i=m

. Очевидно, что σ

= ρ.

94 Глава 4. Программы с метками

Рассмотрим последовательность



, λ



i=0

. Эта последовательность яв-

ляется последовательностью расширенных состояний для Π

(σ). Так

как заключительная метка программы Π

совпадает с заключительной

меткой программы

, то Π

(σ) = σ

= ρ. Итак, Π

(σ) = Π

(σ).

Пусть теперь Π

(σ) определено. Рассмотрим последовательность рас-

ширенных состояний



, λ



i=0

. Тогда метка λ

должна быть заключи-

тельной меткой программы Π

. Но единственной заключительной мет-

кой программы Π

является заключительная метка программы

. Но

тогда λ

n−1

должна быть меткой оператора программы

, потому что

сама заключительная метка программы

в программе

встречаться

не может, потому что единственная метка из

, которая встречается в

, — это δ. Но δ является начальной меткой

, то есть меткой операто-

ра. А заключительная метка не может являться меткой оператора. Итак,

метка λ

является меткой оператора программы

, а метка λ

n−1

— мет-

кой оператора

. Следовательно, в последовательности расширенных

состояний должен быть элемент (σ

, λ

) такой, что все λ

при i < m —

метки операторов программы

, а сама λ

— метка оператора програм-

мы

. Но единственной меткой, которая удовлетворяет этим условиям

является δ.

Итак, рассмотрим последовательность



, λ



i=0

. Тогда она является

последовательностью расширенных состояний для

(σ) и λ

= δ — за-

ключительная метка

. Значит,

(σ) = σ

. По индукционному пред-

положению

(σ) = Π

(σ) =

(σ) = σ

Теперь рассмотрим последовательность



, λ



i=m

. Тогда, она являет-

ся последовательностью расширенных состояний для

(σ

). Поэтому

(σ

) = σ

. По индукционному предположению

(σ

) = Π

(σ

) =

(σ

) = σ

Получаем, что

(σ) = Π



(σ)



= Π

(σ

) = σ

таким образом, Π

(σ) определено и Π

(σ) = Π

(σ).

4.3. Построение программ с метками 95

 2.

∼











if T then

else

end;

По индукционному предположению для Π

и для Π

существуют про-

граммы Π

и Π

. Построим

так же, как и в предыдущем случае.

Пусть γ — заключительная метка программы Π

, а δ — заключитель-

ная метка

. Пусть

∼





. Пусть α — новая метка, которая не

встречается ни в

ни в

. Возьмем

∼











α if T then Start





else Start





Возможны два случая: либо σ |= T , либо σ 6|= T . Рассмотрим первый

случай.

Пусть Π

(σ) определено. По индукционному предположению,

(σ)

определено и

(σ) = Π

(σ) = τ . Значит, существует последователь-

ность расширенных состояний



, λ



i=0

, для которой σ

= σ, λ

Start





, σ

= τ и λ

= δ. Рассмотрим последовательность расширен-

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

ширенного состояния (σ, α): (σ, α) ,



, λ



i=0

. Легко показать, что это —

последовательность расширенных состояний для Π

(σ). Кроме того, δ —

заключительная метка Π

, поэтому Π

(σ) = σ

= τ = Π

(σ).

Пусть теперь Π

(σ) определено. Следовательно, последовательность

расширенных состояний



, λ



для Π

(σ) является конечной. Пред-

положим, она содержит n + 1 элемент. Очевидно, что λ

= Start





Последовательность



, λ



i=1

является последовательностью расширен-

ных состояний для

(σ), так как метки операторов

не встре-

чаются. Тогда последовательность



, λ



n−1

i=1



, γ



является последовательностью расширенных состояний для Π

(σ). По

индукционному предположению Π

(σ) определено и Π

(σ) = σ

. То

96 Глава 4. Программы с метками

есть

(σ) = σ

= Π

(σ) .

Второй случай, когда σ 6|= T рассматривается аналогично, только вме-

сто Π

, Π

рассматриваются Π

, Π

 3. Для неполного ветвления построение аналогично.

 4. Пусть

∼







while T do

end;

и для Π

существует программа с метками Π

. П усть β — начальная

метка Π

, γ — заключительная, а α — новая метка. Возьмем

∼



γ if T then β else α

Пусть Π

(σ) определено. Это означает, что существует последова-

тельность состояний





i=0

такая, что

= σ, σ

i+1

= Π





, σ

|= T ⇐⇒ i < n.

Рассмотрим последовательность расширенных состояний



, λ



для

(σ). Пусть j

— i-ый элемент, для которого λ

= γ. В частности,

= 0, так как λ

= γ. Индукцией по i докажем, что σ

= σ

Базис индукции.

i = 0. Тогда j

= 0 и σ

= σ

= σ = σ

Шаг индукции.

Пусть доказано, что σ

= σ

и i < n. Это означает, что σ

|= T и

|= T . Это означает, что вслед за расширенным состоянием



, γ



должно идти расширенное состояние



, β



. Это является начальным

расширенным состоянием для Π





. Из этого следует, что





= Π





= Π





= σ

i+1

Это означает, что последовательность расширенных состояний для





является конечной, и ее последним элементом является



i+1

, γ



. Заметим, что в этой последовательности метка γ встречается

только один раз в конце.

4.3. Построение программ с метками 97

Следовательно, в последовательности расширенных состояний для

(σ) после



, β



должно встретиться состояние



i+1

, γ



и это —

первое место после j

, где меткой является γ. Очевидно, что j

i+1

— но-

мер этого расширенного состояния, и σ

i+1

= σ

i+1

Итак, мы доказали, что σ

= σ

. Значит,

|= T ⇐⇒ σ

|= T ⇐⇒ i < n.

То есть, σ

6|= T . Значит, после расширенного состояния



, γ



будет

идти



, α



. Так как α является заключительной меткой, то Π

(σ) =

= σ

= Π

(σ).

Пусть теперь Π

(σ) определено. Тогда последовательность расширен-

ных состояний



, λ



является конечной. Пусть (σ

, λ

) — последний

элемент. Пусть j

— i-ый элемент, в котором метка — γ. Очевидно, что

= 0. Кроме того, λ

n−1

= γ, потому что метка α встречается в Π

только в одном месте. Пусть n − 1 = j

для некоторого m. Кроме того,

|= T тогда и только тогда, когда i < m.

Рассмотрим последовательность состояний σ

для Π

(σ). Аналогично

доказывается, что σ

= σ

. То есть,

|= T ⇐⇒ σ

|= T ⇐⇒ i < m.

Это означает, что

(σ) = σ

= σ

n−1

= σ

= Π

(σ) .

∗

Задача 4.6. Завершите доказательство корректности построения

для полного ветвления.

∗

Задача 4.7. Покажите, как построить программу с метками для

неполного ветвления, и докажите правильность построения.

Задача 4.8. Докажите, что если исходная структурная программа

была простой, то с методом, предложенным в теореме, будет постро-

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

Итак, мы научились по любой структурированной программе строить

эквивалентную ей программу с метками.

98 Глава 4. Программы с метками

Задача 4.9. Пользуясь методом, предложенным в теореме, построй-

те программы с метками по ранее построенным программам

1. для сложения чисел;

2. для вычитания чисел;

3. для умножения чисел;

4. для определения простоты числа.

4.4 Построение структурированных программ

В этом параграфе мы решаем обратную задачу — по программе с мет-

ками построим эквивалентную структурированную программу.

Теорема 4.2. (Структуризация) По всякой программе с метками

можно эффективно построить структурную программу Π

та-

кую, что Var





⊆ Var





(σ)  Var





= Π

(σ)  Var





для любого состояния σ программы Π

. Программу Π

можно выбрать

таким образом, чтобы она содержала только один оператор цикла.

Доказательство. Итак, пусть дана программа с метками Π

. Без

ограничения общности можно предполагать, что все ее метки являются

натуральными числами большими 0. Это означает, что программа Π

имеет следующий вид:

∼











Каждый из операторов o

имеет один из видов:

1. o

∼ α

= e

; β

2. o

∼ α

if T

then β

else γ

4.4. Построение структурированных программ 99

Пусть w и y — новые переменные, которые не встречаются в Π

. Для

каждого оператора o

одного из этих видов определим структурную про-

грамму ϕ (o

) следующим образом:

1. ϕ (o

) ∼











if w = succ (0) then

if y = α

then

= e

;

y = β

;

w = 0;

end;

2. ϕ (o

) ∼











if w = succ (0) then

if y = α

then

if T

then

y = β

;

else

y = γ

;

end;

w = 0;

end;

Здесь через n мы обозначаем следующее выражение:

n ∼ succ(succ(. . . succ(

| {z }

n раз

0 ) . . . ))

| {z }

n раз

Очевидно, что σ (n) = n для любого состояния σ. Построим программу

следующим образом:

∼











y = α

;

w = 0;

while w = 0 do

w = succ (0) ;

ϕ (o

)

ϕ (o

)

ϕ (o

)











end;

100 Глава 4. Программы с метками

Докажем, что Π

(σ) определено тогда и только тогда, когда Π

(σ)

определено, для любого состояния σ и в этом случае

(σ)  Var





= Π

(σ)  Var





По определению семантики программ с метками мы должны рассмат-

ривать последовательность расширенных состояний



, λ



, для кото-

рой σ

= σ и λ

= α

Теперь рассмотрим Π

. Через σ

обозначим состояние, которое по-

лучается из σ применением первых двух операторов присваивания про-

граммы Π

= (y = α

; w = 0; ) (σ) .

Очевидно, что

y = α

; σ

w = 0; σ

 Var





= σ  Var





поскольку никакие переменные из программы Π

эти операторы не из-

меняют. Для оператора цикла мы должны строить последовательность

состояний





такую, что σ

= σ

и σ

i+1

= Π





Индукцией по i докажем следующее утверждение:

1. σ

y = λ

;

2. σ

w = 0, если метка λ

i−1

не является заключительной;

3. σ

 Var





= σ

 Var





Базис индукции.

Для i = 0 утверждение, очевидно, выполнено, так как σ

= σ

, а свой-

ства σ

мы описали выше.

Шаг индукции.

Пусть для i утверждение доказано. Тогда рассмотрим Π





= σ

i+1

По определению семантики следования имеем:

i+1

= Π





= ϕ (o

)



. . . ϕ (o

)



(w = succ (0) ; )





. . .



Пусть

= (w = succ (0) ; )





Тогда ρ

отличается от σ

только тем, что ρ

w = 1. Пусть λ

= α

Рассмотрим ϕ (o

)





при k < j

. Очевидно, что

|= w = succ (0) ,