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

Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?

Пусть задан недетерминированный конечный автомат M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={3, 5}, Φ> с программойΦ: 0 b → 1, 0 → 2, 1 → 2, 2 → 3, 2 a → 1, 3 a → 1, 3 b → 4, 4 a → 5, 5 → 3.Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?

Пусть структурированная программа

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

начинает работу в состоянии σ : σ(x) =0, σ(y) =3, σ(z) =5, σ(u) = 4, σ(v) =2В каком из следующих состояний σ1 она завершит свою работу?

Пусть функция F(x) задана примитивной рекурсиейR(1, h(y,z)), где h(y,z) = [2^z/z²]Чему равно значение F(5)?

Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ?
(a) если A ≤m B, то (N \A) ≤m (N \B) ,
(b) A ≤m C и B ≤m C для C= {2x | x ∈ A} ∪ {2x+1 | x ∈ B},
(c) сохраняет свойство неразрешимости: если A ≤m B и A - неразрешимо, то и B неразрешимо .

Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых есть по крайней мере две подряд идущие 1-цы ?

Пусть функция rm(x, y) = y mod x равна остатку от деления y на x ( rm(0,y)=y), а функция p(n) принимает значение 1, если число n простое, и равна 0 для составных n (p(0)=p(1)=0, p(2)=p(3)=1, …). Какое из следующих выражений определяет число dp(x) различных простых делителей числа x?

В конструкции для параллельной композиции машин Тьюринга на этапах 3 и 5 участвует служебная машина, назовем ее CHANGE, меняющая местами аргументы, точнее переводящая любую конфигурацию вида x * q y (x и y – слова в алфавите Σ, не содержащем символов ∧, * и # , q – начальное состояние) в конфигурациюy* q’ x (q' – заключительное состояние). Пусть Q={ q, s, p, r, q'}∪ {p^a | a ∈ Σ} – множество состояний CHANGE. Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для CHANGE ?(В текстах программ a – это произвольный символ из Σ, а b - это произвольный символ из Σ ∪ {, #} ).
P1: q b → q b П , q ∧ → s # Л, s b → s b Л, s ∧ → p ∧ П, p a → p^a ∧П, p → r ∧П, p^a b → p^a b П, p^a ∧ → s a Л, r a → r a П , r # → q’ * П.
P2: q a → q a П , q ∧ → s * Л, s b → s b Л, s ∧ → p ∧ П, p a → p^a ∧П, p * → r ∧П, p^a b → p^a b П, p^a ∧ → s a Л, r a → r a П , r→ q’ П.
P3: q a → q a П , q ∧ → s * Л, s b → s b Л, s ∧ → p ∧ П, p a → p^a ∧П, p * → q’ * П, p^a b → p^a b П, p^a ∧ → s a Л.

Пусть язык L в алфавите {a, b}, состоит из всех слов, которые начинаются на aa и содержат число символов a кратное 3, и пусть гоморфизм h: {0, 1,2}* → {a, b}* задан равенствами: h(0) = aaa, h(1) = ba, h(2) = ε Какие из следующих трех слов принадлежат прообразу h^-1(L) языка L при гомоморфизме h?
W1 = 21112, W2 = 20101012, W3 = 00211011

Пусть машина Тьюринга M имеет алфавит ленты Σ={ ∧, 0, 1}, алфавит состояний Q= {q, p, r, !}, начальное состояние q, заключительное состояние ! и программу Ф:
$\begin{array}{lll}q\ 0 \rightarrow q\ 0\ П & p\ 0 \rightarrow p\ 1\ Л & r\ 0 \rightarrow r\ 0\ Лq\ 1 \rightarrow q\ 1\ П & p\ 1 \rightarrow r\ 0\ Л & r\ 1 \rightarrow r\ 1\ Л q \wedge \rightarrow p \wedge Л & p \wedge \rightarrow ! \wedge П & r \wedge \rightarrow ! \wedge П\end{array}$
В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации q 1100 ?

Постройте минимальные УБДР для функцииf(x1, x2, x3, x4)= (x1 ∨ x2) + ( x3 ∨ x4)относительно двух упорядочений переменных:
a) x1 < x2 < x3 < x4 и
b) x1 < x3 < x2 < x4.
Определите сложности этих двух схем.

Пусть машина Тьюринга 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₁= 3, x₂= 6 и при x₁= 2, x₂= 6, соответственно?

Пусть П_× - это программа, которая вычисляет функцию Ф_× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x целую часть частного [ x/y] (пусть при y=0 результат равен 0)?

Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами?
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 все

Пусть задан конечный автомат - преобразователь A = <Σ_X ={0, 1} Σ_Y= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>,где
Какое входное слово автомат А перерабатывает в выходное слово ТАРАРА?

Пусть задан недетерминированный конечный автомат (без пустых переходов)M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программойΦ: q 0 → p, q 0 → s, q 1→ q, p 0 → q, p 0 → p, s 1 → q, s 1 → pКакие из следующих трех ДКА эквивалентны M?
M1 = < {0, 1}, {q, ps, pq, pqs}, q, F1={ ps, pq, pqs }, Φ1> с программой Φ1:q 0 → ps, q 1 → q, ps 0 → pq, ps 1 → pq, pq 0 → pqs, pq 1 → q, pqs 0 → pqs, pqs 1 → pq
M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F2={p, ps, pq, pqs }, Φ2> с программой Φ2:q 0 → ps, q 1 → q, p 0 → pq, p 1 → q, ps 0 → qs, ps 1 → pq, pq 0 → pqs, pq 1 → q, qs 0 → ps, qs 1 →q, pqs 0 → pqs, pqs 1 → pq, ∅ 0 →∅, ∅ 1 →∅
M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F3={ p, ps, pq, pqs }, Φ3> с программой Φ3:q 0 → ps, q 1 → q, p 0 → pq, p 1 → q, s 0 →∅, s 1 →pq, ps 0 → pq, ps 1 → pq, pq 0 → pqs, pq 1 → q, qs 0 → ps, qs 1 →q, pqs 0 → pqs, pqs 1 → pq, ∅ 0 →∅, ∅ 1 →∅

Три машины Тьюринга M_i = < Σ, Q !, P_i, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы:Какие из этих машин переводят любую начальную конфигурацию вида q aⁿ b в заключительную конфигурацию ! b a²ⁿ (n ≥ 0 )?

Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв b превосходит количество букв a не менее чем на 3. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?

Пусть задана логическая схема S=(V, E) :V= {a (X1), b(X2), c(X3), d(¬),e(¬), f(∨),g(∨),h(∨), i(∧), k(∧) } (после имени вершины в скобках указана ее метка - переменная или булева функция),E= { (a, d), (a, g), (b, e), (b, f), (b, g), (c, f), (d, h), (e, h), (f,k), (g,i), (h, i), (i, k) }.Какую булеву функцию реализует схема S=(V, E) в вершине k?(В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов X1, X2 и X3)

Чему равна глубина схемы S₃, реализующей функцию сложения трехбитовых чисел?

Пусть регулярное выражение b(a+b) определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:

Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые заканчиваются на bcc и содержат подслово aca Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* → {0, 1}* где h(a) = 00, h(b) = 10, h(c) = ε ?

