Ответы на вопросы из коллекции "Введение в схемы, автоматы и алгоритмы"

Пусть множество 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).

• f(x,y) = x3y3
• f(x,y) = (x+2)3 + sg( x2 – sqr(x)2 ) + sg( y2 – sqr(y)2 )
• f(x,y) = 8 + sg( x2 – sqr(x)2 + y2 –sqr(y)2 )
• f(x,y) = sqr(x)3 sqr(y)3
• f(x,y) = (sqr(x) + sqr(y))3

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

• cnaaab
• cbncan+3b
• can+2bnc
• an+2bn
• banbnaaa

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

• a(ba)*
• a*(ba)*
• a*ba
• подходит и 1, и 2
• для этого языка существует только одно регулярное выражение

Пусть задана логическая схема 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.

• только P1
• только P1 и P2
• только P3
• P1, P2 и P3
• только P2 и P3
• только P1 и P3
• только P2

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

• только (b)
• Любой из них
• (b) и (c)
• только (a)
• только (c )
• (a) и (b)
• (a) и (c)

Пусть задана логическая схема 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)

• (1110 0101)
• (1111 0101)
• (1101 1101)
• (0111 1001)
• (1101 0101)

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

• M1 = < {a, b}, {0, 1, 2, 4 ,5}, 0, F1={0, 2, 4, 5}, Φ1> с программой Φ1: 0 b →​ 1, 0 b →​ 2, 0 a →​ 4, 0 a →​ 5, 1 a →​ 2, 1 a →​ 5,1 b →​ 4, 2 a →​ 4, 2 b →​ 2
• M4 = < {a, b}, {0, 1, 2, 4 }, 0, F4={0, 2, 4}, Φ4> с программойΦ4: 0 b →​ 1, 0 b →​ 2, 1 a →​ 2, 1 b →​ 4, 2 a →​ 4, 2 b →​ 2
• M2 = < {a, b}, {0, 1, 2, 4 }, 0, F2={0, 2, 4}, Φ2> с программойΦ2: 0 b →​ 1, 0 b →​ 2, 0 a →​ 4, 1 a →​ 2, 1 b →​ 4, 2 a →​ 4, 2 b →​ 2
• ни один из выше приведенных автоматов M1, M2, M3, M4
• M3 = < {a, b}, {0, 1, 2, 3, 4 }, 0, F3={0, 2, 4}, Φ3> с программойΦ3: 0 b →​ 1, 0 b →​ 2, 0 a →​ 4, 1 a →​ 2, 1 b →​ 4, 2 a →​ 4, 2 b →​ 2, 3 a →​ 4, 3 b →​ 2

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

• все слова четной длины, состоящие из символов {a, b} , которые заканчиваются на a
• все слова над {a, b} , длина которых делится на 3 и каждая третья буква есть a , и слово длины 0
• все слова длины не меньше 12, состоящие из символов {a, b}
• все слова над {a, b}, длина которых делится на 3 и которые заканчиваются на a
• все слова в алфавите {a, b} длины не меньше 3, которые заканчиваются на 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 ]] ?

• 3x12 + 2x22 +x2
• 2x12 + 2x22 +x1
• ни одну из выше перечисленных
• 2x12 x2 + 2x22
• 3x12 + 2x22

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

• только (c )
• (a) и (c)
• всеми
• (a) и (b)
• (b) и (c)
• только (a)
• только (b)

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

• R( 0, [+; [s1 ; [+; I21, I21]], I22 ])
• R( 0, [+; [+; [s1 ; I21], [s1 ; I21]], I22 ])
• R( 0, [+; [+; [s1 ; I21], I21], I22 ])
• R( 0, [+; [+;[+; [s1 ; I21], [s1 ; I21]], [+;I21, I21]], [+;I22 , I22]])
• ни одно из выше перечисленных

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

• только L1
• только L2
• только L3
• L1 и L2
• L1 и L3
• L3 и L2
• все

Пусть задана УБДР 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 эквивалентную ей сокращенную УБДР и укажите ее сложность.

• 6
• 5
• 4
• 3
• 1

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

• 4
• 5
• 6
• 7
• 8

