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

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

P1: x := y+1; z:= 1; если x < z то y := z иначе y:=x конец

P2: x := y+1; z:= x +1; если x < z то y := z иначе y:=x конец

P3: x := y+1; z:= x +1; пока u < z делай y := z; u := u+1 все

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

P1: x := y+1; z:= x + 1; если x +1 < z то y := z иначе y:=x конец

P2: x := y+1; z:= x +1; если x = z то y := z иначе y:=x конец

P3: x := y+1; u:= z +1; пока u = z +1 делай y := z; u := u+1 все

Пусть задана линейная программа P со входными переменными X1, X2, X3:

Y = ¬X1;

Z = ¬X2;

U = ¬X3;

V = X1 ∧ X2;

Z = Y ∧ Z;

W= Y ∧ X2;

Z = Z ∧ W ;

V = V ∧ U ;

Z = Z ∨ V.

Постройте логическую схему S_P со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?

Пусть задана линейная программа P со входными переменными X1, X2, X3:

Y = X1 ∨ X2;

Z = X1 ∨ X3;

U = ¬X3;

Y = Y ∧ Z;

W = X2 ∨ X3;

U = X2 ∨ U;

Z = W ∨ Y ;

Z = U ∧ Y.

Постройте логическую схему S_P со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?

Пусть задана линейная программа P со входными переменными X1, X2, X3:

Y = ¬X1;

Z = ¬X2;

U = ¬X3;

Y = Y ∧ X2;

W = X2 ∧ X3;

Y = Y ∧ U;

Y = W ∨ Y ;

Z = Z ∨ Y.

Постройте логическую схему S_P со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?

В доказательстве теоремы 20.2 для построения м.Т M_П, моделирующей работу структурированной программы П с переменными x₁, … , x_m, используются м.Т. M^ij (1 ≤ i, j ≤ m), которые реализуют присваивание x_i := x_j, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M⁴³, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M⁴³ ?(В текстах программ a,b,c,d – это произвольные символы из алфавита{∧, |})

P1: q <a, b, |, d > → q < a, b , |, | > П , s < a, ,b | , | > → s < a, b, | , | > Л , q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П ,

P3: : q <a, b, |, d > → q < a, b , |, | > П , s < a, ,b | , | > → s < a, b, | , | > Л , q <a, b, ∧, | > → q < a, b, ∧, ∧ > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л ,

В доказательстве теоремы 20.2 для построения м.Т M_П, моделирующей работу структурированной программы П с переменными x₁, … , x_m, используются м.Т. M^ij (1 ≤ i, j ≤ m), которые реализуют присваивание x_i := x_j, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=2, j=4. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M²⁴, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M²⁴ ?(В текстах программ a,b,c,d – это произвольные символы из алфавита{∧, |})

P1: q <a, b, c, |> → q <a, | , c, | > П , s <a, | , c, | > → s <a, | , c, | > Л , q <a, |, c, ∧> → q <a, ∧ , c, ∧> П , s <∧, ∧, ∧, ∧> → p <∧, ∧ , ∧, ∧> П. q <a, ∧, c, ∧> → s <a, ∧ , c, ∧> Л ,

P2: q <a, |, c, d> → q <a, | , c, | > П , s <a, | , c, | > → s <a, | , c, | > Л , q <a, ∧, c, |> → q <a, ∧ , c, ∧> П , s <a, ∧, c, ∧> → p <a, ∧ , c, ∧> П. q <a, ∧, c, ∧> → s <a, ∧ , c, ∧> Л ,

P3: q <a, b, c, |> → q <a, | , c, | > П , s <a, | , c, | > → s <a, | , c, | > Л , q <a, b, c, ∧> → s <a, ∧ , c, ∧> Л , s <a, ∧, c, ∧> → p <a, ∧ , c, ∧> П.

Пусть машина Тьюринга M построена из простых машин Тьюринга Коп_a , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин

Выб_in – выбирает i-ый аргумент из n аргументов: x₁*…*x_i*…*x_n ⇐ x_i ,

Больше_ij - выдает 0, если в аргументе вида |^x1 *…*|^xi *…*|^xj *…*|^xn i-ый аргумент xi больше j-ого аргумента xj , иначе выдает 1,

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

M =  Коп_# ; par_#( par_* (Коп_*, Пуст ); Зам(*, |), Пуст );if  Больше₂₁  then par_#(  Пуст, Сум  ) else  par_#(  Пуст, Умн ) endif;Зам(#, *); Выб_33.

Какие результаты она получит на входных данных вида |^x1 * |^x2при x₁= 2, x₂= 7 и при x₁= 3, x₂= 5, соответственно?

Пусть машина Тьюринга M построена из простых машин Тьюринга Коп_a , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин

Выб_in – выбирает i-ый аргумент из n аргументов: x₁*…*x_i*…*x_n ⇐ x_i ,

Больше_ij - выдает 0, если в аргументе вида |^x1 *…*|^xi *…*|^xj *…*|^xn i-ый аргумент xi больше j-ого аргумента xj , иначе выдает 1,

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

M =  Коп_# ; par_#( par_* (Коп_*, Пуст ); Зам(*, |), Пуст );if  Больше₂₁  then par_#(  Пуст, Умн ) else  par_#(  Пуст, Сум ) endif;Зам(#, *); Выб_33.

Какие результаты она получит на входных данных вида |^x1 * |^x2при x₁= 4, x₂= 8 и при x₁= 1, x₂= 5, соответственно?

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

(a) если x < y то P1 иначе P2 конец,

(b) если x = y то P1 иначе P2 конец.,

(c) x := 0.

Введение в схемы, автоматы и алгоритмы