В теореме 20.5 была доказана неразрешимость проблемы останова:по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть M_h0= {n | Ф_Пn,y(0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе монотонности вычисляемой ею функции:M_mon= {n | для любых x1 и x2, если x1 < x2, то Ф_Пn,y(x1) < Ф_Пn,y(x2)}.Какие из следующих функций сводят M_h0 к M_mon?
f1(n) = номер программы: 'x_n:=x; x:= 0; П_n ; y:= x_n'. (здесь переменная x_n не входит в П_n )
f2(n) = номер программы: 'П_n ; y:= x'.
f3(n) = номер программы: 'y:= x; x:= 0; П_n ; y:= y+1'.

Какие из следующих схем реализуют в вершине a функцию, заданную формулойA = ¬ (a ∧ ¬b) ∨ ((b∨ c) ∧ (a ∧ ¬b)) ?

Какую булеву функцию реализует эта диаграмма?(В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)

Пусть c₂(x, y) = 2^x(2y+1) -1 - это функция нумерации пар, а c₂₁(z) и c₂₂(z) - это соответствующие обратные функции такие, что c₂(c₂₁(z), c₂₂(z)) = z для всех z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функций, значения которых на аргументе (y+1) зависят от их значений в двух предыдущих точках y-1 и yРассмотрим функцию F(x), заданную равенствами:F(0) = 1, F(1) = 1, F(y+2) = F(y) + F(y+1) . Положим G(y) = c₂(F(y), F(y+1))Так какF(y) = c₂₁(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность GОпределите, какая из следующих примитивных рекурсий задает G

Пусть заданы три функции:f(x,y,z) = xy +z, g(x,y) = 2x - y, h(x) =2x²Какую функцию F(x₁,x₂) задает выражение[g; [f; I²₂ , I²₂ , I²₁ ], [h;[s¹; I²₂ ]] ?

Какой язык L является конкатенацией двух языков:L1= {ε, b, ab, abba} и L2= { a, b, ba}?

Заданы два НКА:
A =< {a, b}, {0, 1, 2, 3}, 0, {2}, Φ_A > с программой Φ_A: 0 a → 1, 0 b → 3, 1 a → 2, 1 b → 1, 2 a → 1, 2 b → 3, 3 a → 3, 3b → 3 и
B =< {a, b}, {q0, q1, q2}, q0, {q2}, Φ_B > с программой Φ_B: q0 b → q0, q0 b → q1, q1 a → q1, q1 a → q2, q2 b → q0
Какие из следующих трех НКА С₁ , С₂ , С₃ распознают конкатенацию L_A? L_B языков, распознаваемых автоматами A и B?
С₁ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₁={ q2},Φ₁> ,
С₂ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₂={ q2},Φ₂> ,
С₃ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₃={ q2}, Φ₃> , где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Следующий конечный автомат - преобразователь MINUS= <Σ_X ={0, 1} Σ_Y= { 0, 1}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>,где

вычитает из входного двоичного числа x некоторую константу c и выдает при c ≤ x выходное двоичное число y = x –c Чему равна эта константа c?

Какую булеву функцию реализует эта логическая схема в вершине a ?

Какие из следующих схем реализуют в вершине a функцию, заданную формулойA = ((a ∧ ¬b) ∨ ¬b) ∨ ¬ (b∨ c) ?

Пусть задана логическая схема S=(V, E) :V= {a (X), b(Y), c(Z), d(V), e(∧), f(¬),g(¬),h(∧), i(∧), k(¬), m(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция),E= { (a, e), (b, f), (c, g), (d, e), (d, i), (e, k), (f, h), (g,, h), (h, i),(i, m), (k, m) }.Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m?

P1:                        P2:                             P3:V = X ∧ V;                 f = ¬Y;                         Y = ¬Y;V = ¬V;                    g = ¬Z;                         Z = ¬Z;Y = ¬Y;                    e = X ∧ V;                      Z = Y ∧Z;Z = ¬Z;                    k = ¬e;                         Z = Z ∧V;Y = Y ∧ Z;                 h = f ∧ g;                      V = X ∧ V;Z = Y ∧ V;                 i = h ∧ V;                      V = ¬V;Z = V ∨ Z .                Z = h ∨ k.                      Z = Z ∧ V.

Пусть задана линейная программа 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. Чему равна ее глубина?

Чему равна глубина схемы S_odd , реализующей функцию odd(X₁, X₂, …,X_n) = X₁ + X₂ + … X_n ?

Какую булеву функцию реализует эта диаграмма?(В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)

Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?

Какие из следующих УБДР являются сокращенными?

Пусть задана УБДР D=(V,E):V={v1 (x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), , 0, 1} (в скобках после имени вершины указана переменная, которой она помечена),E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 0), (v2, v5; 1), (v3, v5; 1), (v3, v6; 0), (v4, v7; 0), (v4, v8; 1), (v5, v7; 0), (v5, v8; 1), (v6, v8; 1), (v6, v7; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 1), (v8, 1; 0)} ( для каждого ребра третий параметр после ; - его метка 0 или 1).Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.

Пороговая функция T_n,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T_5,3 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?

Пусть задан конечный автомат - преобразователь A = <Σ_X ={0, 1} Σ_Y= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>,где
Какое входное слово автомат А перерабатывает в выходное слово ТАРТАР?

Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>,где
Какие из следующих трех слов распознаются автоматом A?W= aaabaabab, V= abababaab, U= bbabbbababa

Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>,

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

Какие из следующих трех конечных автоматовA_i = < {a,b}, {0, 1, 2, 3, 4}, 0, F={1}, Φ_i> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые начинаются на b и содержат число букв a , кратное 3 ?

На следующем рисунке представлены диаграммы двух конечных автоматов A =< {a,b}, {q,p}, q, {p}, Φ_A> и B =< {a,b}, {1, 2, 3}, 1, {1, 2}, Φ_B>,

распознающих языки L_A и L_B, соответственно. Какой из следующих автоматов является произведением A × B и какой язык он реализует?
C = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2), (p,3)}, (q,0), F={(p,3)}, Φ_C >,
D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,1), (p,2)}, Φ_D >,

Пусть S={aaa, aab, aba, abb, baa, bab, bba, bbb} Какая из следующих фраз описывает итерацию S* этого языка?

Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых есть по крайней мере два подряд идущих 0 ?

Заданы два НКА:
A =< {a, b}, {0, 1, 2, 3}, 0, {2}, Φ_A > с программой Φ_A: 0 a → 1, 0 b → 3, 1 a → 3 1 b → 2, 2 a → 3, 2 b → 2, 3 a → 3, 3b → 3 и
B =< {a, b}, {q0, q1, q2}, q0, {q2}, Φ_B > с программой Φ_B: q0 a → q0, q0 b → q1, q1 a → q1, q1 a → q2
Какие из следующих трех НКА С₁ , С₂ , С₃ распознают конкатенацию L_A? L_B языков, распознаваемых автоматами A и B?С₁ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₁={ q2}, Φ₁>, С₂ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₂={ q2}, Φ₂>, С₃ = < {a,b}, {0, 1, 2, 3, q1, q2}, 0, F₃={ q2}, Φ₃>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Какие из следующих трех автоматов С₁ , С₂ , С₃ распознают язык, представляемый регулярным выражением 1 (01)*?
С₁ = < {0,1}, {q, p, r, s, t}, q, F₁={ t }, Φ₁>,
С₂ = < {0,1}, {q, p, r, s }, q, F₂={p, s}, Φ₂>,
С₃ = < {0,1}, {q, p, r, s, t}, q, F₃={ p, s}, Φ₃>,

где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые начинаются на aa и содержат подслово bb Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* → {0, 1}* где h(a) = 01, h(b) = 11, h(c) = ε ?

Пусть задан ДКА A =< {a, b, c}, {0, 1, 2}, 0, F= {2}, Φ_A > с программой Φ_A: { 0 a → 0, 0 b → 1, 0 c → 1, 1 a → 1, 1 b → 2, 1 c → 1, 2 a → 2, 2 b → 2, 2 c → 1} и гомоморфизм h: {a, b, c}* → {0, 1}*: h(a) = 1, h(b) = 01, h(c) = ε. Какие из следующих трех автоматов С₁, С₂, С₃ распознают гомоморфный образ h(L_A)?
С₁ = < {0, 1}, {0, 1, 2, q1, q2, q3}, 0, F₁={2}, Φ₁>,
С₂ = < {0, 1}, {0, 1, 2, q1, q2 }, 0, F₂={2}, Φ₂>,
С₃ = < {0, 1}, {0, 2, (q1, q2), (0,1), (1, 2), !}, 0, F₃={2, (1,2)}, Φ₃>,
где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {S}, Φ_A > с программой Φ_A: { Q a → R, Q b → P, P b → P, P a → R, R a → Q, R b → S, S a → R, S b → S} и гомоморфизм h: {0, 1, 2}* → {a, b}*: h(0) = bab, h(1) = aba, h(2) = ε. Какие из следующих трех автоматов С₁, С₂, С₃ распознают гомоморфный прообраз h^-1(L_A)?
С₁ = < {0, 1}, { Q, P, R, S }, 0, F₁={S}, Φ₁>,
С₂ = < {0, 1}, { Q, R, S }, 0, F₂={ S }, Φ₂>,
С₃ = < {0, 1}, { Q, P, R, S }, 0, F₃={ S }, Φ₃>,
где программы заданы в следующих таблицах.

Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв b превосходит количество букв a не менее чем на 2. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?

Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.
L1 = { a²bⁿa² | n > 0 },
L2 = { ww | w = a²bⁿa² , n > 0 },
L3 = { wv | w = a²bⁿa² , v = b²a^mb² для произвольных n,m > 0 }.

Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами?
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: x:= y+1; z := x+1; x := z+1; y:= y+1; z:= y; z := z +1 ; x := x+1начинает работу в состоянии σ : σ(x) =3, σ(y) =5, σ(z) =2В каком из следующих состояний σ1 она завершит свою работу?

Пусть структурированная программа

P:  x:= y+1;  v:= u+1;  пока  x < v  делай   если  y <  x то                       y := y+1                иначе  x := x +1; u := u+1   конец все