Пусть задана логическая схема 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.

• только P1 и P3
• только P2 и P3
• только P2
• только P3
• только P1
• P1, P2 и P3
• только P1 и P2

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

• только (a)
• только (b)
• только (c )
• (a) и (b)
• (a) и (c)
• (b) и (c)
• Любой из них

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

• f(x) = 2x2 + 2x
• f(x) = x2 + 2x
• f(x) = x2 + x
• f(x) = 2x2 + x
• ни одну из выше перечисленных

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

• 1
• 3
• 8
• 4
• 2
• ни одному из выше перечисленных

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

• ни одну из выше перечисленных
• 2x12 x2+ 4x22 +x2
• 4x12 x22+ 4 x12 x2+x2
• 6x12 + 2x22 x1+x2
• 2x12 x2 (2x2 +1) +x2

Пусть структурированная программа 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 она завершит свою работу?

• σ1(x) = 7, σ1(y) = 5, σ(u) = 7, σ(v) =7
• σ1(x) = 6, σ1(y) = 5, σ(u) = 8, σ(v) =7
• σ1(x) = 6, σ1(y) = 5, σ(u) = 8, σ(v) = 6
• ни в одном из вышеуказанных
• σ1(x) = 7, σ1(y) = 6, σ(u) = 8, σ(v) =6

Пусть структурированная программа 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 она завершит свою работу?

• σ1(x) = 5, σ1(y) = 4, σ1(z) = 5
• σ1(x) = 5, σ1(y) = 5, σ1(z) = 5
• ни в одном из вышеуказанных
• σ1(x) = 6, σ1(y) = 4, σ1(z) = 5
• σ1(x) = 6, σ1(y) = 5, σ1(z) = 6

Пусть задана УБДР 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 эквивалентную ей сокращенную УБДР и укажите ее сложность.

• 5
• 6
• 1
• 3
• 4

Пусть задана логическая схема 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)

• (00011101)
• (01110101)
• (01010101)
• (01011101)
• (01011001)

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

• только P1
• только P2
• только P3
• P1 и P2
• P1 и P3
• P2 и P3
• ни одна

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

• 10
• 8
• 9
• 7
• 6

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

• (a) - 6, (b) - 7
• (a) - 7, (b) - 8
• (a) - 6, (b) - 6
• (a) - 7, (b) - 7
• (a) - 5, (b) - 6

Пусть структурированная программа 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 она завершит свою работу?

• σ1(x) = 5, σ1(y) = 7, σ1(z) = 8
• σ1(x) = 5, σ1(y) = 6, σ1(z) = 7
• σ1(x) = 6, σ1(y) = 7, σ1(z) = 8
• σ1(x) = 5, σ1(y) = 7, σ1(z) = 7
• ни в одном из вышеуказанных

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

• только P1
• только P2
• только P3
• P1 и P2
• все
• ни одна

В теореме 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'.

• только f3
• все
• f1 и f2
• f1 и f3
• только f2
• только f1

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

• f(x,y) = 1 + sg(| x2 – y |)
• f(x,y) = 2x
• f(x,y) = 4 + sg( | x2 – y |)
• f(x,y) = 2x+1 + sg( | x2 – sqr(y)2 |)
• f(x,y) = 2x + | x2 – y |

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

• только P1
• только P2
• только P3
• P2 и P3
• P1 и P3
• ни одна

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

• 9 и 8
• ни один из предыдущих ответов не подходит
• 9 и 15
• 14 и 8
• 14 и 15

Предположим, что в некоторой конфигурации машины Тьюринга 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 Н.

• только P2
• ни одна
• P1 и P2
• P2 и P3
• только P1
• только P3
• P1 и P3

Пусть 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.

