База ответов ИНТУИТ

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

Количество вопросов - 168

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

Пусть задан недетерминированный конечный автомат 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) = [2z/z2]Чему равно значение 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'}∪ {pa | a ∈ Σ} – множество состояний CHANGE. Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для CHANGE ?(В текстах программ a – это произвольный символ из Σ, а b - это произвольный символ из Σ ∪ {*, #} ).

    P1: q b →​ q b П , q ∧ →​ s # Л, s b →​ s b Л, s ∧ →​ p ∧ П, p a →​ pa ∧П, p * →​ r ∧П, pa b →​ pa b П, pa ∧ →​ s a Л, r a →​ r a П , r # →​ q’ * П.

    P2: q a →​ q a П , q ∧ →​ s * Л, s b →​ s b Л, s ∧ →​ p ∧ П, p a →​ pa ∧П, p * →​ r ∧П, pa b →​ pa b П, pa ∧ →​ s a Л, r a →​ r a П , r*→​ q’ * П.

    P3: q a →​ q a П , q ∧ →​ s * Л, s b →​ s b Л, s ∧ →​ p ∧ П, p a →​ pa ∧П, p * →​ q’ * П, pa b →​ pa b П, pa ∧ →​ 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 аргументов: x1*…*xi*…*xn ⇐ xi ,
  • Большеij - выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn i-ый аргумент xi больше j-ого аргумента xj , иначе выдает 1,
  • с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом:
    M =  Коп# ; par#( par* (Коп*, Пуст ); Зам(*, |), Пуст );if  Больше12  then par#(  Пуст, Сум  ) else  par#(  Пуст, Умн ) endif;Зам(#, *); Выб33.
    Какие результаты она получит на входных данных вида |x1 * |x2 при x1 = 3, x2 = 6 и при x1 = 2, x2 = 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 →​∅

    Три машины Тьюринга Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы:Какие из этих машин переводят любую начальную конфигурацию вида q an b в заключительную конфигурацию ! b a2n (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)

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

    Пусть регулярное выражение 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. Пусть Mh0= {n | ФПn,y (0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе монотонности вычисляемой ею функции:M mon = {n | для любых x1 и x2, если x1 < x2, то ФПn,y (x1) < ФПn,y (x2)}.Какие из следующих функций сводят Mh0 к M mon ?
  • f1(n) = номер программы: 'xn:=x; x:= 0; Пn ; y:= xn'. (здесь переменная xn не входит в П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)

    Пусть c2(x, y) = 2x(2y+1) -1 - это функция нумерации пар, а c21(z) и c22(z) - это соответствующие обратные функции такие, что c2(c21(z), c22(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) = c2(F(y), F(y+1))Так какF(y) = c21(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность GОпределите, какая из следующих примитивных рекурсий задает G

    Пусть заданы три функции: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, 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

    Какие из следующих трех НКА С1 , С2 , С3 распознают конкатенацию LA? LB языков, распознаваемых автоматами A и B?

    С1 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F1={ q2},Φ1> ,

    С2 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F2={ q2},Φ2> ,

    С3 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F3={ q2}, Φ3> , где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

    Следующий конечный автомат - преобразователь 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.
  • Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?

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

    Какую булеву функцию реализует эта диаграмма?(В ответах функции заданы последовательностями 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 эквивалентную ей сокращенную УБДР и укажите ее сложность.

    Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T5,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 ?

    Какие из следующих трех конечных автоматовAi = < {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>,

    распознающих языки LA и LB, соответственно. Какой из следующих автоматов является произведением 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

    Какие из следующих трех НКА С1 , С2 , С3 распознают конкатенацию LA? LB языков, распознаваемых автоматами A и B?С1 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F1={ q2}, Φ1>, С2 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F2={ q2}, Φ2>, С3 = < {a,b}, {0, 1, 2, 3, q1, q2}, 0, F3={ q2}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

    Какие из следующих трех автоматов С1 , С2 , С3 распознают язык, представляемый регулярным выражением 1 (01)*?

    С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1>,

    С2 = < {0,1}, {q, p, r, s }, q, F2={p, s}, Φ2>,

    С3 = < {0,1}, {q, p, r, s, t}, q, F3={ p, s}, Φ3>,

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

    Пусть язык 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) = ε. Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный образ h(LA)?

    С1 = < {0, 1}, {0, 1, 2, q1, q2, q3}, 0, F1={2}, Φ1>,

    С2 = < {0, 1}, {0, 1, 2, q1, q2 }, 0, F2={2}, Φ2>,

    С3 = < {0, 1}, {0, 2, (q1, q2), (0,1), (1, 2), !}, 0, F3={2, (1,2)}, Φ3>,

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

    Пусть задан ДКА 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) = ε. Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный прообраз h-1(LA)?

    С1 = < {0, 1}, { Q, P, R, S }, 0, F1={S}, Φ1>,

    С2 = < {0, 1}, { Q, R, S }, 0, F2={ S }, Φ2>,

    С3 = < {0, 1}, { Q, P, R, S }, 0, F3={ S }, Φ3>,

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

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

    Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.

    L1 = { a2bna2 | n > 0 },

    L2 = { ww | w = a2bna2 , n > 0 },

    L3 = { wv | w = a2bna2 , v = b2amb2 для произвольных 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)= x2 +2x +2 ?

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

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

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

    Пусть c2(x, y) = 2x(2y+1) -1 - это функция нумерации пар, а c21(z) и c22(z) - это соответствующие обратные функции такие, что c2(c21(z), c22(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) = c2(F(y), F(y+1)). Так какF(y) = c21(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 ?

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

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

    P1: q a →​ pa ∧ П , q a' →​ p a' Н , pa b →​ pb a П, pa b' →​ pb a' П, pa # →​ r a Л, pa #' →​ r a' Л, pa ∧ →​ r a Л, r a →​ r a Л , r a' →​ r a' Л , r ∧ →​ q ∧ П.

    P2: q a →​ pa ∧ П , pa b →​ pb a П, pa b' →​ pb a' П, pa # →​ r a Л, pa #' →​ r a' Л, pa ∧ →​ r a Л, r a →​ r a Л , r a' →​ r a' Л , r ∧ →​ q ∧ П.

    P3: q a →​ pa ∧ П , pa b →​ pa b П, pa # →​ pa # П, pa #' →​ r a Л, pa b' →​ pa b' П, pa ∧ →​ 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: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );Сум - складывает два аргумента в унарной системе: |x * |y ⇐ |x+y ;Умн - умножает два аргумента в унарной системе: |x * |y ⇐ |xy;с помощью операций последовательного и параллельного применения следующим образом:M = Коп# ; par#( Коп* , Коп* ); par#( Умн, Сум); Зам(#, *); СумКакую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?

    Пусть машина Тьюринга M построена из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин
  • Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,
  • Большеij - выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn i-ый аргумент xi больше j-ого аргумента xj , иначе выдает 1,
  • с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом:
    M =  Коп# ; par#( par* (Коп*, Пуст ); Зам(*, |), Пуст );if  Больше21  then par#(  Пуст, Умн ) else  par#(  Пуст, Сум ) endif;Зам(#, *); Выб33.
    Какие результаты она получит на входных данных вида |x1 * |x2при x1 = 4, x2 = 8 и при x1 = 1, x2 = 5, соответственно?

    Приведенные ниже машины Тьюринга Mi (i= 1,2,3,4)
  • M1 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; Зам(#, |); Выч1) enddo; Выб22
  • M2 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; par# (Пуст, Коп#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб22
  • M3 =   if  Нуль11 then Пуст             else  Коп* Зам(∧, *); Зам(∧,|); while Нуль13 do par*( Выч1, Коп#, Пуст);             par# (Пуст, Умн);  Зам(#, *)) enddo;  Выб33   endif.
  • M4 =   if  Нуль11 then Пуст             else  Коп* Зам(∧, *); while Нуль13 do par*( Выч1, Коп#, Пуст);             par# (Пуст, Сум);  Зам(#, *)) enddo;  Выб33   endif.
  • построены из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин
  • Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,
  • Нульin - выдает 1, если i-ый аргумент из n аргументов равен (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |i , i >0),
  • Выч1 – вычитает единицу в унарной системе: |j ⇐ |j-1 (| ⇐ ∧)
  • Какая из этих машин вычисляет функцию f(x) = 2x в унарном кодировании, т.е. переводит вход |x в выход |y, где y = 2x?

    В доказательстве теоремы 20.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x1,x2, y) = R( g2, f4), требовалась м.Т. M1, которая переводит конфигурацию вида |x1*|x2* |y в конфигурацию |y * |x1*|x2* ∧ *|g(x) , используя м.Т. Mg, вычисляющую функцию g(x1,x2).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M1 ?
  • P1 = Коп# ; par# (par* (Чист, Чист,Пуст); Зам(*,∧ ) , par* (Пуст , Пуст ,Чист); Зам(*,# ) ; Зам(*,∧ ) ; Зам( #,* )); par# (Пуст, Коп* ); par* (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* ))
  • P2 = Коп# ; par# (par* (Чист, Чист , Пуст); Зам(*,∧ ) ; Зам(*,∧ ), par* (Пуст , Пуст ,Чист); Зам(*,# ) ; Зам(*,∧ ) ; Зам( #,* )); par# (Пуст, Коп# ); par# (Пуст, Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* )
  • P3 = Коп* ; par* (Чист, Чист, Пуст, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par# (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* )
  • В этих определениях участвуют следующие простые машины Тьюринга:

  • Копa –копирует вход после разделительного символа a : w ⇐ w a w;
  • Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );
  • Пуст - не изменяет аргумент: w ⇐ w ;
  • Чист – стирает аргумент: w ⇐ ∧ ;
  • +1 - прибавляет 1 к аргументу: |x⇐ |x+1
  • В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M43, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M43 ?(В текстах программ 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 = x2 }, B = { n3 | 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.
  • Какие из следующих трех конечных автоматовAi = < {a,b}, {0, 1, 2, 3}, 0, F={1}, Φi> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые начинаются на a и содержат четное число букв b ?

    Какие из следующих трех автоматов С1 , С2 , С3 распознают язык, представляемый регулярным выражением (00 + 1)*1?

    С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1> ,

    С2 = < {0,1}, {q, p, r, s }, q, F2={ s}, Φ2> ,

    С3 = < {0,1}, {q, p, r, s, t}, q, F3={ s}, Φ3> ,

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

    Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами?
  • 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) = [2z+1/z]Чему равно значение F(3)?

    Пусть машина Тьюринга M построена из следующих простых машин Тьюринга:Копa –копирует вход после разделительного символа a : w ⇐ w a w;
  • Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );
  • Сум - складывает два аргумента в унарной системе: |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 Нуль12 do par*( Выч1, Коп#; Зам(#, |); Выч1) enddo; Выб22
  • M2 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; par# (Пуст, Коп#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб22
  • M3 =   if  Нуль11 then Пуст             else  Коп* Зам(∧, *); Зам(∧,|); while Нуль13 do par*( Выч1, Коп#, Пуст);              par# (Пуст, Умн);  Зам(#, *)) enddo;  Выб33   endif.
  • M4 =   if  Нуль11 then Пуст             else  Коп* Зам(∧, *); while Нуль13 do par*( Выч1, Коп#, Пуст);             par# (Пуст, Сум);  Зам(#, *)) enddo;  Выб33   endif.
  • построены из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин
  • Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,
  • Нульin - выдает 1, если i-ый аргумент из n аргументов равен (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |i, i >0),
  • Выч1 – вычитает единицу в унарной системе: |j ⇐ |j-1 (| ⇐ ∧)
  • Какая из этих машин вычисляет функцию f(x) = 3x в унарном кодировании, т.е. переводит вход |x в выход |y, где y = 3x?

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

    распознающих языки LA и LB, соответственно. Какой из следующих автоматов является произведением 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П, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M31, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M31 ?(В текстах программ 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 Нуль12 do par*( Выч1, Коп#; Зам(#, |); Выч1) enddo; Выб22
  • M2 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; par# (Пуст, Коп#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб22
  • M3 =   if  Нуль11 then Пуст             else  Коп* Зам(∧, *); Зам(∧,|); while Нуль13 do par*( Выч1, Коп#, Пуст);             par# (Пуст, Умн);  Зам(#, *)) enddo;  Выб33   endif. 
  • M4 =   if  Нуль11 then Пуст             else  Коп* Зам(∧, *); while Нуль13 do par*( Выч1, Коп#, Пуст);             par# (Пуст, Сум);  Зам(#, *)) enddo;  Выб33   endif.
  • построены из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин
  • Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,
  • Нульin - выдает 1, если i-ый аргумент из n аргументов равен (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |i , i >0),
  • Выч1 – вычитает единицу в унарной системе: |j ⇐ |j-1 (| ⇐ ∧, ∧ ⇐ ∧)
  • Какая из этих машин вычисляет функцию f(x) = xx в унарном кодировании, т.е. переводит вход |x в выход |y, где y = xx (пусть 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.
  • Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?

    В теореме 20.5 была доказана неразрешимость проблемы останова:по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть Mh0= {n | ФПn,y (0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе бесконечности множества ее результатов: Minf = {n | множество значений ФПn,y (x) бесконечно}.Какие из следующих функций сводят Mh0 к Minf ?
  • f1(n) = номер программы: ' x:= 0; Пn ; y:= x '.
  • f2(n) = номер программы: 'xn:=x; x:= 0; Пn ; y:= xn '. (здесь переменная xn не входит в П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) = ε ?

    Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T5,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.
  • Постройте логическую схему SP со входами 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) = ε Какие из следующих трех автоматов С1 , С2, С3 распознают гомоморфный образ h(LA)?

    С1 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2, q3, q4, q5, q6, q7}, 0, F1={1,2}, Φ1>,

    С2 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2 }, 0, F2={ 1,2}, Φ2>,

    С3 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2 }, 0, F3={0,1,2}, Φ3>,

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

    Пусть задан ДКА 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) = ε Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный прообраз h-1(LA)?

    С1 = < {0, 1}, { Q, P, R, S }, 0, F1={ R }, Φ1>,

    С2 = < {0, 1}, { Q, P, R, S }, 0, F2={ R }, Φ2>,

    С3 = < {0, 1}, { Q, P, R, S }, 0, F3={ R }, Φ3>,

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

    Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.

    L1 = { wbw | w = an , n > 0 },

    L2 = { bwwb | w = an , n > 0 },

    L3 = { (ab)nam | 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) = 2x2 ?

    Обозначим через 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) ?

    Пусть c2(x, y) = 2x(2y+1) -1 - это функция нумерации пар, а c21(z) и c22(z) - это соответствующие обратные функции такие, что c2(c21(z), c22(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) = c2(F(y), F(y+1)). Так какF(y) = c21(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∧k q ∧ (k > 0) переведут в конфигурацию q'w ?(В текстах программ a – это произвольный символ из Σ, используемые состояния: q, q', l, r, l1, r1 , l2 , r2, l3, r3, l4)

    P1: q ∧ →​ l1 * Л, l1∧→​ r * П, l1a→​ l2a П, l2 a→​ l2 a Л, l2 ∧→​ q'∧ П, r∧ →​ r ∧ П, r *→​ r1 ∧ П, r1 ∧→​ l * Л, l ∧→​ l ∧ Л, l *→​ l1 ∧ Л, r1 a→​ r2a Л, r2 ∧→​ r2∧ Л, r2 *→​ r3∧ П, r3∧→​ r3∧ П, r3 a→​ q'a Н.

    P2: q ∧ →​ l1 * Л, l1∧→​ r * П, l1a→​ l2a П, l2 ∧→​ l2∧ П, l2 *→​ l3∧ Л, l3 ∧→​ l3∧ Л, l3 a→​ q'a Н,r∧ →​ r ∧ П, r *→​ r1 ∧ П, r1 ∧→​ l * Л, l ∧→​ l ∧ Л, l *→​ l1 ∧ Л,r1 a→​ r2a Л, r2 ∧→​ r2∧ Л, r2 *→​ r3∧ П, r3∧→​ r3∧ П, r3 a→​ q'a Н.

    P3: q ∧ →​ l1 * Л, l1∧→​ r * П, l1a→​ l2a П, l2 ∧→​ l2∧ П, l2 *→​ l3∧ Л, l3 ∧→​ l3∧ Л, l3 a→​ l4 a Л,l4 a→​ l4 a Л, l4 ∧→​ q'∧ П, r∧ →​ r ∧ П, r *→​ r1 ∧ П, r1 ∧→​ l * Л, l ∧→​ l ∧ Л, l *→​ l1 ∧ Л,r1 a→​ r2a Л, r2 ∧→​ r2∧ Л, r2 *→​ r3∧ П, r3∧→​ r3∧ П, r3 a→​ q'a Н.

    Пусть машина Тьюринга M построена из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин
  • Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,
  • Большеij - выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn i-ый аргумент xi больше j-ого аргумента xj , иначе выдает 1,
  • с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом:
    M =  Коп# ; par#( par* (Коп*, Пуст ); Зам(*, |), Пуст );if  Больше21  then par#(  Пуст, Сум  ) else  par#(  Пуст, Умн ) endif;Зам(#, *); Выб33.
    Какие результаты она получит на входных данных вида |x1 * |x2при x1 = 2, x2 = 7 и при x1 = 3, x2 = 5, соответственно?

    В доказательстве теоремы 20.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g1, f3), требовалась м.Т. M2, которая переводит конфигурацию вида |y *|x* |u* |z в конфигурацию |y *|x* |u+1* |f(x,u,z) , используя м.Т. Mf, вычисляющую функцию f(x,u,z).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M2 ?
  • P1 = Зам(*,# ); par# ( Пуст, Коп#); par# (Пуст, Пуст, Mf ); Зам( #,* ); Зам( #,* )
  • P2 = Зам(*,# ); par# ( Пуст, Коп#); par# (Пуст, Пуст, Mf ); par# (Пуст, par* (Пуст, +1, Чист), Пуст); Зам( #,* ); Зам(∧, |); Зам( #,| ); par* (Пуст, Пуст, Пуст, Выч1; Выч1)
  • P3 = Зам(*,# ); par# ( Пуст, Коп#); par# (Пуст, par* (Пуст, +1, Чист), Mf ); par* (Зам( #,* ), Пуст, Зам(∧, |); Зам( #,| ); Выч1; Выч1)
  • В этих определениях участвуют следующие простые машины Тьюринга:

  • Копa –копирует вход после разделительного символа a : w ⇐ w a w;
  • Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );
  • Пуст - не изменяет аргумент: w ⇐ w ;
  • Чист – стирает аргумент: w ⇐ ∧ ;
  • Выч1 – вычитает единицу в унарной системе: |j ⇐ |j-1 (| ⇐ ∧, ∧ ⇐ ∧);
  • +1 - прибавляет 1 к аргументу: |x⇐ |x+1
  • Пусть множество A = { (x, y) | y = x2 }, B = { 2n | n ∈ N }.Какие из следующих функций осуществляют сведение A ≤m B ? (В выражениях ниже sqr(y) обозначает целую часть квадратного корня из y, sg(0) =0 иsg(n) = 1 при n > 0).

    В теореме 20.5 была доказана неразрешимость проблемы останова:по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть Mh0= {n | ФПn,y (0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе независимости ее результата от входа: Mconst= {n | существует константа c ∈ N такая, что ФПn,y (x) = c для всех x}.Какие из следующих функций сводят Mh0 к Mconst ?
  • 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( g1, f3), требовалась м.Т. M1, которая переводит конфигурацию вида |x* |y в конфигурацию |y * |x* ∧ *|g(x) , используя м.Т. Mg, вычисляющую функцию g(x).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M1 ?
  • P1 = Коп# ; par# (par* (Чист, Пуст); Зам(*,∧ ) , par* (Пуст ,Чист); Зам(*,∧ ) ); par# (Пуст, Коп* ); par* (Пуст, +1; +1; Зам(|,∧ ); Зам(|,* )); par* (Пуст, Пуст, Mg); Зам( #,* )
  • P2 = Коп# ; par# (par* (Чист, Пуст); Зам(*,∧ ) , par* (Пуст ,Чист); Зам(*,∧ ) ); par# (Пуст, Коп# ); par# (Пуст, Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* )
  • P3 = Коп* ; par* (Чист, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par# (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* )
  • В этих определениях участвуют следующие простые машины Тьюринга:
  • Копa – копирует вход после разделительного символа a : w ⇐ w a w;
  • Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );
  • Пуст – не изменяет аргумент: 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>,

    распознающих языки LA и LB, соответственно. Какой из следующих автоматов является произведением 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

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

    В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=2, j=4. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M24, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M24 ?(В текстах программ 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, ∧> П.
  • Какие из следующих трех конечных автоматовAi = < {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) = ε. Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный прообраз h-1(LA)?

    С1 = < {0, 1}, { Q, P, R, S }, 0, F1={P, S}, Φ1>,

    С2 = < {0, 1}, { Q, S }, 0, F2={ S }, Φ2>,

    С3 = < {0, 1}, { Q, R, S }, 0, F3={ S }, Φ3>,

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

    Пусть структурированная программа 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) =2x2Какую функцию F(x1,x2) задает выражение[f; [h; I21 ] [g; [h; I22 ], I22], I22] ?

    Обозначим через 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) = [2z/z]Чему равно значение F(5)?

    Пусть машина Тьюринга M построена из следующих простых машин Тьюринга:
  • Копa –копирует вход после разделительного символа a : w ⇐ w a w;
  • Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );
  • Сум - складывает два аргумента в унарной системе: |x * |y ⇐ |x+y ;
  • Умн - умножает два аргумента в унарной системе: |x * |y ⇐ |xy ;
  • Пуст - не изменяет аргумент: w ⇐ w
  • с помощью операций последовательного и параллельного применения следующим образом:

    M = Коп# ; par#( Коп* , Коп* ); par#( Умн, Сум); par#( Коп* ; Сум , Пуст ); Зам(#,?); Сум

    Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?

    Какие из следующих трех автоматов С1 , С2 , С3 распознают язык, представляемый регулярным выражением 0(10 +1)*?

    С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1>,

    С2 = < {0,1}, {q, p, r, s }, q, F2={p, r}, Φ2>,

    С3 = < {0,1}, {q, p, r, s, t}, q, F3={ p, r, s}, Φ3>,

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

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

    (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.

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

    Пусть задана УБДР 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) = εКакие из следующих трех автоматов С1, С2, С3 распознают гомоморфный образ h(LA)?

    С1 = < {0, 1}, {0, 1, 2, q1, q2, q3}, 0, F1={2}, Φ1>,

    С2 = < {0, 1}, {0, 1, 2, q1, q2 }, 0, F2={2}, Φ2>,

    С3 = < {0, 1}, {0, 2, (q1, q2), (0,1), (1, 2), !}, 0, F3={2, (1,2)}, Φ3>,

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

    Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.

    L1 = { ww | w = b2anb , n > 0 },

    L2 = { b2anb | n > 0 },

    L3 = { (ab)nanb | n > 0 }.

    Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = x2 + 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) =2x2Какую функцию F(x1,x2) задает выражение[f;[g;I21, I21], I21 , [h; I22 ]] ?

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

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

    Три машины Тьюринга Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы:Какие из этих машин переводят любую начальную конфигурацию вида q an b в заключительную конфигурацию ! b an (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

    Какие из следующих трех НКА С1 , С2 , С3 распознают конкатенацию LA? LB языков, распознаваемых автоматами A и B?С1 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F1={ q2}, Φ1>, С2 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F2={ q2}, Φ2>, С3 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F3={ q2}, Φ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), (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 = { (x2, y2) | x ∈ N , y ∈ N }, B = { n3 | n ∈ N }.Какие из следующих функций осуществляют сведение A ≤m B ? (В выражениях ниже sqr(x) обозначает целую часть квадратного корня из x, sg(0) =0 иsg(n) = 1 при n > 0).