начинает работу в состоянии σ : σ(x) = 2, σ(y) =3, σ(u) = 5, σ(v) =0В каком из следующих состояний σ1она завершит свою работу?

Пусть П₊ - это построенная в лекции программа, которая вычисляет функцию Ф₊(x,y) = x+y в переменной x, используя одну рабочую переменную zКакие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный трехчлен p(x)= x² +2x +2 ?

Пусть П_× - это программа, которая вычисляет функцию Ф_× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x двоичный логарифм от x, т.е. функцию [ log₂( x)]?

Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = (x+1)² ?

Обозначим через minus(x,y) функцию "усеченного" вычитания,равную (x – y) при x ≥ y и 0 – в противном случае. Для какой из следующих функций f(x,y) выражение μy [ f(x,y)= 0] задает функцию F(x) = [ log₂ (x+1) ] (целая часть двоичного логарифма x+1) ?

Пусть c₂(x, y) = 2^x(2y+1) -1 - это функция нумерации пар, а c₂₁(z) и c₂₂(z) - это соответствующие обратные функции такие, что c₂(c₂₁(z), c₂₂(z)) = z для всех z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функций, значения которых на аргументе (y+1) зависят от их значений в двух предыдущих точках y-1 и y. Рассмотрим функцию F(x), заданную равенствами:F(0) = 1, F(1) = 2, F(y+2) = F(y) × F(y+1). Положим G(y) = c₂(F(y), F(y+1)). Так какF(y) = c₂₁(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность G. Определите, какая из следующих примитивных рекурсий задает G.

Пусть машина Тьюринга M имеет алфавит ленты Σ={ ∧, 0, 1}, алфавит состояний Q= {q, p, r, !}, начальное состояние q, заключительное состояние ! и программу Ф:
$\begin{array}{lll}q\ 0 \rightarrow q\ 0\ П & p\ 0 \rightarrow p\ 1\ Л & r\ 0 \rightarrow r\ 0\ Лq\ 1 \rightarrow q\ 1\ П & p\ 1 \rightarrow r\ 0\ Л & r\ 1 \rightarrow r\ 1\ Л q \wedge \rightarrow p\ \wedge Л & p \wedge \rightarrow ! \wedge П & r \wedge \rightarrow ! \wedge П\end{array}$
В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации q 1010 ?

Три машины Тьюринга M_i = < Σ, Q !, P_i, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы:Какие из этих машин переводят любую начальную конфигурацию вида q a²ⁿ b в заключительную конфигурацию ! b aⁿ (n ≥ 0 )?

В конструкции машины Тьюринга со стандартными заключительными конфигурациями нужна служебная машина Тьюринга, назовем ее MOVE, которая сдвигает полученный результат в начальную позицию, отмеченную символом со штрихом. Точнее, MOVE, начав работать в конфигурации вида q a w₁ #^k#' (a ∈Σ, w₁ ∈Σ*, k ≥ 0), должна завершить работу в конфигурации ∧^kpa'w₁ Пусть алфавит ленты MOVE включает символы из Σ ∪ {a' | a ∈ Σ}∪ {∧, #, #'}, а алфавит состояний Q= {q, p, r} ∪ {p^a | a ∈ Σ}Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для MOVE ?(В текстах программ a и b – это произвольные символы из Σ),
P1: q a → p^a ∧ П , q a' → p a' Н , p^a b → p^b a П, p^a b' → p^b a' П, p^a # → r a Л, p^a #' → r a' Л, p^a ∧ → r a Л, r a → r a Л , r a' → r a' Л , r ∧ → q ∧ П.
P2: q a → p^a ∧ П , p^a b → p^b a П, p^a b' → p^b a' П, p^a # → r a Л, p^a #' → r a' Л, p^a ∧ → r a Л, r a → r a Л , r a' → r a' Л , r ∧ → q ∧ П.
P3: q a → p^a ∧ П , p^a b → p^a b П, p^a # → p^a # П, p^a #' → r a Л, p^a b' → p^a b' П, p^a ∧ → r a Л, r a → r a Л , r a' → r a' Л , r ∧ → q ∧ П, q # → q ∧ П , q a' → p a' Н.

Пусть машина Тьюринга M построена из следующих простых машин Тьюринга:Коп_a –копирует вход после разделительного символа a : w ⇐ w a w;Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );Сум - складывает два аргумента в унарной системе: |^x * |^y ⇐ |^x+y ;Умн - умножает два аргумента в унарной системе: |^x * |^y ⇐ |^xy;с помощью операций последовательного и параллельного применения следующим образом:M = Коп_# ; par_#( Коп_* , Коп_* ); par_#( Умн, Сум); Зам(#, *); СумКакую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?

Пусть машина Тьюринга 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, соответственно?

Приведенные ниже машины Тьюринга Mi (i= 1,2,3,4)

M1 = Зам(∧, *); Зам(∧,|); while Нуль₁₂ do par_*( Выч1, Коп_#; Зам(#, |); Выч1) enddo; Выб₂₂

M2 = Зам(∧, *); Зам(∧,|); while Нуль₁₂ do par_*( Выч1, Коп_#; par_# (Пуст, Коп_#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб₂₂

M3 =   if  Нуль₁₁ then Пуст             else  Коп_*Зам(∧, *); Зам(∧,|); while Нуль₁₃ do par_*( Выч1, Коп_#, Пуст);             par_# (Пуст, Умн);  Зам(#, *)) enddo;  Выб₃₃ endif.

M4 =   if  Нуль₁₁ then Пуст             else  Коп_*Зам(∧, *); while Нуль₁₃ do par_*( Выч1, Коп_#, Пуст);             par_# (Пуст, Сум);  Зам(#, *)) enddo;  Выб₃₃ endif.

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

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

Нуль_in - выдает 1, если i-ый аргумент из n аргументов равен ∧ (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |ⁱ , i >0),

Выч1 – вычитает единицу в унарной системе: |^j⇐ |^j-1 (| ⇐ ∧)

Какая из этих машин вычисляет функцию f(x) = 2^x в унарном кодировании, т.е. переводит вход |^x в выход |^y, где y = 2^x?

В доказательстве теоремы 20.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x1,x2, y) = R( g², f⁴), требовалась м.Т. M₁, которая переводит конфигурацию вида |^x1|^x2 |^y в конфигурацию |^y * |^x1|^x2 ∧ |^g(x) , используя м.Т. M_g, вычисляющую функцию g(x1,x2).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M₁ ?
P1 = Коп_#; par_# (par_ (Чист, Чист,Пуст); Зам(,∧ ) , par_ (Пуст , Пуст ,Чист); Зам(,# ) ; Зам(,∧ ) ; Зам( #,* )); par_# (Пуст, Коп_* ); par_* (Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|,* ))
P2 = Коп_#; par_# (par_* (Чист, Чист , Пуст); Зам(,∧ ) ; Зам(,∧ ), par_* (Пуст , Пуст ,Чист); Зам(,# ) ; Зам(,∧ ) ; Зам( #,* )); par_# (Пуст, Коп_# ); par_# (Пуст, Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* )
P3 = Коп_; par_ (Чист, Чист, Пуст, Пуст, Пуст ,Чист); Зам(,∧ ); Зам(,# ); Зам(,∧ ); par_# (Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|, )); Зам( #,* )
В этих определениях участвуют следующие простые машины Тьюринга:
Коп_a –копирует вход после разделительного символа a : w ⇐ w a w;
Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );
Пуст - не изменяет аргумент: w ⇐ w ;
Чист – стирает аргумент: w ⇐ ∧ ;
+1 - прибавляет 1 к аргументу: |^x⇐ |^x+1

В доказательстве теоремы 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 < ∧, ∧, ∧, ∧> П ,
P2: : q <a, b, c, | > → q < a, b , c, | > П , s < a , b, |, d > → s < a , b, |, | > Л , q <a, b, |, d > → q < a, b, |, d > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q <a, b, ∧, ∧> → s < a , b, ∧, ∧ > Л , s < a , b, ∧, | > → s < a , b, ∧, ∧ > Л,
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 > Л ,

Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ?
(а) рефлексивность: A ≤m A ,
(b) симметричность: A ≤m B ⇔ B ≤m A,
(с) транзитивность: A ≤m B и B ≤m C ⇐ A ≤m C .

Пусть множество A = { (x, y) | y = x² }, B = { n³ | n ∈ N }.Какие из следующих функций осуществляют сведение A ≤m B ? (В выражениях ниже sqr(y) обозначает целую часть квадратного корня из y, sg(0) =0 и sg(n) = 1 при n > 0).

Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении.Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка.
(a) если x < y то P1 иначе P2 конец,
(b) если x = y то P1 иначе P2 конец.,
(c) x := 0.

Какие из следующих трех конечных автоматовA_i = < {a,b}, {0, 1, 2, 3}, 0, F={1}, Φ_i> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые начинаются на a и содержат четное число букв b ?

Какие из следующих трех автоматов С₁ , С₂ , С₃ распознают язык, представляемый регулярным выражением (00 + 1)*1?
С₁ = < {0,1}, {q, p, r, s, t}, q, F₁={ t }, Φ₁> ,
С₂ = < {0,1}, {q, p, r, s }, q, F₂={ s}, Φ₂> ,
С₃ = < {0,1}, {q, p, r, s, t}, q, F₃={ s}, Φ₃> ,
где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами?
P1: x := y+1; z:= x + 1; если x < z то y := z иначе y:=x конец
P2: x := y+1; v:= x +1; если x = z то y := v все
P3: x := y+1; u:= z +1; пока u < z +1 делай y := z; u := u+1 все

Постройте минимальные УБДР для функцииf(x1, x2, x3, x4)= (x1 ∧ x2) ∨ ( x3 ∧ x4)относительно двух упорядочений переменных:
a) x1 < x2 < x3 < x4 и
b) x1 < x3 < x2 < x4.
Определите сложности этих двух схем.

Пусть язык L в алфавите {a, b}, состоит из всех слов, которые заканчиваются на aa и содержат число символов b кратное 4, и пусть гоморфизм h: {0, 1,2}* → {a, b}* задан равенствами: h(0) = bab, h(1) = a, h(2) = ε Какие из следующих трех слов принадлежат прообразу h^-1(L) языка L при гомоморфизме h?W1 = 211100112, W2 = 201010121, W3 = 0021010211

Пусть П_× - это программа, которая вычисляет функцию Ф_× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный корень из x, т.е. функцию [ x ^1/2]?

Пусть функция F(x) задана примитивной рекурсиейR(1, h(y,z)), где h(y,z) = [2^z+1/z]Чему равно значение F(3)?

Пусть машина Тьюринга M построена из следующих простых машин Тьюринга:Коп_a –копирует вход после разделительного символа a : w ⇐ w a w;
Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );
Сум - складывает два аргумента в унарной системе: |^x * |^y ⇐ |^x+y ;
Умн - умножает два аргумента в унарной системе: |^x * |^y ⇐ |^xy ;
Пуст - не изменяет аргумент: w ⇐ w
с помощью операций последовательного и параллельного применения следующим образом:
M = Коп_# ; par_#( Коп_* ; Умн, Пуст ); par_#( Коп_* ; Сум , Пуст ); Зам(#,?); Сум
Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?

