Ответы к контрольной работе: Введение в схемы, автоматы и алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть машина Тьюринга 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) задана примитивной рекурсиейR(1, h(y,z)), где h(y,z) = [2z/z]Чему равно значение F(5)?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть регулярное выражение b(ab)* определяет некоторый язык над алфавитом S={a, 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) задана примитивной рекурсиейR(1, h(y,z)), где h(y,z) = [2z+1/z]Чему равно значение F(3)?

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

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

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

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

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

Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ?(а) рефлексивность: A ≤m A ,(b) симметричность: A ≤m B ⇔ B ≤m A,(с) транзитивность: A ≤m B и B ≤m C ⇐ A ≤m 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 > Л ,

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

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

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

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

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

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

Обозначим через 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) = (x+1)2 ?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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