• R( 1, [c2; [c22; I22], [+; [c21; I21], [c22; I22]])
• R( 2, [c2; [c22; I22], [s; [+; [c21; I22], [c22; I22]]])
• R( 2, [c2; [c21; I22], [+; [c21; I22], [s;[c22; I22]]])
• R( 1, [c2; [c22; I22], [+; [c21; I22], [s; [c22; I22]]])
• ни одна из выше перечисленных

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

• f(x,y) = minus(y+1, i(x+1))
• f(x,y) = minus(y+1, ix)
• f(x,y) = minus(y+1, (i+1)x)
• f(x,y) = minus(y, ix)
• f(x,y) = minus(y, (i+1)x)

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

• [s1 ; R( 0, [+; [+; [s1 ; I21], I21], I22 ])]
• ни одно из выше перечисленных
• R( 0, [+; [s1 ; [+; I21, I21]], I22 ])
• R( 0, [+; [+; [s1 ; I21], [s1 ; I21]], I22 ])
• R( 0, [+; [+;[+; [s1 ; I21], [s1 ; I21]], [+;I21, I21]], [+;I22 , I22]])

Пусть структурированная программа 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 она завершит свою работу?

• σ1(x) = 7, σ1(y) = 6, σ1(z) = 2, σ(u) = 5, σ(v) =6
• ни в одном из вышеуказанных
• σ1(x) = 6, σ1(y) = 7, σ1(z) = 2, σ(u) = 5, σ(v) =6
• σ1(x) = 6, σ1(y) = 5, σ1(z) = 2, σ(u) = 5, σ(v) =7
• σ1(x) = 8, σ1(y) = 7, σ1(z) = 2, σ(u) = 5, σ(v) =6

Пусть структурированная программа 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 она завершит свою работу?

• σ1(x) = 7, σ1(y) = 6, σ1(z) = 5, σ(u) = 6, σ(v) =8
• σ1(x) = 8, σ1(y) = 7, σ1(z) = 5, σ(u) = 6, σ(v) =7
• σ1(x) = 6, σ1(y) = 7, σ1(z) = 5, σ(u) = 6, σ(v) =7
• σ1(x) = 6, σ1(y) = 6, σ1(z) = 5, σ(u) = 6, σ(v) =7
• ни в одном из вышеуказанных

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

• все
• L1 и L3
• только L3
• только L1
• L1 и L2
• только L2
• L3 и L2

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

• (01 )*1*01*
• (1 +01)*(0 +1)
• (1*01*)*
• (1 + 01)* (ε + 0)
• 1*01(1 + 01)*( ε + 0)

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

• все слова нечетной длины, состоящие из символов {a, b}
• все слова над {a, b}, которые начинаются и кончаются одним и тем же символом
• все слова над {a, b} , длина которых делится на 2, включая слово длины 0
• все слова в алфавите {a, b} длины не меньше 2 и пустое слово
• Ответ 4. Все слова длины не меньше 8, состоящие из символов {a, b}

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

• L = {a, b, ba, bb, bba, aba, abb, abba, abba, abab}
• L = {ε, a, b, ba, bb, ab, bab, aba, abba, abb, abba, abbb}
• L = {a, ab, abba, aa, aba, abbaa, abb, abbab, abbaba}
• L = {ε, a, b, ba, bb, bba, ab, aba, abba , baa, bab, baba}
• L = {ε, a, b, ba, bb, bba, aba, abbaa, ab, abb, abbab, abbaba}

Пусть задан недетерминированный конечный автомат (без пустых переходов)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 →​∅

• только M1
• M2 и M3
• только M3
• M1 и M3
• только M2
• ни один
• M1 и M2

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

• M4 = < {a, b}, {0, 1, 2, 3, 5}, 0, F4={3, 5}, Φ4> с программойΦ4: 0 b →​ 1, 1 a →​ 2, 1 b →​ 3, 2 a →​ 3, 2 b →​ 1, 3 a →​ 5, 3 a →​ 3, 3 b →​ 1, 5 a →​ 3,5 b →​ 1
• M3 = < {a, b}, {0, 1, 2, 3, 5 }, 0, F3={5}, Φ3> с программойΦ3: 0 b →​ 1, 1 a →​ 2, 1 b →​ 3, 2 a →​ 3, 2 b →​ 1, 3 a →​ 5, 3 b →​ 1, 5 a →​ 3, 5 b →​ 1
• M1 = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F1={3, 4, 5}, Φ1> с программойΦ1: 0 b →​ 1, 1 a →​ 2, 1 b →​ 3, 1 b →​ 4, 2 a →​ 3, 2 b →​ 1, 3 a →​ 5, 3 a →​ 3, 3 b →​ 1, 4 a →​ 5, 5 a →​ 3, 5 b →​ 1
• M2 = < {a, b}, {0, 1, 3, 5 }, 0, F2={3, 5}, Φ2> с программойΦ2: 0 b →​ 1, 1 a →​ 2, 1 b →​ 3, 2 a →​ 3, 2 b →​ 1, 3 a →​ 5, 3 a →​ 3, 5 a →​ 3
• ни один из выше приведенных автоматов M1, M2, M3, M4

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

• 6
• 5
• 3
• 4
• 2

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

• 10
• 8
• 9
• 11
• 7

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

• все слова в алфавите {0, 1}, начинающиеся на 0, с длиной > 5
• все слова в алфавите {0, 1}, начинающиеся на 0 и содержащие подслово 1111, в которых единицы идут блоками четной длины
• все слова нечетной длины в алфавите {0, 1}, начинающиеся на 0 и содержащие подслово 1111, в которых на нечетных местах стоят нули
• все слова в алфавите {0, 1}, начинающиеся на 0, в которых на четных местах стоят нули и которые содержат подслово 1111
• все слова в алфавите {0, 1}, начинающиеся на 0, в которых единицы идут блоками четной длины

В теореме 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'.

• только f1
• только f2
• только f3
• f1 и f2
• f1 и f3
• все

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

• 3
• 4
• 6
• 5
• 2

Пусть структурированная программа 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 она завершит свою работу?

• σ1(x) = 4, σ1(y) = 5, σ1(z) = 4, σ(u) = 4, σ(v) = 5
• σ1(x) = 4, σ1(y) = 5, σ1(z) = 4, σ(u) = 4, σ(v) =6
• σ1(x) = 4, σ1(y) = 5, σ1(z) = 5, σ(u) = 4, σ(v) =6
• ни в одном из вышеуказанных
• σ1(x) = 4, σ1(y) = 5, σ1(z) = 6, σ(u) = 4, σ(v) =6

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

• L = {aa, aba, abbaa, ab, abb, abbab, abbaba}
• L = {aa, aba, abbaa, ab, abb, abbab, abbaba}
• L = {a, ab, abba, aa, aab, aba, abbaa, abb, abbab, abbaba}
• L = {aa, aba, abbaa, ab, abb, abbab, abbaba}
• L = {a, ab, abba, aa, aba, abbaa, abb, abbab, abbaba}

Приведенные ниже машины Тьюринга 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) ?

• M1
• M2
• M3
• M4
• ни одна

Пусть язык 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

• только W1
• W1 и W3
• все
• только W2
• только W3
• W1 и W2
• W2 и W3

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

• P1 и P3
• только P1
• только P3
• только P2
• P1 и P2
• ни одна
• P2 и P3

Пусть задан недетерминированный конечный автомат (без пустых переходов)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 →​ pM2 = < {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 →​ ∅

• только M1
• ни один
• только M3
• M1 и M3
• M1 и M2
• M2 и M3
• только M2

Приведенные ниже машины Тьюринга 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?

• M2
• M4
• ни одна
• M3
• M1

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

• b*ab*
• для этого языка существует только одно регулярное выражение
• a(ba)*
• подходит и 1, и 2
• (ba)*b

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

• f(x) = 2x2 + 2x
• f(x) = 2x2 + x
• ни одну из выше перечисленных
• f(x) = x2 + x
• f(x) = x2 + 2x

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

• 64
• 2
• ни одному из выше перечисленных
• 8
• 32
• 16

Пусть язык 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

• W1 и W2
• W2 и W3
• только W1
• только W3
• все
• только W2
• W1 и W3

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

• (a) - 4, (b) - 5
• (a) - 6, (b) - 7
• (a) - 6, (b) - 6
• (a) - 5, (b) - 6
• (a) - 4, (b) - 6

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

• P1 и P3
• P2 и P3
• только P1
• все
• только P2
• только P3
• P1 и P2

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

• только (a)
• (b) и (c)
• только (b)
• Любой из них
• (a) и (b)
• только (c )
• (a) и (c)

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

• f(x,y) = (x+1)3 + sg( | x2 – sqr(y)2 |)
• f(x,y) = x3
• f(x,y) = (x+1)3 + | x2 – y |
• f(x,y) = x3 + sg( | x2 – sqr(y)2 |)
• f(x,y) = 1 + sg(| x2 – y |)

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

• только (a)
• только (b)
• только (c )
• (a) и (b)
• (a) и (c)
• (b) и (c)
• всеми

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

• только P3
• только P1
• P1 и P3
• P2 и P3
• только P2
• P1 и P2
• ни одна

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

• ни одна
• только P3
• только P2
• все
• только P1
• P1 и P2

Приведенные ниже машины Тьюринга 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?

• M1
• ни одна
• M4
• M3
• M2

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

• 32 и 6
• ни один из предыдущих ответов не подходит
• 32 и 5
• 12 и 5
• 12 и 6

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

• f(x) = x2 + x
• f(x) = x2 + 2x
• ни одну из выше перечисленных
• f(x) = 2x2 + x
• f(x) = 2x2 + 2x

В конструкции машины Тьюринга со стандартными заключительными конфигурациями нужна служебная машина Тьюринга, назовем ее 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' Н.

• P1 и P3
• только P2
• только P1
• только P3
• P2 и P3
• ни одна
• P1 и P2

Пусть 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.

• R( 2, [c2; [c22; I22], [×; [c21; I21], [c22; I22]])
• R( 9, [c2; [c22; I22], [×; [c21; I22], [c22; I22]])
• R( 2, [c2; [c22; I22], [×; [c21; I21], [c22; I22]])
• ни одна из выше перечисленных
• R( 9, [c2; [c21; I22], [×; [c21; I22], [c22; I22]])

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

• f(x,y) = minus(x+2, 2(y+1))
• f(x,y) = minus(x+1, 2y)
• f(x,y) = minus(x+2, 2y)
• f(x,y) = minus(2y, x+1)
• f(x,y) = minus(x+1, 2(y+1))

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

• [s1 ; R( 0, [+; [+; [s1 ; I21], I21], I22 ])]
• R( 1, [+; [+;[+; [s1 ; I21], [s1 ; I21]], [+;I21, I21]], [+;I22 , I22]])
• ни одно из выше перечисленных
• R( 1, [+; [s1 ;[ s1 ;[ s1 ;[+; I21, I21]]]], I22 ])
• R( 1, [+; [+; [s1 ; I21], [s1 ; I21]], I22 ])

Пусть структурированная программа 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она завершит свою работу?

• σ1(x) = 7, σ1(y) = 6, σ(u) = 8, σ(v) =6
• σ1(x) = 6, σ1(y) = 5, σ(u) = 8, σ(v) = 6
• σ1(x) = 7, σ1(y) = 5, σ(u) = 7, σ(v) = 7
• ни в одном из вышеуказанных
• σ1(x) = 6, σ1(y) = 5, σ(u) = 7, σ(v) = 6

Пусть структурированная программа 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 она завершит свою работу?

• σ1(x) = 9, σ1(y) = 6, σ1(z) = 6
• σ1(x) = 8, σ1(y) = 5, σ1(z) = 7
• σ1(x) = 7, σ1(y) = 6, σ1(z) = 6
• σ1(x) = 9, σ1(y) = 6, σ1(z) = 7
• ни в одном из вышеуказанных

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

• только P1
• только P2
• только P3
• P1 и P2
• P1 и P3
• P2 и P3
• все

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

• L3 и L2
• только L2
• только L1
• только L3
• L1 и L3
• все
• L1 и L2

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

• cnbbbaaabb
• banbn+4aaa
• cbn+2
• bn+2canc
• bncanbbb

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

• все слова в алфавите {0, 1}, начинающиеся на 0101, с длиной > 7
• все слова четной длины в алфавите {0, 1}, начинающиеся на 0101
• все слова четной длины в алфавите {0, 1}, начинающиеся на 0101, в которых на четных местах стоят единицы и которые содержат подслово 1111
• все слова в алфавите {0, 1}, начинающиеся на 0101, в которых на четных местах стоят единицы и которые содержат подслово 1111
• ни одна из предыдущих

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

• (1 +01)*00(0 +1)*
• (1 + 01)*00(01 +1)*
• (1 +00)*
• (0 + 1)*10*1(0+1)*
• 1*00(0 + 10)*(0+1)*

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

• все слова в алфавите {a, b} длины не меньше 3 и пустое слово
• все слова над {a, b} , длина которых делится на 3, включая слово длины 0
• все слова длины не меньше 24, состоящие из символов {a, b}
• все слова четной длины, состоящие из символов {a, b}
• все слова над {a, b}, которые начинаются и кончаются одним и тем же символом

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

• 11
• 8
• 9
• 7
• 10

Пусть задана УБДР 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 эквивалентную ей сокращенную УБДР и укажите ее сложность.

• 1
• 3
• 4
• 5
• 6

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

• n
• 2n
• 2(n+1)
• 3(n-1)
• 3n

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

• 4
• 2
• 3
• 6
• 5

Пусть задана логическая схема 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.

• P1, P2 и P3
• только P1 и P3
• только P2
• только P3
• только P2 и P3
• только P1
• только P1 и P2

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

• L = {a, ab, abba, aa, aba, abbaa, abb, abbab, abbaba}
• L = {a, b, ba, bb, bba, aba, abb, abbab, abbaa, abbaba}
• L = {a, b, ba, bb, ab, abba, aab, aba, abbaa, abb, abbab, abbaba}
• L = {ε, bb, ba, aba, abbaa, ab, abb, abbab, abbaba}
• L = {a, b, ba, bb, bba, aba, abbaa, ab, abb, abbab, abbaba}

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

• ни одну из выше перечисленных
• 2x1 - 2x2 -2
• 2x1 x2 - 4x2 -2
• 4x12 - 4x2 -1
• 2x1 - 4x2 -2

Пусть 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

• R( 5, [c2; [c22; I22], [+; [c21; I22], [c22; I22]])
• R( 2, [c2; [c22; I22], [+; [c21; I21], [c22; I22]])
• ни одна из выше перечисленных
• R( 5, [c2; [c21; I22], [+; [c21; I22], [c22; I22]])
• R( 1, [c2; [c22; I22], [+; [c21; I21], [c22; I22]])

В теореме 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'.

• f1 и f3
• только f2
• все
• f1 и f2
• только f1
• только f3

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

• все слова четной длины в алфавите {0, 1}, заканчивающиеся на 10, в которых на четных местах стоят нули
• все слова в алфавите {0, 1}, заканчивающиеся на 10, с длиной > 5
• все слова четной длины в алфавите {0, 1}, содержащие подслово 0000
• все слова в алфавите {0, 1}, заканчивающиеся на 10, в которых на нечетных местах стоят нули и которые содержат подслово 0000
• все слова в алфавите {0, 1}, заканчивающиеся на 10, в которых на четных местах стоят нули и которые содержат подслово 0000

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

• для этого языка существует только одно регулярное выражение
• (b*+a)*
• подходит и 1, и 2
• (a +b)*
• b*ab*

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

• 12
• 14
• 17
• 15
• 11

Пусть задана логическая схема 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)

• (0001 0101)
• (0111 0100)
• (1010 0101)
• (0011 0100)
• (0011 0110)

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

• bn+2canc
• ancbn+3c
• bcbn+4anaca
• canbn+3c
• bbbcnaabb

Пусть задан недетерминированный конечный автомат (без пустых переходов)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 →​ pqM2 = < {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 →​∅

• только M1
• M2 и M3
• M1 и M3
• только M2
• M1 и M2
• ни один
• только M3

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

• только P1
• все
• только P2
• P1 и P3
• P2 и P3
• P1 и P2
• только P3

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

• 9 и 12
• 18 и 8
• ни один из предыдущих ответов не подходит
• 9 и 8
• 18 и 12

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

• (a) - 6, (b) - 6
• (a) - 6, (b) - 7
• (a) - 5, (b) - 7
• (a) - 5, (b) - 6
• (a) - 7, (b) - 7