Пусть регулярное выражение b(ab)* определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:

Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>,

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

Какие из следующих схем реализуют в вершине a функцию, заданную формулойA = (a ∧ b ∧ с) ∨ (¬b ∧ (b∨ c)) ?

Приведенные ниже машины Тьюринга Mi (i= 1,2,3,4)

M1 = Зам(∧, *); Зам(∧,|); while Нуль₁₂ do par_*( Выч1, Коп_#; Зам(#, |); Выч1) enddo; Выб₂₂

M2 = Зам(∧, *); Зам(∧,|); while Нуль₁₂ do par_*( Выч1, Коп_#; par_# (Пуст, Коп_#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб₂₂

M3 =   if  Нуль₁₁ then Пуст             else  Коп_*Зам(∧, *); Зам(∧,|); while Нуль₁₃ do par_*( Выч1, Коп_#, Пуст);              par_# (Пуст, Умн);  Зам(#, *)) enddo;  Выб₃₃ endif.

M4 =   if  Нуль₁₁ then Пуст             else  Коп_*Зам(∧, *); while Нуль₁₃ do par_*( Выч1, Коп_#, Пуст);             par_# (Пуст, Сум);  Зам(#, *)) enddo;  Выб₃₃ endif.

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

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

Нуль_in - выдает 1, если i-ый аргумент из n аргументов равен ∧ (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |ⁱ, i >0),

Выч1 – вычитает единицу в унарной системе: |^j⇐ |^j-1 (| ⇐ ∧)

Какая из этих машин вычисляет функцию f(x) = 3^x в унарном кодировании, т.е. переводит вход |^x в выход |^y, где y = 3^x?

На следующем рисунке представлены диаграммы двух конечных автоматов A =< {a,b}, {q,p}, q, {p}, Φ_A> и B =< {a,b}, {1, 2, 3}, 1, {1, 2}, Φ_B>,

распознающих языки L_A и L_B, соответственно. Какой из следующих автоматов является произведением A × B и какой язык он реализует?
C = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2), (p,3)}, (q,0), F={(q, 1), (q, 2)}, Φ_C >,
D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,3)}, Φ_D >,

Пусть П₊ - это построенная в лекции программа, которая вычисляет функцию Ф₊(x,y) = x+y в переменной x, используя одну рабочую переменную z. Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x произведение x · y?

Пусть задан недетерминированный конечный автомат (без пустых переходов)M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программойΦ: q 0 → p, q 0 → s, p 0 → q, p 0 → s, p 1 → p, s 1 → pКакие из следующих трех ДКА эквивалентны M?
M1 = < {0, 1}, {q, p, ps, qs}, q, F1={p, ps}, Φ1> с программойΦ1: q 0 → ps, q 1 → p, p 0 → qs, p 1 → p, ps 0 → qs, ps 1 → p, qs 0 → ps, qs 1 → p
M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F2={p, ps, pq, qps}, Φ2> с программойΦ2: q 0 → ps, q 1 → p, p 0 → qs, p 1 → p, s 0→ ∅, s 1→ p, ps 0 → qs, ps 1 → p, qs 0 → ps, qs 1 → p, qp 0 → ps, qp 1 → p, qps 0 → qps, qps 1 → p, ∅ 0 →∅, ∅ 1 →∅.
M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F3={ p, ps, pq, qps }, Φ3> с программойΦ3: q 0 → ps, q 1 → p, p 0 → qs, p 1 → p, s 1→ p, ps 0 → qs, ps 1 → p, qs 0 → qps, qs 1 →qps, qp 0 → ps, qp 1 → p, qps 0 → qps, qps 1 → p. ∅ 0 →∅, ∅ 1 → ∅

В доказательстве теоремы 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 <|, b, c, d > → q < |, b , |, d > П , s < | , b, |, d > → s < | , b, |, d > Л , q <∧, b, |, d > → q < ∧, b, ∧, d > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л ,
P2: : q <|, b, c, d > → q < |, b , c, d > П , s < ∧ , b, |, d > → s < | , b, ∧, d > Л , q <a, b, |, d > → q < a, b, |, d > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л , s < | , b, c, d > → s < | , b, |, d > Л ,
P3: : q <|, b, c, d > → q < |, b , |, d > П , s < | , b, |, d > → s < | , b, |, d > Л , q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П.

Пусть язык L в алфавите {a, b}, состоит из всех слов, которые заканчиваются на abb и содержат число символов b кратное 3, и пусть гоморфизм h: {0, 1,2}* → {a, b}* задан равенствами: h(0) = bab, h(1) = b, h(2) = ε Какие из следующих трех слов принадлежат прообразу h^-1(L) языка L при гомоморфизме h?W1 = 210102012, W2 = 201000201021, W3 = 021010212

Какие из следующих УБДР являются сокращенными?

Какую булеву функцию реализует эта диаграмма?(В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)

Приведенные ниже машины Тьюринга Mi (i= 1,2,3,4)

M1 = Зам(∧, *); Зам(∧,|); while Нуль₁₂ do par_*( Выч1, Коп_#; Зам(#, |); Выч1) enddo; Выб₂₂

M2 = Зам(∧, *); Зам(∧,|); while Нуль₁₂ do par_*( Выч1, Коп_#; par_# (Пуст, Коп_#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб₂₂

M3 =   if  Нуль₁₁ then Пуст             else  Коп_*Зам(∧, *); Зам(∧,|); while Нуль₁₃ do par_*( Выч1, Коп_#, Пуст);             par_# (Пуст, Умн);  Зам(#, *)) enddo;  Выб₃₃ endif.

M4 =   if  Нуль₁₁ then Пуст             else  Коп_*Зам(∧, *); while Нуль₁₃ do par_*( Выч1, Коп_#, Пуст);             par_# (Пуст, Сум);  Зам(#, *)) enddo;  Выб₃₃ endif.

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

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

Нуль_in - выдает 1, если i-ый аргумент из n аргументов равен ∧ (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |ⁱ , i >0),

Выч1 – вычитает единицу в унарной системе: |^j⇐ |^j-1 (| ⇐ ∧, ∧ ⇐ ∧)

Какая из этих машин вычисляет функцию f(x) = x^x в унарном кодировании, т.е. переводит вход |^x в выход |^y, где y = x^x (пусть f(0)=0) ?

Какой язык L является конкатенацией двух языков:L1= {a, ab, abba} и L2= { ε, a, b, ba}?

Следующий конечный автомат - преобразователь MINUS= <Σ_X ={0, 1} Σ_Y= { 0, 1}, Q ={ 0, 1, 2 }, 0, Φ, Ψ>,где
вычитает из входного двоичного числа x некоторую константу c и выдает при c ≤ x выходное двоичное число y = x –c Чему равна эта константа c?

Пусть структурированная программа

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

начинает работу в состоянии σ : σ(x) =0, σ(y) =3, σ(z) =5, σ(u) = 4, σ(v) =2В каком из следующих состояний σ1 она завершит свою работу?

Пусть задана линейная программа 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.5 была доказана неразрешимость проблемы останова:по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть M_h0= {n | Ф_Пn,y(0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе бесконечности множества ее результатов: M_inf= {n | множество значений Ф_Пn,y(x) бесконечно}.Какие из следующих функций сводят M_h0 к M_inf ?
f1(n) = номер программы: ' x:= 0; П_n ; y:= x '.
f2(n) = номер программы: 'x_n:=x; x:= 0; П_n ; y:= x_n'. (здесь переменная x_n не входит в П_n )
f3(n) = номер программы: 'y:= x; x:= 0; П_n ; y:= y+1'.

Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые начинаются на cac и содержат подслово bcb Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* → {0, 1}* где
h(a) = 0, h(b) = 11, h(c) = ε ?

Пороговая функция T_n,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T_5,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?

Пусть функция rm(x, y) = y mod x равна остатку от деления y на x ( rm(0,y)=y), а функция p(n) принимает значение 1, если число n простое, и равна 0 для составных n (p(0)=p(1)=0, p(2)=p(3)=1, …). Какое из следующих выражений определяет при x >1 число mp(x), равное произведению различных простых делителей числа x? Например, mp(2)=mp(4)=mp(8) =2, mp(12)=2x3=6, … (Пусть mp(0)=mp(1)=1).

Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>,где
Какие из следующих трех слов распознаются автоматом A?W= aaabaababaab, V= babbbaabba, U= ababaaabba

Какую булеву функцию реализует эта логическая схема в вершине a ?

Пусть задана линейная программа 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. Чему равна ее глубина?

Какие из следующих УБДР являются сокращенными?

Следующий конечный автомат - преобразователь MINUS= <Σ_X ={0, 1} Σ_Y= { 0, 1}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>,
где
вычитает из входного двоичного числа x некоторую константу c и выдает при c ≤ x выходное двоичное число y = x – c Чему равна эта константа c?

Пусть задан недетерминированный конечный автомат M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={4, 5}, Φ> с программойΦ: 0 b → 1, 1 a → 2, 1 b → 3, 2 a → 3, 2 b → 1, 3 → 4, 4 a → 5, 4 → 5, 5 → 2Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?

Пусть задан недетерминированный конечный автомат (без пустых переходов)M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программойΦ: q 0 → q, q 1 → s, q 1→ p, p 0 → q, p 0 → p, s 0 → q, s 1 → pКакие из следующих трех ДКА эквивалентны M?
M1 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F1={p, ps, pq, pqs }, Φ1> с программой Φ1:q 0 → q, q 1 → ps, p 0 → pq, p 1 → ∅, s 0 → q, s 1 → pq, ps 0 → pq, ps 1 → p, pq 0 → pq, pq 1 → p, qs 0 → q, qs 1 →pq, pqs 0 → pq, pqs 1 → ps, ∅ 0 →∅, ∅ 1 →∅
M2 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F2={ p, ps, pq, pqs }, Φ2> с программой Φ2:q 0 → q, q 1 → ps, p 0 → pq, p 1 → q, s 0 → q, s 1 → pq, ps 0 → pq, ps 1 → p, pq 0 → pq, pq 1 → ps, qs 0 → q, qs 1 →pq, pqs 0 → pq, pqs 1 → ps, ∅ 0 →∅, ∅ 1 →∅
M3 = < {0, 1}, {q, p, ps, pq, ∅ }, q, F3={ ps, pq, p }, Φ3> с программой Φ3:q 0 → q, q 1 → ps, ps 0 → pq, ps 1 → p, pq 0 → pq, pq 1 → ps, p 0 → pq, p 1 → ∅, ∅ 0 →∅, ∅ 1 →∅

Какой язык L является конкатенацией двух языков:L1= {ε, b, ab, ba} и L2= {ε, a, b, ba}?

Пусть S={aa, ab, ba, bb} Какая из следующих фраз описывает итерацию S* этого языка?

Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых нет двух подряд идущих 0 ?

Пусть задан ДКА A =< {a, b, c}, {0, 1, 2, 3}, 0, F= {2}, Φ_A > с программой Φ_A: { 0 a → 1, 0 b → 1, 0 c → 0, 1 a → 1, 1 b → 2, 1 c → 2, 2 a → 3, 2 b → 3, 2 c → 2, 3 a → 3, 3 b → 3, 3 c → 3} и гомоморфизм h: {a, b, c}* → {0, 1}*: h(a) = 01, h(b) = 11, h(c) = ε Какие из следующих трех автоматов С₁, С₂, С₃ распознают гомоморфный образ h(L_A)?
С₁ = < {0, 1}, {0, 1, 2, 3, q0, q1, q2, q3, q4, q5, q6, q7}, 0, F₁={1,2}, Φ₁>,
С₂ = < {0, 1}, {0, 1, 2, 3, q0, q1, q2 }, 0, F₂={ 1,2}, Φ₂>,
С₃ = < {0, 1}, {0, 1, 2, 3, q0, q1, q2 }, 0, F₃={0,1,2}, Φ₃>,

где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {R}, Φ_A > с программой Φ_A: { Q a → P, Q b → Q, P b → P, P a → R, R a → Q, R b → S, S a → S, S b → S} и гомоморфизм h: {0, 1, 2}* → {a, b}*: h(0) = aba, h(1) = aa, h(2) = ε Какие из следующих трех автоматов С₁, С₂, С₃ распознают гомоморфный прообраз h^-1(L_A)?
С₁ = < {0, 1}, { Q, P, R, S }, 0, F₁={ R }, Φ₁>,
С₂ = < {0, 1}, { Q, P, R, S }, 0, F₂={ R }, Φ₂>,
С₃ = < {0, 1}, { Q, P, R, S }, 0, F₃={ R }, Φ₃>,
где программы заданы в следующих таблицах.

Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.
L1 = { wbw | w = aⁿ , n > 0 },
L2 = { bwwb | w = aⁿ , n > 0 },
L3 = { (ab)ⁿa^m | n, m > 0 }.

Пусть структурированная программа

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

начинает работу в состоянии σ : σ(x) =0, σ(y) =5, σ(z) =5, σ(u) = 6, σ(v) =2В каком из следующих состояний σ1 она завершит свою работу?

Пусть структурированная программа

P:  x:= y+1;  v:= u+1;  y := z+1; пока  x < v  делай   если  x < y   то                           x := y+1                    иначе  y := x +1   конец все

начинает работу в состоянии σ : σ(x) =0, σ(y) =2, σ(z) =2, σ(u) = 5, σ(v) =0В каком из следующих состояний σ1 она завершит свою работу?

Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = 2x² ?

Обозначим через minus(x,y) функцию "усеченного" вычитания,равную (x – y) при x ≥ y и 0 – в противном случае. Для какой из следующих функций f(x,y, i) выражение μi [ f(x,y,i)= 0] задает функцию F(x,y) = [ y/x ] (целая часть частного от деления y на x) ?

Пусть c₂(x, y) = 2^x(2y+1) -1 - это функция нумерации пар, а c₂₁(z) и c₂₂(z) - это соответствующие обратные функции такие, что c₂(c₂₁(z), c₂₂(z)) = z для всех z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функций, значения которых на аргументе (y+1) зависят от их значений в двух предыдущих точках y-1 и y. Рассмотрим функцию F(x), заданную равенствами:F(0) = 0, F(1) = 1, F(y+2) = F(y) + F(y+1) +1. Положим G(y) = c₂(F(y), F(y+1)). Так какF(y) = c₂₁(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность G. Определите, какая из следующих примитивных рекурсий задает G.

Пусть машина Тьюринга M имеет алфавит ленты Σ={ ∧, 0, 1}, алфавит состояний Q= {q, p, r, !}, начальное состояние q, заключительное состояние ! и программу Ф:
$\begin{array}{lll}q\ 0 \rightarrow q\ 0\ П & p\ 0 \rightarrow p\ 1\ Л & r\ 0 \rightarrow r\ 0\ Лq\ 1 \rightarrow q\ 1\ П & p\ 1 \rightarrow r\ 0\ Л & r\ 1 \rightarrow r\ 1\ Л q \wedge \rightarrow p \wedge Л & p \wedge \rightarrow ! \wedge П & r \wedge \rightarrow ! \wedge П\end{array}$
В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации q 1010 ?

Предположим, что в некоторой конфигурации машины Тьюринга M на ленте записано слово w в алфавите Σ, не содержащем символов ∧ и , но головка "заблудилась" – она наблюдает символ ∧ и не знает левее или правее слова w находится. Какие из следующих программ помогут найти начало слова w, т.е. любую конфигурацию вида q ∧^k w или w∧^kq ∧ (k > 0) переведут в конфигурацию q'w ?(В текстах программ a – это произвольный символ из Σ, используемые состояния: q, q', l, r, l₁, r₁ , l₂, r₂, l₃, r₃, l₄)
P1: q ∧ → l₁ Л, l₁∧→ r * П, l₁a→ l₂a П, l₂a→ l₂ a Л, l₂∧→ q'∧ П, r∧ → r ∧ П, r → r₁ ∧ П, r₁ ∧→ l Л, l ∧→ l ∧ Л, l → l₁ ∧ Л, r₁ a→ r₂a Л, r₂∧→ r₂∧ Л, r₂→ r₃∧ П, r₃∧→ r₃∧ П, r₃a→ q'a Н.
P2: q ∧ → l₁ * Л, l₁∧→ r * П, l₁a→ l₂a П, l₂∧→ l₂∧ П, l₂→ l₃∧ Л, l₃∧→ l₃∧ Л, l₃a→ q'a Н,r∧ → r ∧ П, r → r₁ ∧ П, r₁ ∧→ l * Л, l ∧→ l ∧ Л, l → l₁ ∧ Л,r₁ a→ r₂a Л, r₂∧→ r₂∧ Л, r₂→ r₃∧ П, r₃∧→ r₃∧ П, r₃a→ q'a Н.
P3: q ∧ → l₁ * Л, l₁∧→ r * П, l₁a→ l₂a П, l₂∧→ l₂∧ П, l₂→ l₃∧ Л, l₃∧→ l₃∧ Л, l₃a→ l₄ a Л,l₄a→ l₄ a Л, l₄∧→ q'∧ П, r∧ → r ∧ П, r → r₁ ∧ П, r₁ ∧→ l * Л, l ∧→ l ∧ Л, l → l₁ ∧ Л,r₁ a→ r₂a Л, r₂∧→ r₂∧ Л, r₂→ r₃∧ П, r₃∧→ r₃∧ П, r₃a→ q'a Н.

Пусть машина Тьюринга 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, соответственно?

В доказательстве теоремы 20.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g¹, f³), требовалась м.Т. M₂, которая переводит конфигурацию вида |^y |^x |^u* |^z в конфигурацию |^y |^x |^u+1* |^f(x,u,z) , используя м.Т. M_f, вычисляющую функцию f(x,u,z).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M₂ ?
P1 = Зам(,# ); par_# ( Пуст, Коп_#); par_# (Пуст, Пуст, M_f ); Зам( #, ); Зам( #,* )
P2 = Зам(,# ); par_# ( Пуст, Коп_#); par_# (Пуст, Пуст, M_f ); par_# (Пуст, par_ (Пуст, +1, Чист), Пуст); Зам( #,* ); Зам(∧, |); Зам( #,| ); par_* (Пуст, Пуст, Пуст, Выч1; Выч1)
P3 = Зам(,# ); par_# ( Пуст, Коп_#); par_# (Пуст, par_ (Пуст, +1, Чист), M_f ); par_* (Зам( #,* ), Пуст, Зам(∧, |); Зам( #,| ); Выч1; Выч1)
В этих определениях участвуют следующие простые машины Тьюринга:
Коп_a –копирует вход после разделительного символа a : w ⇐ w a w;
Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );
Пуст - не изменяет аргумент: w ⇐ w ;
Чист – стирает аргумент: w ⇐ ∧ ;
Выч1 – вычитает единицу в унарной системе: |^j⇐ |^j-1 (| ⇐ ∧, ∧ ⇐ ∧);
+1 - прибавляет 1 к аргументу: |^x⇐ |^x+1

Пусть множество A = { (x, y) | y = x² }, B = { 2ⁿ | n ∈ N }.Какие из следующих функций осуществляют сведение A ≤m B ? (В выражениях ниже sqr(y) обозначает целую часть квадратного корня из y, sg(0) =0 иsg(n) = 1 при n > 0).

В теореме 20.5 была доказана неразрешимость проблемы останова:по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть M_h0= {n | Ф_Пn,y(0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе независимости ее результата от входа: M_const= {n | существует константа c ∈ N такая, что Ф_Пn,y(x) = c для всех x}.Какие из следующих функций сводят M_h0 к M_const ?
f1(n) = номер программы: ' x:= 0; П_n ; y:= 0'.
f2(n) = номер программы: 'П_n ; y:= x'.
f3(n) = номер программы: ' x:= 0; П_n ; y:= 0; y:= y+1'.

В доказательстве теоремы 10.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g¹, f³), требовалась м.Т. M₁, которая переводит конфигурацию вида |^x* |^y в конфигурацию |^y * |^x* ∧ |^g(x) , используя м.Т. M_g, вычисляющую функцию g(x).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M₁ ?
P1 = Коп_#; par_# (par_ (Чист, Пуст); Зам(,∧ ) , par_ (Пуст ,Чист); Зам(,∧ ) ); par_# (Пуст, Коп_ ); par_* (Пуст, +1; +1; Зам(|,∧ ); Зам(|,* )); par_* (Пуст, Пуст, M_g); Зам( #,* )
P2 = Коп_#; par_# (par_* (Чист, Пуст); Зам(,∧ ) , par_ (Пуст ,Чист); Зам(,∧ ) ); par_# (Пуст, Коп_# ); par_# (Пуст, Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|, )); Зам( #,* ); Зам( #,* )
P3 = Коп_; par_ (Чист, Пуст, Пуст ,Чист); Зам(,∧ ); Зам(,# ); Зам(,∧ ); par_# (Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|, )); Зам( #,* )
В этих определениях участвуют следующие простые машины Тьюринга:
Коп_a – копирует вход после разделительного символа a : w ⇐ w a w;
Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );
Пуст – не изменяет аргумент: w ⇐ w ;
Чист – стирает аргумент: w ⇐ ∧ ;
+1 – прибавляет 1 к аргументу: |^x ⇐ |^x+1

Пусть структурированная программа P: x:= y+1; z := x+1; y := z+1; y:= y+1; z:= y; z := z +1 ; x := x+1начинает работу в состоянии σ : σ(x) = 2, σ(y) =3, σ(z) =2В каком из следующих состояний σ1 она завершит свою работу?

Постройте минимальные УБДР для функцииf(x1, x2, x3, x4)= (x1 ∧ x2) +( x3 ∧ x4)относительно двух упорядочений переменных:
a) x1 < x2 < x3 < x4 и
b) x1 < x3 < x2 < x4.
Определите сложности этих двух схем.

На следующем рисунке представлены диаграммы двух конечных автоматов A =< {a,b}, {q,p}, q, {p}, Φ_A> и B =< {a,b}, {1, 2, 3}, 1, {1, 2}, Φ_B>,

распознающих языки L_A и L_B, соответственно. Какой из следующих автоматов является произведением A × B и какой язык он реализует?
C = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2), (p,3)}, (q,0), F={(q, 1), (q, 2)}, Φ_C >,
D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,1), (p,2)}, Φ_D >,

Пусть функция rm(x, y) = y mod x равна остатку от деления y на x ( rm(0,y)=y )Какое из следующих выражений определяет число dn(x) различных делителей числа x, отличных от 1 и самого x?

Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>,где

Какие из следующих трех слов распознаются автоматом A?W= aaabbabab, V= babbbabba, U= ababaaab

Пороговая функция T_n,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T_4,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?

В доказательстве теоремы 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, ∧> П.

Какие из следующих трех конечных автоматовA_i = < {a,b}, {0, 1, 2, 3, 4}, 0, F={1}, Φ_i> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые заканчиваются на b и содержат число букв a , кратное 3 ?

Пусть задана логическая схема S=(V, E) :V= {a (X1), b(X2), c(X3), d(¬),e(¬), f(∧),g(∧),h(∧), i(∨), k(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция),E= { (a, d), (a, g), (b, e), (b, f), (c, f), (c, h), (d, h), (e, g), (f,k), (g, i), (i, k) }.Какую булеву функцию реализует схема S=(V, E) в вершине k?(В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов X1, X2 и X3)

Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?

Пусть задана УБДР D=(V,E): V={v1 (x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), v9(w), 0, 1} (в скобках после имени вершины указана переменная, которой она помечена),E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 1), (v2, v5; 0), (v3, v4; 1), (v3, v6; 0), (v4, v7; 1), (v4, v8; 0), (v5, v8; 1), (v5, v9; 0), (v6, v8; 1), (v6, v9; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 0), (v8, 1; 1), (v9, 0; 0), (v9, 1; 1) } ( для каждого ребра третий параметр после ; - его метка 0 или 1).Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.

Пусть задан конечный автомат - преобразователь A = <Σ_X ={0, 1} Σ_Y= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>, где

Какое входное слово автомат А перерабатывает в выходное слово АРАРАТ?

4.
Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {P, S}, Φ_A > с программой Φ_A: { Q a → R, Q b → P, P b → S, P a → P, R a → R, R b → S, S a → S, S b → R} и гомоморфизм h: {0, 1, 2}* → {a, b}*: h(0) = bab, h(1) = aa, h(2) = ε. Какие из следующих трех автоматов С₁, С₂, С₃ распознают гомоморфный прообраз h^-1(L_A)?
С₁ = < {0, 1}, { Q, P, R, S }, 0, F₁={P, S}, Φ₁>,
С₂ = < {0, 1}, { Q, S }, 0, F₂={ S }, Φ₂>,
С₃ = < {0, 1}, { Q, R, S }, 0, F₃={ S }, Φ₃>,
где программы заданы в следующих таблицах.

Пусть структурированная программа P: x:= y+1; y := z+1; z := z+1; y:= y+1; z:= y; z := z +1 ; x := x+1начинает работу в состоянии σ : σ(x) = 3, σ(y) =4, σ(z) =2В каком из следующих состояний σ1 она завершит свою работу?

Пусть структурированная программа

P:  x:= y+1;  v:= u+1;  пока  x < v  делай  если  y <  x то                         y := y+1; u := u+1                  иначе  x := x +1  конец все

начинает работу в состоянии σ : σ(x) =0, σ(y) =2, σ(u) = 5, σ(v) =0В каком из следующих состояний σ1 она завершит свою работу?

Пусть заданы три функции:f(x,y,z) = xy +z, g(x,y) = 2x + y, h(x) =2x²Какую функцию F(x₁,x₂) задает выражение[f; [h; I²₁ ] [g; [h; I²₂ ], I²₂], I²₂] ?

Обозначим через minus(x,y) функцию "усеченного" вычитания,равную (x – y) при x ≥ y и 0 – в противном случае. Для какой из следующих функций f(x,y) выражение μy [ f(x,y)= 0] задает функцию $F(x) = [ \sqrt{x} ]$ (целая часть квадратного корня из x) ?

Пусть функция F(x) задана примитивной рекурсиейR(1, h(y,z)), где h(y,z) = [2^z/z]Чему равно значение F(5)?

Пусть машина Тьюринга M построена из следующих простых машин Тьюринга:
Коп_a –копирует вход после разделительного символа a : w ⇐ w a w;
Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );
Сум - складывает два аргумента в унарной системе: |^x * |^y ⇐ |^x+y ;
Умн - умножает два аргумента в унарной системе: |^x * |^y ⇐ |^xy ;
Пуст - не изменяет аргумент: w ⇐ w
с помощью операций последовательного и параллельного применения следующим образом:
M = Коп_# ; par_#( Коп_* , Коп_* ); par_#( Умн, Сум); par_#( Коп_* ; Сум , Пуст ); Зам(#,?); Сум
Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?

Какие из следующих трех автоматов С₁ , С₂ , С₃ распознают язык, представляемый регулярным выражением 0(10 +1)*?
С₁ = < {0,1}, {q, p, r, s, t}, q, F₁={ t }, Φ₁>,
С₂ = < {0,1}, {q, p, r, s }, q, F₂={p, r}, Φ₂>,
С₃ = < {0,1}, {q, p, r, s, t}, q, F₃={ p, r, s}, Φ₃>,
где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

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

Пусть задана логическая схема S=(V, E) :V= {a (X), b(Y), c(Z), d(V), e(¬), f(∨),g(∨),h(¬), i(¬), k(∨), m(∧) } (после имени вершины в скобках указана ее метка - переменная или булева функция),E= { (a, i), (b, f), (b, k), (c, g), (d, e), (e, g), (f, h), (g, k), (h, m), (i, f), (k, m) }.Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m?

P1:                       P2:                        P3:X = ¬X;                   i = ¬X;                    X = ¬X;V = ¬V;                   e = ¬V;                    X = X ∨ Y;X = X ∨ Y;                f = i ∨ Y;                 X = ¬X;  Z = Z ∨ V;                h = ¬i;                    V = ¬V;X = ¬X;                   g = Z ∨ e;                 V = Z ∨ V;Y = Y ∨ Z;                k = Y ∨ g;                 V = Y ∨ V;Z = X ∧ Y.                Z = h ∧ k.                 Z = X ∧ V.

Чему равна глубина схемы S₁, реализующей функцию сложения однобитовых чисел?

Пусть задана УБДР D=(V,E): V={v1(x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), , 0, 1} (в скобках после имени вершины указана переменная, которой она помечена), E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 0), (v2, v5; 1), (v3, v5; 1), (v3, v6; 0), (v4, v7; 0), (v4, v8; 1), (v5, v7; 0), (v5, v8; 1), (v6, v8; 1), (v6, v7; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 0), (v8, 1; 1)} ( для каждого ребра третий параметр после ; - его метка 0 или 1).Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.

Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>,
Какой из следующих языков распознает автомат A ?

Пусть задан ДКА A =< {a, b, c}, {0, 1, 2}, 0, F= {2}, Φ_A > с программой Φ_A: { 0 a → 1, 0 b → 0, 0 c → 1, 1 a → 2, 1 b → 1, 1 c → 1, 2 a → 2, 2 b → 2, 2 c → 1} и гомоморфизм h: {a, b, c}* → {0, 1}*: h(a) = 01, h(b) = 1, h(c) = εКакие из следующих трех автоматов С₁, С₂, С₃ распознают гомоморфный образ h(L_A)?
С₁ = < {0, 1}, {0, 1, 2, q1, q2, q3}, 0, F₁={2}, Φ₁>,
С₂ = < {0, 1}, {0, 1, 2, q1, q2 }, 0, F₂={2}, Φ₂>,
С₃ = < {0, 1}, {0, 2, (q1, q2), (0,1), (1, 2), !}, 0, F₃={2, (1,2)}, Φ₃>,
где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.
L1 = { ww | w = b²aⁿb , n > 0 },
L2 = { b²aⁿb | n > 0 },
L3 = { (ab)ⁿaⁿb | n > 0 }.

Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = x² + x?

Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ?
(a) является отношением эквивалентности,
(b) рефлексивно и транзитивно,
(c) сохраняет свойство разрешимости: если A ≤ m B и B - разрешимо, то и A разрешимо.

Пусть заданы три функции:f(x,y,z) = xy +z, g(x,y) = 2x + y, h(x) =2x²Какую функцию F(x₁,x₂) задает выражение[f;[g;I²₁, I²₁], I²₁ , [h; I²₂ ]] ?

Пусть S={aaa, aba, baa, bba} Какая из следующих фраз описывает итерацию S* этого языка?

Пусть П₊ - это построенная в лекции программа, которая вычисляет функцию Ф₊(x,y) = x+y в переменной x, используя одну рабочую переменную zКакие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x ее квадрат x · x ?

Три машины Тьюринга M_i = < Σ, Q !, P_i, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы:Какие из этих машин переводят любую начальную конфигурацию вида q aⁿ b в заключительную конфигурацию ! b aⁿ (n ≥ 0 )?

Какую булеву функцию реализует эта логическая схема в вершине a?

Пусть задан недетерминированный конечный автомат M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={4, 5}, Φ> с программойΦ: 0 b → 1, 0 → 2, 1 a → 2, 1 b → 4, 2 → 3, 2 → 5, 3 a → 4, 3 b → 2, 4 → 5Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?

Заданы два НКА:
A =< {a, b}, {0, 1, 2, 3}, 0, {2}, Φ_A > с программой Φ_A: 0 a → 1, 0 a → 2, 0 b → 0, 1 a → 2, 1 b → 1, 2 a → 3, 2 b → 2, 3 a → 3, 3b → 3 и
B =< {a, b}, {q0, q1, q2}, q0, {q2}, Φ_B > с программой Φ_B: q0 a → q1, q1 b → q0,q1 a → q2, q2 b → q1
Какие из следующих трех НКА С₁ , С₂ , С₃ распознают конкатенацию L_A? L_B языков, распознаваемых автоматами A и B?С₁ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₁={ q2}, Φ₁>, С₂ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₂={ q2}, Φ₂>, С₃ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₃={ q2}, Φ₃>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Пусть задана логическая схема S=(V, E) :V= {a (X1), b(X2), c(X3), d(¬),e(¬), f(¬),g(∧),h(∨), i(∧), k(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция),E= { (a, d), (a, g), (b, e), (c, f), (c, g), (d, i), (e, h), (f,h), (g,k), (i, k) }.Какую булеву функцию реализует схема S=(V, E) в вершине k?(В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов X1, X2 и X3)

Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении.Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка.
(a) x := x +1,
(b) пока x < y делай P все,
(c) пока x = y делай P все.
.

Пусть задана логическая схема S=(V, E) :V= {a (X), b(Y), c(Z), d(V), e(∧), f(∧),g(¬),h(¬), i(∧), k(∧), m(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция),E= { (a, h), (b, f), (c, e), (c, g), (d, f), (e, i), (f ,i), (f ,k), (g,, k), (h,e),(i, m), (k, m) }.Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m?

P1:                         P2:                        P3:X = ¬X;                     h = ¬X;                    X = ¬X; Z = ¬Z;                     g = ¬Z;                    X = X ∧ Z;  X = X ∧ Z;                  e = h ∧ Z;                 Z = ¬Z;      Y = Y ∧ V;                  f = Y ∧ V;                 V = Y ∧ V;Y = Y ∧ X;                  k = f ∧ g;                 V = X ∧ V;Z = Y ∧ Z;                  i = e ∧ f;                 Y = V ∧ Z;Z = Y ∨ Z.                  Z = i ∨ k.                 Z = Y ∨ V.

Пусть регулярное выражение (ab)*a определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:

Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв a превосходит количество букв b не менее чем на 2. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?

Пусть множество A = { (x², y²) | x ∈ N , y ∈ N }, B = { n³ | n ∈ N }.Какие из следующих функций осуществляют сведение A ≤m B ? (В выражениях ниже sqr(x) обозначает целую часть квадратного корня из x, sg(0) =0 иsg(n) = 1 при n > 0).

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

Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?

Пусть функция F(x) задана примитивной рекурсиейR(1, h(y,z)), где h(y,z) = [2z/z2]Чему равно значение F(5)?

Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых есть по крайней мере две подряд идущие 1-цы ?

Пусть задан конечный автомат - преобразователь A = <ΣX ={0, 1} ΣY= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>,гдеКакое входное слово автомат А перерабатывает в выходное слово ТАРАРА?

Чему равна глубина схемы S3, реализующей функцию сложения трехбитовых чисел?

Пусть регулярное выражение b*(a+b)* определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:

Какие из следующих схем реализуют в вершине a функцию, заданную формулойA = ¬ (a ∧ ¬b) ∨ ((b∨ c) ∧ (a ∧ ¬b)) ?

Пусть заданы три функции:f(x,y,z) = xy +z, g(x,y) = 2x - y, h(x) =2x2Какую функцию F(x1,x2) задает выражение[g; [f; I22 , I22 , I21 ], [h;[s1; I22 ]] ?

Какой язык L является конкатенацией двух языков:L1= {ε, b, ab, abba} и L2= { a, b, ba}?

Какую булеву функцию реализует эта логическая схема в вершине a ?

Какие из следующих схем реализуют в вершине a функцию, заданную формулойA = ((a ∧ ¬b) ∨ ¬b) ∨ ¬ (b∨ c) ?

Чему равна глубина схемы Sodd , реализующей функцию odd(X1, X2, …,Xn) = X1 + X2 + … Xn ?

Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?

Какие из следующих УБДР являются сокращенными?

Пусть задан конечный автомат - преобразователь A = <ΣX ={0, 1} ΣY= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>,гдеКакое входное слово автомат А перерабатывает в выходное слово ТАРТАР?

Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>,гдеКакие из следующих трех слов распознаются автоматом A?W= aaabaabab, V= abababaab, U= bbabbbababa

Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>, Какой из следующих языков распознает автомат A ?

Пусть S={aaa, aab, aba, abb, baa, bab, bba, bbb} Какая из следующих фраз описывает итерацию S* этого языка?

Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых есть по крайней мере два подряд идущих 0 ?

Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = (x+1)2 ?

Пусть функция F(x) задана примитивной рекурсиейR(1, h(y,z)), где h(y,z) = [2z+1/z]Чему равно значение F(3)?

Пусть регулярное выражение b(ab)* определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:

Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>, Какой из следующих языков распознает автомат A ?

Какие из следующих схем реализуют в вершине a функцию, заданную формулойA = (a ∧ b ∧ с) ∨ (¬b ∧ (b∨ c)) ?

Какие из следующих УБДР являются сокращенными?

Какой язык L является конкатенацией двух языков:L1= {a, ab, abba} и L2= { ε, a, b, ba}?

Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>,гдеКакие из следующих трех слов распознаются автоматом A?W= aaabaababaab, V= babbbaabba, U= ababaaabba

Какую булеву функцию реализует эта логическая схема в вершине a ?

Какие из следующих УБДР являются сокращенными?

Какой язык L является конкатенацией двух языков:L1= {ε, b, ab, ba} и L2= {ε, a, b, ba}?

Пусть S={aa, ab, ba, bb} Какая из следующих фраз описывает итерацию S* этого языка?

Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых нет двух подряд идущих 0 ?

Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = 2x2 ?

Пусть функция rm(x, y) = y mod x равна остатку от деления y на x ( rm(0,y)=y )Какое из следующих выражений определяет число dn(x) различных делителей числа x, отличных от 1 и самого x?

Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>,где Какие из следующих трех слов распознаются автоматом A?W= aaabbabab, V= babbbabba, U= ababaaab

Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?

Пусть задан конечный автомат - преобразователь A = <ΣX ={0, 1} ΣY= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>, где Какое входное слово автомат А перерабатывает в выходное слово АРАРАТ?

Пусть заданы три функции:f(x,y,z) = xy +z, g(x,y) = 2x + y, h(x) =2x2Какую функцию F(x1,x2) задает выражение[f; [h; I21 ] [g; [h; I22 ], I22], I22] ?

Пусть функция F(x) задана примитивной рекурсиейR(1, h(y,z)), где h(y,z) = [2z/z]Чему равно значение F(5)?

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

Пусть функция F(x) задана примитивной рекурсиейR(1, h(y,z)), где h(y,z) = [2^z/z²]Чему равно значение F(5)?

Пусть задан конечный автомат - преобразователь A = <Σ_X ={0, 1} Σ_Y= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>,где
Какое входное слово автомат А перерабатывает в выходное слово ТАРАРА?

Чему равна глубина схемы S₃, реализующей функцию сложения трехбитовых чисел?

Пусть регулярное выражение b(a+b) определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:

Пусть заданы три функции:f(x,y,z) = xy +z, g(x,y) = 2x - y, h(x) =2x²Какую функцию F(x₁,x₂) задает выражение[g; [f; I²₂ , I²₂ , I²₁ ], [h;[s¹; I²₂ ]] ?

Чему равна глубина схемы S_odd , реализующей функцию odd(X₁, X₂, …,X_n) = X₁ + X₂ + … X_n ?

Пусть задан конечный автомат - преобразователь A = <Σ_X ={0, 1} Σ_Y= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>,где
Какое входное слово автомат А перерабатывает в выходное слово ТАРТАР?

Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>,где
Какие из следующих трех слов распознаются автоматом A?W= aaabaabab, V= abababaab, U= bbabbbababa

Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>,

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

Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = (x+1)² ?

Пусть функция F(x) задана примитивной рекурсиейR(1, h(y,z)), где h(y,z) = [2^z+1/z]Чему равно значение F(3)?

Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>,

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

Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>,где
Какие из следующих трех слов распознаются автоматом A?W= aaabaababaab, V= babbbaabba, U= ababaaabba

Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = 2x² ?

Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>,где

Какие из следующих трех слов распознаются автоматом A?W= aaabbabab, V= babbbabba, U= ababaaab

Пусть задан конечный автомат - преобразователь A = <Σ_X ={0, 1} Σ_Y= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>, где

Какое входное слово автомат А перерабатывает в выходное слово АРАРАТ?

Пусть заданы три функции:f(x,y,z) = xy +z, g(x,y) = 2x + y, h(x) =2x²Какую функцию F(x₁,x₂) задает выражение[f; [h; I²₁ ] [g; [h; I²₂ ], I²₂], I²₂] ?

Пусть функция F(x) задана примитивной рекурсиейR(1, h(y,z)), где h(y,z) = [2^z/z]Чему равно значение F(5)?

Чему равна глубина схемы S₁, реализующей функцию сложения однобитовых чисел?