Главная / Алгоритмы и дискретные структуры / Введение в схемы, автоматы и алгоритмы

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

Правильные ответы выделены зелёным цветом.
Все ответы: Краткий начальный курс по таким дискретным структурам как схемы, конечные автоматы и алгоритмы.

В доказательстве теоремы 10.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g¹, f³), требовалась м.Т. M₁, которая переводит конфигурацию вида |^x* |^y в конфигурацию |^y * |^x* ∧ *|^g(x) , используя м.Т. M_g, вычисляющую функцию g(x). Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M₁ ?

P1 = Коп_#; par_# (par_* (Чист, Пуст); Зам(*,∧ ) ,  par_* (Пуст ,Чист); Зам(*,∧ ) ); par_# (Пуст, Коп_* ); par_* (Пуст, +1; +1; Зам(|,∧ ); Зам(|,* ));         par_* (Пуст,  Пуст, M_g); Зам( #,* )

P2 = Коп_#; par_# (par_* (Чист, Пуст); Зам(*,∧ ) ,  par_* (Пуст ,Чист); Зам(*,∧ ) ); par_# (Пуст, Коп_# ); par_# (Пуст, Пуст,  M_g ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* )

P3 = Коп_*; par_* (Чист, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par_# (Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* )

В этих определениях участвуют следующие простые машины Тьюринга:

Коп_a – копирует вход после разделительного символа a : w ⇐ w a w;

Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );

Пуст – не изменяет аргумент: w ⇐ w ;

Чист – стирает аргумент: w ⇐ ∧ ;

+1 – прибавляет 1 к аргументу: |^x ⇐ |^x+1

(1) только P1

(2) только P2

(3) только P3

(4) P1 и P2

(5) все

(6) ни одна

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

(1) (X ∨ ¬Z) ∧((Y ∨ ¬X) ∧¬Z)

(2) (¬X ∨ ¬Z) ∧((Y ∨ ¬X) ∧¬Z)

(3) (¬X ∨ ¬Z) ∧(( X ∨ Y) ∧¬Z)

(4) (¬X ∨ ¬Z) ∨ (( X∧ Y) ∧¬Z)

(5) (( X∧ Y) ∧¬Z)) ∨ ¬Z ∨ ¬ X

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

(1) (00011101)

(2) (01010101)

(3) (01011001)

(4) (01010001)

(5) (01011101)

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

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

(1) 100101

(2) 000001

(3) 100011

(4) 100001

(5) никакое

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

(1) L = {a, ab, abba, aa, aab, aba, abbaa, abb, abbab, abbaba}

(2) L = {a, ab, abba, aa, aba, abbaa, abb, abbab, abbaba}

(3) L = {aa, aba, abbaa, ab, abb, abbab, abbaba}

(4) L = {aa, aba, abbaa, ab, abb, abbab, abbaba}

(5) L = {aa, aba, abbaa, ab, abb, abbab, abbaba}

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

(1) все слова в алфавите {0, 1}, начинающиеся на 0101, с длиной > 7

(2) все слова четной длины в алфавите {0, 1}, начинающиеся на 0101

(3) все слова четной длины в алфавите {0, 1}, начинающиеся на 0101, в которых на четных местах стоят единицы и которые содержат подслово 1111

(4) все слова в алфавите {0, 1}, начинающиеся на 0101, в которых на четных местах стоят единицы и которые содержат подслово 1111

(5) ни одна из предыдущих

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

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 все

(1) только P1

(2) только P2

(3) только P3

(4) P1 и P2

(5) P1 и P3

(6) P2 и P3

(7) все

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

(1) 2x₁² + 2x₂² +x₁

(2) 3x₁² + 2x₂² +x₂

(3) 2x₁² x₂+ 2x₂²

(4) 3x₁² + 2x₂²

(5) ни одну из выше перечисленных

Пусть машина Тьюринга M имеет алфавит ленты Σ={ ∧, 0, 1}, алфавит состояний Q= {q, p, r, !}, начальное состояние q, заключительное состояние ! и программу Ф:

\begin{array}{lll}
q\ 0 \rightarrow q\ 0\ П & p\ 0 \rightarrow p\ 1\ Л  &  r\ 0 \rightarrow r\ 0\ Л
q\ 1 \rightarrow q\ 1\ П & p\ 1 \rightarrow r\ 0\ Л  & r\ 1 \rightarrow r\ 1\ Л 
q \wedge \rightarrow p\ \wedge Л  &  p \wedge \rightarrow ! \wedge П  & r \wedge \rightarrow ! \wedge П
\end{array}

В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации q 1010 ?

(1) ! 0101

(2) ! 0110

(3) ! 1001

(4) ! 1110

(5) ни в одну из выше указанных

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

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

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

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

(1) только P₁

(2) только P₂

(3) только P₃

(4) P₁ и P₂

(5) P₁ и P₃

(6) P₂ и P₃

(7) ни одна

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

(1) только S1

(2) только S2

(3) только S3

(4) S1 и S3

(5) S2 и S3

(6) S1 и S2

(7) ни одна

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

(1) (X1 ∧ X3) ∨ (X2 ∧¬X3)

(2) (X1 ∧ ¬X2 ∧ X3) ∨ (X2 ∧ X3))

(3) (X1 ∨ X2) ∧(X2 ∧X3)

(4) (X1 ∧ X3) ∨ (X2∧ X3)

(5) ¬X2 ∧ X3

(6) (X1 ∧ X3) ∨ (¬X1 ∧¬X2 ∧ X3)

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

где

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

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

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

(1) все слова в алфавите {a, b} длины не меньше 3 и пустое слово

(2) все слова над {a, b}, которые начинаются и кончаются одним и тем же символом

(3) все слова четной длины, состоящие из символов {a, b}

(4) все слова над {a, b} , длина которых делится на 3, включая слово длины 0

(5) все слова длины не меньше 24, состоящие из символов {a, b}

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

W1 = 21112, W2 = 20101012, W3 = 00211011

(1) только W1

(2) только W2

(3) только W3

(4) W1 и W2

(5) W1 и W3

(6) W2 и W3

(7) все

Пусть структурированная программа 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) σ1(x) = 9, σ1(y) = 6, σ1(z) = 6

(2) σ1(x) = 8, σ1(y) = 5, σ1(z) = 7

(3) σ1(x) = 7, σ1(y) = 6, σ1(z) = 6

(4) σ1(x) = 9, σ1(y) = 6, σ1(z) = 7

(5) ни в одном из вышеуказанных

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

(1) R( 0, [+; [s¹ ; [+; I²₁, I²₁]], I²₂ ])

(2) R( 0, [+; [+; [s¹ ; I²₁], [s¹ ; I²₁]], I²₂ ])

(3) R( 0, [+; [+; [s¹ ; I²₁], I²₁], I²₂ ])

(4) R( 0, [+; [+;[+; [s¹ ; I²₁], [s¹ ; I²₁]], [+;I²₁, I²₁]], [+;I²₂ , I²₂]])

(5) ни одно из выше перечисленных

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

Какие из этих машин переводят любую начальную конфигурацию вида q aⁿ b в заключительную конфигурацию ! b aⁿ (n ≥ 0 )?

(1) только M₁

(2) только M₂

(3) только M₃

(4) M₁ и M₂

(5) M₁ и M₃

(6) M₂ и M₃

(7) ни одна

Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ?

(а) рефлексивность: A ≤m A ,

(b) симметричность: A ≤m B ⇔ B ≤m A,

(с) транзитивность: A ≤m B и B ≤m C ⇐ A ≤m C .

(1) только (a)

(2) только (b)

(3) только (c )

(4) (a) и (b)

(5) (a) и (c)

(6) (b) и (c)

(7) всеми

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

(1) (00011101)

(2) (01010101)

(3) (01011001)

(4) (01110101)

(5) (01011101)

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

(1) только D1

(2) только D2

(3) только D3

(4) D1 и D2

(5) D2 и D3

(6) D1 и D3

(7) все

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

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

(1) только W

(2) только V

(3) только U

(4) W и V

(5) V и U

(6) W и U

(7) все

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

(1) (0 + 10)*11(10 +0)*

(2) (0 +10)*11(0 +1)*

(3) (0 + 1)*10*1(0+1)*

(4) 0*11(0 + 10)*(0+1)*

(5) (0 +11)*

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

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

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

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

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

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

Пусть структурированная программа 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) σ1(x) = 8, σ1(y) = 7, σ1(z) = 5, σ(u) = 6, σ(v) =7

(2) σ1(x) = 6, σ1(y) = 7, σ1(z) = 5, σ(u) = 6, σ(v) =7

(3) σ1(x) = 7, σ1(y) = 6, σ1(z) = 5, σ(u) = 6, σ(v) =8

(4) σ1(x) = 6, σ1(y) = 6, σ1(z) = 5, σ(u) = 6, σ(v) =7

(5) ни в одном из вышеуказанных

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

(целая часть квадратного корня из x) ?

(1) f(x,y) = minus(y², x)

(2) f(x,y) = minus(x,y²)

(3) f(x,y) = minus((x+1),y²)

(4) f(x,y) = minus((x+1),(y+1)²)

(5) f(x,y) = minus(x,(y+1)²)

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

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

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

P3: q a → q a П , q ∧ → s * Л, s b → s b Л, s ∧ → p ∧ П, p a → p^a ∧П, p * → q’ * П, p^a b → p^a b П, p^a ∧ → s a Л.

(1) только P₁

(2) только P₂

(3) только P₃

(4) P₁ и P₂

(5) P₁ и P₃

(6) P₂ и P₃

(7) ни одна

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

(1) f(x,y) = x³

(2) f(x,y) = x³ + sg( | x² – sqr(y)² |)

(3) f(x,y) = (x+1)³ + sg( | x² – sqr(y)² |)

(4) f(x,y) = (x+1)³ + | x² – y |

(5) f(x,y) = 1 + sg(| x² – y |)

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

(1) только P1

(2) только P2

(3) только P3

(4) только P1 и P3

(5) только P2 и P3

(6) только P1 и P2

(7) P1, P2 и P3

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

(1) 1

(2) 3

(3) 4

(4) 5

(5) 6

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

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

(1) все слова, начинающиеся на b и заканчивающиеся на a

(2) все слова, начинающиеся на b и заканчивающиеся на a , в которых буквы b идут блоками четной длины

(3) все слова, начинающиеся на b и заканчивающиеся на a , в которых буквы b идут блоками нечетной длины

(4) все слова, в которых буквы b идут блоками нечетной длины

(5) все слова, начинающиеся блоком букв b нечетной длины, после которого стоит буква a

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

(1) a(ba)*

(2) a*(ba)*

(3) a*ba

(4) подходит и 1, и 2

(5) для этого языка существует только одно регулярное выражение

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

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

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

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

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

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁и C₂

(5) C₁и C₃

(6) C₂и C₃

(7) все

Пусть структурированная программа 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) σ1(x) = 8, σ1(y) = 7, σ1(z) = 2, σ(u) = 5, σ(v) =6

(2) σ1(x) = 6, σ1(y) = 7, σ1(z) = 2, σ(u) = 5, σ(v) =6

(3) σ1(x) = 7, σ1(y) = 6, σ1(z) = 2, σ(u) = 5, σ(v) =6

(4) σ1(x) = 6, σ1(y) = 5, σ1(z) = 2, σ(u) = 5, σ(v) =7

(5) ни в одном из вышеуказанных

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

(1) 1

(2) 2

(3) 4

(4) 8

(5) 3

(6) ни одному из выше перечисленных

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

(1) f(x) = 2x² + 2x

(2) f(x) = x² + x

(3) f(x) = 2x² + x

(4) f(x) = x² + 2x

(5) ни одну из выше перечисленных

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

(a) x := x+1, (b) x := 0, (c) x := y.

(1) только (a)

(2) только (b)

(3) только (c )

(4) (a) и (b)

(5) (a) и (c)

(6) (b) и (c)

(7) Любой из них

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

Y = ¬X1;

Z = ¬X2;

U = ¬X3;

V = X1 ∧ X2;

Z = Y ∧ Z;

W= Y ∧ X2;

Z = Z ∧ W ;

V = V ∧ U ;

Z = Z ∨ V.

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

(1) 2

(2) 3

(3) 4

(4) 5

(5) 6

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

a) x1 < x2 < x3 < x4 и

b) x1 < x3 < x2 < x4.

Определите сложности этих двух схем.

(1) (a) - 7, (b) - 8

(2) (a) - 6, (b) - 6

(3) (a) - 5, (b) - 6

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

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

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

(1) только A₁

(2) только A₂

(3) только A₃

(4) A₁ и A₂

(5) A₁ и A₃

(6) A₂ и A₃

Заданы два НКА:

A =< {a, b}, {0, 1, 2, 3}, 0, {2}, Φ_A > с программой Φ_A: 0 a → 1, 0 a → 2, 0 b → 0, 1 a → 2, 1 b → 1, 2 a → 3, 2 b → 2, 3 a → 3, 3b → 3 и

B =< {a, b}, {q0, q1, q2}, q0, {q2}, Φ_B > с программой Φ_B: q0 a → q1, q1 b → q0, q1 a → q2, q2 b → q1

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

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

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

(1) cⁿaaab

(2) baⁿbⁿaaa

(3) aⁿ⁺²bⁿ

(4) caⁿ⁺²bⁿc

(5) cbⁿcaⁿ⁺³b

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

(1) только П1

(2) только П2

(3) только П3

(4) П1 и П2

(5) П1 и П3

(6) П2 и П3

(7) все

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

(1)

(2)

(3)

(4)

(5) ни одно из выше перечисленных

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

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

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

с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом: M = Коп_# ; par_#( par_* (Коп_*, Пуст ); Зам(*, |), Пуст ); if Больше₁₂ then par_#( Пуст, Сум ) else par_#( Пуст, Умн ) endif; Зам(#, *); Выб_33. Какие результаты она получит на входных данных вида |^x1 * |^x2 при x₁= 3, x₂= 6 и при x₁= 2, x₂= 6, соответственно?

(1) 9 и 8

(2) 18 и 12

(3) 9 и 12

(4) 18 и 8

(5) ни один из предыдущих ответов не подходит

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

f1(n) = номер программы: ' x:= 0; П_n ; y:= 0'.

f2(n) = номер программы: 'П_n ; y:= x'.

f3(n) = номер программы: ' x:= 0; П_n ; y:= 0; y:= y+1'.

(1) только f1

(2) только f2

(3) только f3

(4) f1 и f2

(5) f1 и f3

(6) все

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

(1) n

(2) 2n

(3) 2(n+1)

(4) 3(n-1)

(5) 3n

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

(1) 10

(2) 8

(3) 9

(4) 11

(5) 7

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

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

C = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2), (p,3)}, (q,0), F={(p,3)}, Φ_C >,

D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,1), (p,2)}, Φ_D >,

(1) C, L_C = L_A \ L_B

(2) C, L_C= L_A ∩ L_B

(3) C, L_C = L_B \ L_A

(4) D, L_D = L_A \ L_B

(5) D, L_D = L_A ∩ L_B

(6) D, L_D = L_A ∪ L_B

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

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

С₂ = < {0,1}, {q, p, r, s }, q, F₂={ s}, Φ₂> ,

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

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

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

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

L1 = { a²bⁿa² | n > 0 },

L2 = { ww | w = a²bⁿa² , n > 0 },

L3 = { wv | w = a²bⁿa² , v = b²a^mb² для произвольных n,m > 0 }.

(1) только L1

(2) только L2

(3) только L3

(4) L1 и L2

(5) L1 и L3

(6) L3 и L2

(7) все

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

(1) только П1

(2) только П2

(3) только П3

(4) П1 и П2

(5) П1 и П3

(6) П2 и П3

(7) все

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

(1) R( 5, [c₂; [c₂₁; I²₂], [+; [c₂₁; I²₂], [c₂₂; I²₂]])

(2) R( 1, [c₂; [c₂₂; I²₂], [+; [c₂₁; I²₁], [c₂₂; I²₂]])

(3) R( 2, [c₂; [c₂₂; I²₂], [+; [c₂₁; I²₁], [c₂₂; I²₂]])

(4) R( 5, [c₂; [c₂₂; I²₂], [+; [c₂₁; I²₂], [c₂₂; I²₂]])

(5) ни одна из выше перечисленных

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

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

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

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

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

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

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

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

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

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

(1) M1

(2) M2

(3) M3

(4) M4

(5) ни одна

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

(1)

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

(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

(3)

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

(4)

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

(5) ни один из выше приведенных автоматов M1, M2, M3, M4

Пусть задан недетерминированный конечный автомат (без пустых переходов) M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программой Φ: q 0 → p, q 0 → s, p 0 → q, p 0 → s, p 1 → p, s 1 → p Какие из следующих трех ДКА эквивалентны M?

M1 = < {0, 1}, {q, p, ps, qs}, q, F1={p, ps}, Φ1> с программой Φ1: q 0 → ps, q 1 → p, p 0 → qs, p 1 → p, ps 0 → qs, ps 1 → p, qs 0 → ps, qs 1 → p

M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F2={p, ps, pq, qps}, Φ2> с программой Φ2: q 0 → ps, q 1 → p, p 0 → qs, p 1 → p, s 0→ ∅, s 1→ p, ps 0 → qs, ps 1 → p, qs 0 → ps, qs 1 → p, qp 0 → ps, qp 1 → p, qps 0 → qps, qps 1 → p, ∅ 0 →∅, ∅ 1 →∅.

M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F3={ p, ps, pq, qps }, Φ3> с программой Φ3: q 0 → ps, q 1 → p, p 0 → qs, p 1 → p, s 1→ p, ps 0 → qs, ps 1 → p, qs 0 → qps, qs 1 →qps, qp 0 → ps, qp 1 → p, qps 0 → qps, qps 1 → p. ∅ 0 →∅, ∅ 1 → ∅

(1) только M1

(2) только M2

(3) только M3

(4) M1 и M2

(5) M1 и M3

(6) M2 и M3

(7) ни один

В доказательстве теоремы 20.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g¹, f³), требовалась м.Т. M₂, которая переводит конфигурацию вида |^y *|^x* |^u* |^z в конфигурацию |^y *|^x* |^u+1* |^f(x,u,z) , используя м.Т. M_f, вычисляющую функцию f(x,u,z). Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M₂ ?

P1 = Зам(*,# ); par_# ( Пуст, Коп_#); par_# (Пуст, Пуст, M_f ); Зам( #,* ); Зам( #,* )

P2 = Зам(*,# ); par_# ( Пуст, Коп_#);   par_# (Пуст, Пуст, M_f );  par_# (Пуст,  par_* (Пуст, +1, Чист), Пуст); Зам( #,* ); Зам(∧, |); Зам( #,| ); par_* (Пуст, Пуст,  Пуст, Выч1; Выч1)

P3 = Зам(*,# ); par_# ( Пуст, Коп_#);  par_# (Пуст, par_* (Пуст, +1, Чист), M_f ); par_* (Зам( #,* ), Пуст, Зам(∧, |); Зам( #,| ); Выч1; Выч1)

В этих определениях участвуют следующие простые машины Тьюринга:

Коп_a –копирует вход после разделительного символа a : w ⇐ w a w;

Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );

Пуст - не изменяет аргумент: w ⇐ w ;

Чист – стирает аргумент: w ⇐ ∧ ;

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

+1 - прибавляет 1 к аргументу: |^x⇐ |^x+1

(1) только P1

(2) только P2

(3) только P3

(4) P2 и P3

(5) P1 и P3

(6) ни одна

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

(1) (X ∨ ¬Z) ∧((Y ∨ ¬X) ∧¬Z)

(2) (¬X ∨ Y ∨ ¬Z) ∧((X ∨ Y) ∧(Y ∨ Z))

(3) ((X ∨ Y) ∧(Y ∨ Z)) ∧(( X ∨ Y) ∧¬Z)

(4) ((X ∨ Y) ∧(Y ∨ Z)) ∨ ((¬ X∨ Y) ∧Z)

(5) (¬ X∨ (Y ∨ Z)) ∧ ( Z ∨ X)

(1) (01010111)

(2) (01010101)

(3) (01011011)

(4) (01010011)

(5) (01011101)

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

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

(1) 010001

(2) 010000

(3) 100011

(4) 000001

(5) никакое

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

(1) L = {a, b, ba, bb, ab, abba, aab, aba, abbaa, abb, abbab, abbaba}

(2) L = {a, ab, abba, aa, aba, abbaa, abb, abbab, abbaba}

(3) L = {ε, bb, ba, aba, abbaa, ab, abb, abbab, abbaba}

(4) L = {a, b, ba, bb, bba, aba, abb, abbab, abbaa, abbaba}

(5) L = {a, b, ba, bb, bba, aba, abbaa, ab, abb, abbab, abbaba}

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

(1) все слова в алфавите {0, 1}, заканчивающиеся на 10, с длиной > 5

(2) все слова четной длины в алфавите {0, 1}, содержащие подслово 0000

(3) все слова четной длины в алфавите {0, 1}, заканчивающиеся на 10, в которых на четных местах стоят нули

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

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

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 все

(1) только P1

(2) только P2

(3) только P3

(4) P1 и P2

(5) P1 и P3

(6) P2 и P3

(7) все

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

(1) 6x₁² + 2x₂² x₁+x₂

(2) 2x₁² x₂+ 4x₂² +x₂

(3) 2x₁² x₂(2x₂ +1) +x₂

(4) 4x₁² x₂²+ 4 x₁² x₂+x₂

(5) ни одну из выше перечисленных

\begin{array}{lll}
q\ 0 \rightarrow q\ 0\ П & p\ 0 \rightarrow p\ 1\ Л  &  r\ 0 \rightarrow r\ 0\ Л
q\ 1 \rightarrow q\ 1\ П & p\ 1 \rightarrow r\ 0\ Л  & r\ 1 \rightarrow r\ 1\ Л 
q \wedge \rightarrow p \wedge Л  &  p \wedge \rightarrow ! \wedge П  & r \wedge \rightarrow ! \wedge П
\end{array}

В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации q 1100 ?

(1) ! 1011

(2) ! 0110

(3) ! 0011

(4) ! 1110

(5) ни в одну из выше указанных

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

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

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

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

(1) только P₁

(2) только P₂

(3) только P₃

(4) P₁ и P₂

(5) P₁ и P₃

(6) P₂ и P₃

(7) ни одна

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

(1) только S1

(2) только S2

(3) только S3

(4) S1 и S3

(5) S2 и S3

(6) S1 и S2

(7) ни одна

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

(1) (X1 ∧ X3) ∨ (X2 ∧¬X3)

(2) (X1 ∧ ¬X2 ∧ X3) ∨ (X2 ∧ X3))

(3) (X1 ∨ X2) ∧(X2 ∧X3)

(4) (X1 ∧ X3) ∨ (X2∧ X3)

(5) X2 ∧ ¬X3

(6) (X2 ∧ ¬X3) ∨ (X1 ∧¬X2 ∧ X3)

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

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

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

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

(1) все слова в алфавите {a, b} длины не меньше 2 и пустое слово

(2) все слова над {a, b}, которые начинаются и кончаются одним и тем же символом

(3) все слова нечетной длины, состоящие из символов {a, b}

(4) Ответ 4. Все слова длины не меньше 8, состоящие из символов {a, b}

(5) все слова над {a, b} , длина которых делится на 2, включая слово длины 0

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

(1) только W1

(2) только W2

(3) только W3

(4) W1 и W2

(5) W1 и W3

(6) W2 и W3

(7) все

Пусть структурированная программа 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) σ1(x) = 5, σ1(y) = 7, σ1(z) = 8

(2) σ1(x) = 5, σ1(y) = 6, σ1(z) = 7

(3) σ1(x) = 6, σ1(y) = 7, σ1(z) = 8

(4) σ1(x) = 5, σ1(y) = 7, σ1(z) = 7

(5) ни в одном из вышеуказанных

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

(1) R( 0, [+; [s¹ ; [+; I²₁, I²₁]], I²₂ ])

(2) R( 0, [+; [+; [s¹ ; I²₁], [s¹ ; I²₁]], I²₂ ])

(3) [s¹ ; R( 0, [+; [+; [s¹ ; I²₁], I²₁], I²₂ ])]

(4) R( 0, [+; [+;[+; [s¹ ; I²₁], [s¹ ; I²₁]], [+;I²₁, I²₁]], [+;I²₂ , I²₂]])

(5) ни одно из выше перечисленных

Какие из этих машин переводят любую начальную конфигурацию вида q a²ⁿ b в заключительную конфигурацию ! b aⁿ (n ≥ 0 )?

(1) только M₁

(2) только M₂

(3) только M₃

(4) M₁ и M₂

(5) M₁ и M₃

(6) M₂ и M₃

(7) ни одна

Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ?

(a) является отношением эквивалентности,

(b) рефлексивно и транзитивно,

(1) только (a)

(2) только (b)

(3) только (c )

(4) (a) и (b)

(5) (a) и (c)

(6) (b) и (c)

(7) всеми

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

(1) (1101 1101)

(2) (1111 0101)

(3) (0111 1001)

(4) (1110 0101)

(5) (1101 0101)

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

(1) только D1

(2) только D2

(3) только D3

(4) D1 и D2

(5) D2 и D3

(6) D1 и D3

(7) все

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

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

(1) только W

(2) только V

(3) только U

(4) W и V

(5) V и U

(6) W и U

(7) все

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

(1) (1 + 01)*00(01 +1)*

(2) (1 +00)*

(3) (0 + 1)*10*1(0+1)*

(4) 1*00(0 + 10)*(0+1)*

(5) (1 +01)*00(0 +1)*

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

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

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

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

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

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

Пусть структурированная программа 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) σ1(x) = 4, σ1(y) = 5, σ1(z) = 6, σ(u) = 4, σ(v) =6

(2) σ1(x) = 4, σ1(y) = 5, σ1(z) = 5, σ(u) = 4, σ(v) =6

(3) σ1(x) = 4, σ1(y) = 5, σ1(z) = 4, σ(u) = 4, σ(v) =6

(4) σ1(x) = 4, σ1(y) = 5, σ1(z) = 4, σ(u) = 4, σ(v) = 5

(5) ни в одном из вышеуказанных

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

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

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

(3) f(x,y) = minus(x+2, 2^y)

(4) f(x,y) = minus(x+1, 2^y)

(5) f(x,y) = minus(x+1, 2^(y+1))

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

P1: q ∧ → l₁ * Л, l₁∧→ r * П, l₁a→ l₂a П, l₂a→ l₂ a Л, l₂∧→ q'∧ П, r∧ → r ∧ П, r *→ r₁ ∧ П, r₁ ∧→ l * Л, l ∧→ l ∧ Л, l *→ l₁ ∧ Л, r₁ a→ r₂a Л, r₂∧→ r₂∧ Л, r₂*→ r₃∧ П, r₃∧→ r₃∧ П, r₃a→ q'a Н.

P2: q ∧ → l₁ * Л, l₁∧→ r * П, l₁a→ l₂a П, l₂∧→ l₂∧ П, l₂*→ l₃∧ Л, l₃∧→ l₃∧ Л, l₃a→ q'a Н, r∧ → r ∧ П, r *→ r₁ ∧ П, r₁ ∧→ l * Л, l ∧→ l ∧ Л, l *→ l₁ ∧ Л, r₁ a→ r₂a Л, r₂∧→ r₂∧ Л, r₂*→ r₃∧ П, r₃∧→ r₃∧ П, r₃a→ q'a Н.

P3: q ∧ → l₁ * Л, l₁∧→ r * П, l₁a→ l₂a П, l₂∧→ l₂∧ П, l₂*→ l₃∧ Л, l₃∧→ l₃∧ Л, l₃a→ l₄ a Л, l₄a→ l₄ a Л, l₄∧→ q'∧ П, r∧ → r ∧ П, r *→ r₁ ∧ П, r₁ ∧→ l * Л, l ∧→ l ∧ Л, l *→ l₁ ∧ Л, r₁ a→ r₂a Л, r₂∧→ r₂∧ Л, r₂*→ r₃∧ П, r₃∧→ r₃∧ П, r₃a→ q'a Н.

(1) только P₁

(2) только P₂

(3) только P₃

(4) P₁ и P₂

(5) P₁ и P₃

(6) P₂ и P₃

(7) ни одна

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

(1) f(x,y) = x³y³

(2) f(x,y) = (x+2)³ + sg( x² – sqr(x)² ) + sg( y² – sqr(y)² )

(3) f(x,y) = 8 + sg( x² – sqr(x)² + y² –sqr(y)² )

(4) f(x,y) = sqr(x)³ sqr(y)³

(5) f(x,y) = (sqr(x) + sqr(y))³

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

(1) только P1

(2) только P2

(3) только P3

(4) только P1 и P3

(5) только P2 и P3

(6) только P1 и P2

(7) P1, P2 и P3

Пусть задана УБДР 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)}

(1) 1

(2) 3

(3) 4

(4) 5

(5) 6

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

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

(1) все слова, начинающиеся с a

(2) все слова из букв a , начинающиеся с aa

(3) все слова из букв a , длина которых при делении на 3 дает остаток 2

(4) все слова, в которых буквы a идут блоками нечетной длины

(5) все слова из букв a , начинающиеся с aa или aaa

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

(1) a(ba)*

(2) (ba)*b

(3) b*ab*

(4) подходит и 1, и 2

(5) для этого языка существует только одно регулярное выражение

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

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

С₂ = < {0, 1}, { Q, R, S }, 0, F₂={ S }, Φ₂>,

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

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

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁и C₂

(5) C₁и C₃

(6) C₂и C₃

(7) все

Пусть структурированная программа 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) σ1(x) = 6, σ1(y) = 5, σ(u) = 8, σ(v) = 6

(2) σ1(x) = 6, σ1(y) = 5, σ(u) = 8, σ(v) =7

(3) σ1(x) = 7, σ1(y) = 6, σ(u) = 8, σ(v) =6

(4) σ1(x) = 7, σ1(y) = 5, σ(u) = 7, σ(v) =7

(5) ни в одном из вышеуказанных

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

(1) 1

(2) 3

(3) 8

(4) 4

(5) 2

(6) ни одному из выше перечисленных

Пусть машина Тьюринга M построена из следующих простых машин Тьюринга:

Коп_a –копирует вход после разделительного символа a : w ⇐ w a w;

Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );

Сум - складывает два аргумента в унарной системе: |^x * |^y ⇐ |^x+y ;

Умн - умножает два аргумента в унарной системе: |^x * |^y ⇐ |^xy ;

Пуст - не изменяет аргумент: w ⇐ w

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

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

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

(1) f(x) = 2x² + 2x

(2) f(x) = x² + x

(3) f(x) = 2x² + x

(4) f(x) = x² + 2x

(5) ни одну из выше перечисленных

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

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

(1) только (a)

(2) только (b)

(3) только (c )

(4) (a) и (b)

(5) (a) и (c)

(6) (b) и (c)

(7) Любой из них

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

(1) 2

(2) 3

(3) 4

(4) 5

(5) 6

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

a) x1 < x2 < x3 < x4 и

b) x1 < x3 < x2 < x4.

Определите сложности этих двух схем.

(1) (a) - 5, (b) - 6

(2) (a) - 4, (b) - 6

(3) (a) - 4, (b) - 5

(4) (a) - 6, (b) - 6

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

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

(1) только A₁

(2) только A₂

(3) только A₃

(4) A₁ и A₂

(5) A₁ и A₃

(6) A₂ и A₃

Заданы два НКА:

A =< {a, b}, {0, 1, 2, 3}, 0, {2}, Φ_A > с программой Φ_A: 0 a → 1, 0 b → 3, 1 a → 3 1 b → 2, 2 a → 3, 2 b → 2, 3 a → 3, 3b → 3 и

B =< {a, b}, {q0, q1, q2}, q0, {q2}, Φ_B > с программой Φ_B: q0 a → q0, q0 b → q1, q1 a → q1, q1 a → q2

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

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

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

(1) cⁿbbbaaabb

(2) baⁿbⁿ⁺⁴aaa

(3) cbⁿ⁺²

(4) bⁿ⁺²caⁿc

(5) bⁿcaⁿbbb

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

(1) только П1

(2) только П2

(3) только П3

(4) П1 и П2

(5) П1 и П3

(6) П2 и П3

(7) все

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

(1)

(2)

(3)

(4)

(5) ни одно из выше перечисленных

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

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

с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом: M = Коп_# ; par_#( par_* (Коп_*, Пуст ); Зам(*, |), Пуст ); if Больше₂₁ then par_#( Пуст, Сум ) else par_#( Пуст, Умн ) endif; Зам(#, *); Выб_33. Какие результаты она получит на входных данных вида

|^x1 * |^x2
при  x₁= 2, x₂= 7

и при x₁= 3, x₂= 5, соответственно?

(1) 9 и 8

(2) 9 и 15

(3) 14 и 8

(4) 14 и 15

(5) ни один из предыдущих ответов не подходит

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

f1(n) = номер программы: ' x:= 0; П_n ; y:= x '.

f2(n) = номер программы: 'x_n:=x; x:= 0; П_n ; y:= x_n'. (здесь переменная x_n не входит в П_n )

f3(n) = номер программы: 'y:= x; x:= 0; П_n ; y:= y+1'.

(1) только f1

(2) только f2

(3) только f3

(4) f1 и f2

(5) f1 и f3

(6) все

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

(1) 4

(2) 5

(3) 6

(4) 7

(5) 8

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

(1) 10

(2) 8

(3) 9

(4) 11

(5) 7

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

C = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2), (p,3)}, (q,0), F={(q, 1), (q, 2)}, Φ_C >,

D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,1), (p,2)}, Φ_D >,

(1) C, L_C = L_A \ L_B

(2) C, L_C= L_A ∩ L_B

(3) C, L_C = L_B \ L_A

(4) D, L_D = L_A \ L_B

(5) D, L_D = L_A ∩ L_B

(6) D, L_D = L_A ∪ L_B

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

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

С₂ = < {0,1}, {q, p, r, s }, q, F₂={p, s}, Φ₂>,

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

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

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

L1 = { ww | w = b²aⁿb , n > 0 },

L2 = { b²aⁿb | n > 0 },

L3 = { (ab)ⁿaⁿb | n > 0 }.

(1) только L1

(2) только L2

(3) только L3

(4) L1 и L2

(5) L1 и L3

(6) L3 и L2

(7) все

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

(1) только П1

(2) только П2

(3) только П3

(4) П1 и П2

(5) П1 и П3

(6) П2 и П3

(7) все

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

(1) R( 9, [c₂; [c₂₁; I²₂], [×; [c₂₁; I²₂], [c₂₂; I²₂]])

(2) R( 9, [c₂; [c₂₂; I²₂], [×; [c₂₁; I²₂], [c₂₂; I²₂]])

(3) R( 2, [c₂; [c₂₂; I²₂], [×; [c₂₁; I²₁], [c₂₂; I²₂]])

(4) R( 2, [c₂; [c₂₂; I²₂], [×; [c₂₁; I²₁], [c₂₂; I²₂]])

(5) ни одна из выше перечисленных

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

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

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

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

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

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

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

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

(1) M1

(2) M2

(3) M3

(4) M4

(5) ни одна

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

(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

(2) 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

(3) 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

(4) 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

(5) ни один из выше приведенных автоматов M1, M2, M3, M4

Пусть задан недетерминированный конечный автомат (без пустых переходов) M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программой Φ: q 0 → p, q 0 → s, q 1→ q, p 0 → q, p 0 → p, s 1 → q, s 1 → p Какие из следующих трех ДКА эквивалентны M?

M1 = < {0, 1}, {q, ps, pq, pqs}, q, F1={ ps, pq, pqs }, Φ1> с программой Φ1: q 0 → ps, q 1 → q, ps 0 → pq, ps 1 → pq, pq 0 → pqs, pq 1 → q, pqs 0 → pqs, pqs 1 → pq

M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F2={p, ps, pq, pqs }, Φ2> с программой Φ2: q 0 → ps, q 1 → q, p 0 → pq, p 1 → q, ps 0 → qs, ps 1 → pq, pq 0 → pqs, pq 1 → q, qs 0 → ps, qs 1 →q, pqs 0 → pqs, pqs 1 → pq, ∅ 0 →∅, ∅ 1 →∅

M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F3={ p, ps, pq, pqs }, Φ3> с программой Φ3: q 0 → ps, q 1 → q, p 0 → pq, p 1 → q, s 0 →∅, s 1 →pq, ps 0 → pq, ps 1 → pq, pq 0 → pqs, pq 1 → q, qs 0 → ps, qs 1 →q, pqs 0 → pqs, pqs 1 → pq, ∅ 0 →∅, ∅ 1 →∅

(1) только M1

(2) только M2

(3) только M3

(4) M1 и M2

(5) M1 и M3

(6) M2 и M3

(7) ни один

В доказательстве теоремы 20.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x1,x2, y) = R( g², f⁴), требовалась м.Т. M₁, которая переводит конфигурацию вида |^x1*|^x2* |^y в конфигурацию |^y * |^x1*|^x2* ∧ *|^g(x) , используя м.Т. M_g, вычисляющую функцию g(x1,x2). Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M₁ ?

P1 = Коп_#; par_# (par_* (Чист, Чист,Пуст); Зам(*,∧ ) , par_* (Пуст , Пуст ,Чист); Зам(*,# ) ; Зам(*,∧ ) ; Зам( #,* )); par_# (Пуст, Коп_* ); par_* (Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|,* ))

P2 = Коп_#; par_# (par_* (Чист, Чист , Пуст); Зам(*,∧ ) ; Зам(*,∧ ), par_* (Пуст , Пуст ,Чист); Зам(*,# ) ; Зам(*,∧ ) ; Зам( #,* )); par_# (Пуст, Коп_# ); par_# (Пуст, Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* )

P3 = Коп_*; par_* (Чист, Чист, Пуст, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par_# (Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* )

В этих определениях участвуют следующие простые машины Тьюринга:

Коп_a –копирует вход после разделительного символа a : w ⇐ w a w;

Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );

Пуст - не изменяет аргумент: w ⇐ w ;

Чист – стирает аргумент: w ⇐ ∧ ;

+1 - прибавляет 1 к аргументу: |^x⇐ |^x+1

(1) только P1

(2) только P2

(3) только P3

(4) P1 и P2

(5) все

(6) ни одна

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

(1) (X ∨ ¬Z) ∧((Y ∨ ¬X) ∧¬Z)

(2) (¬X ∨ Y ∨ ¬Z) ∧((X ∨ Y) ∧(Y ∨ Z))

(3) ((X ∨ Y) ∧(Y ∨ Z)) ∧(( X ∨ Y) ∧¬Z)

(4) ((X ∧ Y) ∨ (Y ∨ Z)) ∧ (¬Y ∧ (Y∨Z))

(5) ¬Y ∧ Z

(1) (01011101)

(2) (01010111)

(3) (01011011)

(4) (01000111)

(5) (01011101)

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

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

(1) 010100

(2) 010000

(3) 100011

(4) 000001

(5) никакое

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

(1) L = {ε, a, b, ba, bb, ab, bab, aba, abba, abb, abba, abbb}

(2) L = {a, ab, abba, aa, aba, abbaa, abb, abbab, abbaba}

(3) L = {ε, a, b, ba, bb, bba, ab, aba, abba , baa, bab, baba}

(4) L = {a, b, ba, bb, bba, aba, abb, abba, abba, abab}

(5) L = {ε, a, b, ba, bb, bba, aba, abbaa, ab, abb, abbab, abbaba}

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

h(a) = 0, h(b) = 11, h(c) = ε ?

(1) все слова в алфавите {0, 1}, начинающиеся на 0, с длиной > 5

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

(3) все слова нечетной длины в алфавите {0, 1}, начинающиеся на 0 и содержащие подслово 1111, в которых на нечетных местах стоят нули

(4) все слова в алфавите {0, 1}, начинающиеся на 0, в которых на четных местах стоят нули и которые содержат подслово 1111

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

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 все

(1) только P1

(2) только P2

(3) только P3

(4) P1 и P2

(5) P1 и P3

(6) P2 и P3

(7) все

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

(1) 2x₁ - 4x₂ -2

(2) 2x₁ x₂ - 4x₂ -2

(3) 4x₁² - 4x₂ -1

(4) 2x₁ - 2x₂ -2

(5) ни одну из выше перечисленных

\begin{array}{lll}
q\ 0 \rightarrow q\ 0\ П & p\ 0 \rightarrow p\ 1\ Л  &  r\ 0 \rightarrow r\ 0\ Л
q\ 1 \rightarrow q\ 1\ П & p\ 1 \rightarrow r\ 0\ Л  & r\ 1 \rightarrow r\ 1\ Л 
q \wedge \rightarrow p \wedge Л  &  p \wedge \rightarrow ! \wedge П  & r \wedge \rightarrow ! \wedge П
\end{array}

В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации q 1010 ?

(1) ! 1100

(2) ! 0101

(3) ! 1001

(4) ! 1101

(5) ни в одну из выше указанных

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

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

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

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

(1) только P₁

(2) только P₂

(3) только P₃

(4) P₁ и P₂

(5) P₁ и P₃

(6) P₂ и P₃

(7) ни одна

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

(1) только S1

(2) только S2

(3) только S3

(4) S1 и S3

(5) S2 и S3

(6) S1 и S2

(7) ни одна

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

(1) (X1 ∧ X3) ∨ (¬X2 ∧¬X3)

(2) (X1 ∧ ¬X2 ∧ X3) ∨ (X2 ∧ X3))

(3) (X1 ∨ X2) ∧(¬X2 ∧¬X3)

(4) (X1 ∧ X3) ∨ (X2∧ X3)

(5) (¬X2 ∧ ¬X3 ) ∨ (X1 ∧ X2 ∧ X3)

(6) (¬X2 ∧ X3) ∨ (¬X1 ∧¬X2 ∧ ¬X3)

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

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

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

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

(1) все слова над {a, b} , длина которых делится на 3 и каждая третья буква есть a , и слово длины 0

(2) все слова в алфавите {a, b} длины не меньше 3, которые заканчиваются на a, и пустое слово

(3) все слова над {a, b}, длина которых делится на 3 и которые заканчиваются на a

(4) все слова четной длины, состоящие из символов {a, b} , которые заканчиваются на a

(5) все слова длины не меньше 12, состоящие из символов {a, b}

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

(1) только W1

(2) только W2

(3) только W3

(4) W1 и W2

(5) W1 и W3

(6) W2 и W3

(7) все

Пусть структурированная программа 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) σ1(x) = 5, σ1(y) = 4, σ1(z) = 5

(2) σ1(x) = 6, σ1(y) = 5, σ1(z) = 6

(3) σ1(x) = 6, σ1(y) = 4, σ1(z) = 5

(4) σ1(x) = 5, σ1(y) = 5, σ1(z) = 5

(5) ни в одном из вышеуказанных

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

(1) R( 1, [+; [s¹ ;[ s¹ ;[ s¹ ;[+; I²₁, I²₁]]]], I²₂ ])

(2) R( 1, [+; [+; [s¹ ; I²₁], [s¹ ; I²₁]], I²₂ ])

(3) [s¹ ; R( 0, [+; [+; [s¹ ; I²₁], I²₁], I²₂ ])]

(4) R( 1, [+; [+;[+; [s¹ ; I²₁], [s¹ ; I²₁]], [+;I²₁, I²₁]], [+;I²₂ , I²₂]])

(5) ни одно из выше перечисленных

Какие из этих машин переводят любую начальную конфигурацию вида q aⁿ b в заключительную конфигурацию ! b a²ⁿ (n ≥ 0 )?

(1) только M₁

(2) только M₂

(3) только M₃

(4) M₁ и M₂

(5) M₁ и M₃

(6) M₂ и M₃

(7) ни одна

Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ?

(a) если A ≤m B, то (N \A) ≤m (N \B) ,

(b) A ≤m C и B ≤m C для C= {2x | x ∈ A} ∪ {2x+1 | x ∈ B},

(1) только (a)

(2) только (b)

(3) только (c )

(4) (a) и (b)

(5) (a) и (c)

(6) (b) и (c)

(7) всеми

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

(1) (0111 0100)

(2) (0011 0110)

(3) (0011 0100)

(4) (1010 0101)

(5) (0001 0101)

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

(1) только D1

(2) только D2

(3) только D3

(4) D1 и D2

(5) D2 и D3

(6) D1 и D3

(7) все

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

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

(1) только W

(2) только V

(3) только U

(4) W и V

(5) V и U

(6) W и U

(7) все

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

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

(2) (1*01*)*

(3) (01 )*1*01*

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

(5) (1 +01)*(0 +1)

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

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

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

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

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

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

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

(1) σ1(x) = 6, σ1(y) = 5, σ1(z) = 6, σ(u) = 4, σ(v) =6

(2) σ1(x) = 6, σ1(y) = 5, σ1(z) = 7, σ(u) = 4, σ(v) = 7

(3) σ1(x) = 5, σ1(y) = 5, σ1(z) = 6, σ(u) = 4, σ(v) =6

(4) σ1(x) = 6, σ1(y) = 5, σ1(z) = 7, σ(u) = 4, σ(v) = 6

(5) ни в одном из вышеуказанных

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

(1) f(x,y) = minus(y, ix)

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

(3) f(x,y) = minus(y, (i+1)x)

(4) f(x,y) = minus(y+1, ix)

(5) f(x,y) = minus(y+1, (i+1)x)

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

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

P2: q a → p^a ∧ П , p^a b → p^b a П, p^a b' → p^b a' П, p^a # → r a Л, p^a #' → r a' Л, p^a ∧ → r a Л, r a → r a Л , r a' → r a' Л , r ∧ → q ∧ П.

P3: q a → p^a ∧ П , p^a b → p^a b П, p^a # → p^a # П, p^a #' → r a Л, p^a b' → p^a b' П, p^a ∧ → r a Л, r a → r a Л , r a' → r a' Л , r ∧ → q ∧ П, q # → q ∧ П , q a' → p a' Н.

(1) только P₁

(2) только P₂

(3) только P₃

(4) P₁ и P₂

(5) P₁ и P₃

(6) P₂ и P₃

(7) ни одна

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

(1) f(x,y) = 2^x

(2) f(x,y) = 2^x+1 + sg( | x² – sqr(y)² |)

(3) f(x,y) = 4 + sg( | x² – y |)

(4) f(x,y) = 2^x + | x² – y |

(5) f(x,y) = 1 + sg(| x² – y |)

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

(1) только P1

(2) только P2

(3) только P3

(4) только P1 и P3

(5) только P2 и P3

(6) только P1 и P2

(7) P1, P2 и P3

Пусть задана УБДР 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)}

(1) 1

(2) 3

(3) 4

(4) 5

(5) 6

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

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

(1) все слова, начинающиеся на ab и заканчивающиеся на a

(2) все слова вида (ab)ⁿaa при n=0, 1, 2, 3, …

(3) все слова вида (ab)ⁿa при n=0, 1, 2, 3, …

(4) все слова, начинающиеся на a и заканчивающиеся на a

(5) все слова вида (aba)ⁿa при n= 1, 2, 3, …

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

(1) (b*+a)*

(2) (a +b)*

(3) b*ab*

(4) подходит и 1, и 2

(5) для этого языка существует только одно регулярное выражение

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

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

С₂ = < {0, 1}, { Q, S }, 0, F₂={ S }, Φ₂>,

С₃ = < {0, 1}, { Q, R, S }, 0, F₃={ S }, Φ₃>,

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

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁и C₂

(5) C₁и C₃

(6) C₂и C₃

(7) все

Пусть структурированная программа 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) σ1(x) = 7, σ1(y) = 5, σ(u) = 7, σ(v) = 7

(2) σ1(x) = 6, σ1(y) = 5, σ(u) = 8, σ(v) = 6

(3) σ1(x) = 7, σ1(y) = 6, σ(u) = 8, σ(v) =6

(4) σ1(x) = 6, σ1(y) = 5, σ(u) = 7, σ(v) = 6

(5) ни в одном из вышеуказанных

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

(1) 2

(2) 16

(3) 8

(4) 64

(5) 32

(6) ни одному из выше перечисленных

Пусть машина Тьюринга M построена из следующих простых машин Тьюринга: Коп_a –копирует вход после разделительного символа a : w ⇐ w a w;

Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );

Сум - складывает два аргумента в унарной системе: |^x * |^y ⇐ |^x+y ;

Умн - умножает два аргумента в унарной системе: |^x * |^y ⇐ |^xy ;

Пуст - не изменяет аргумент: w ⇐ w

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

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

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

(1) f(x) = 2x² + 2x

(2) f(x) = x² + x

(3) f(x) = 2x² + x

(4) f(x) = x² + 2x

(5) ни одну из выше перечисленных

(a) x := x +1,

(b) пока x < y делай P все,

(1) только (a)

(2) только (b)

(3) только (c )

(4) (a) и (b)

(5) (a) и (c)

(6) (b) и (c)

(7) Любой из них

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

(1) 2

(2) 3

(3) 4

(4) 5

(5) 6

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

a) x1 < x2 < x3 < x4 и

b) x1 < x3 < x2 < x4.

Определите сложности этих двух схем.

(1) (a) - 6, (b) - 7

(2) (a) - 6, (b) - 6

(3) (a) - 5, (b) - 6

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

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

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

(1) только A₁

(2) только A₂

(3) только A₃

(4) A₁ и A₂

(5) A₁ и A₃

(6) A₂ и A₃

Заданы два НКА:

A =< {a, b}, {0, 1, 2, 3}, 0, {2}, Φ_A > с программой Φ_A: 0 a → 1, 0 b → 3, 1 a → 2, 1 b → 1, 2 a → 1, 2 b → 3, 3 a → 3, 3b → 3 и

B =< {a, b}, {q0, q1, q2}, q0, {q2}, Φ_B > с программой Φ_B: q0 b → q0, q0 b → q1, q1 a → q1, q1 a → q2, q2 b → q0

Какие из следующих трех НКА С₁ , С₂ , С₃ распознают конкатенацию L_A? L_B языков, распознаваемых автоматами A и B?

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

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

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

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

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

(1) bbbcⁿaabb

(2) bcbⁿ⁺⁴aⁿaca

(3) caⁿbⁿ⁺³c

(4) bⁿ⁺²caⁿc

(5) aⁿcbⁿ⁺³c

(1) только П1

(2) только П2

(3) только П3

(4) П1 и П2

(5) П1 и П3

(6) П2 и П3

(7) все

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

(1)

(2)

(3)

(4)

(5) ни одно из выше перечисленных

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

с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом: M = Коп_# ; par_#( par_* (Коп_*, Пуст ); Зам(*, |), Пуст ); if Больше₂₁ then par_#( Пуст, Умн ) else par_#( Пуст, Сум ) endif; Зам(#, *); Выб_33. Какие результаты она получит на входных данных вида

|^x1 * |^x2
при  x₁= 4, x₂= 8

и при x₁= 1, x₂= 5, соответственно?

(1) 12 и 5

(2) 12 и 6

(3) 32 и 5

(4) 32 и 6

(5) ни один из предыдущих ответов не подходит

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

f1(n) = номер программы: 'x_n:=x; x:= 0; П_n ; y:= x_n'. (здесь переменная x_n не входит в П_n )

f2(n) = номер программы: 'П_n ; y:= x'.

f3(n) = номер программы: 'y:= x; x:= 0; П_n ; y:= y+1'.

(1) только f1

(2) только f2

(3) только f3

(4) f1 и f2

(5) f1 и f3

(6) все

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

(1) 14

(2) 15

(3) 12

(4) 17

(5) 11

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

(1) 10

(2) 8

(3) 9

(4) 7

(5) 6

C = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2), (p,3)}, (q,0), F={(q, 1), (q, 2)}, Φ_C >,

D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,3)}, Φ_D >,

(1) C, L_C = L_A \ L_B

(2) C, L_C= L_A ∩ L_B

(3) C, L_C = L_B \ L_A

(4) D, L_D = L_A \ L_B

(5) D, L_D = L_A ∩ L_B

(6) D, L_D = L_A ∪ L_B

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

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

С₂ = < {0,1}, {q, p, r, s }, q, F₂={p, r}, Φ₂>,

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

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

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

L1 = { wbw | w = aⁿ , n > 0 },

L2 = { bwwb | w = aⁿ , n > 0 },

L3 = { (ab)ⁿa^m | n, m > 0 }.

(1) только L1

(2) только L2

(3) только L3

(4) L1 и L2

(5) L1 и L3

(6) L3 и L2

(7) все

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

(1) только П1

(2) только П2

(3) только П3

(4) П1 и П2

(5) П1 и П3

(6) П2 и П3

(7) все

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

(1) R( 2, [c₂; [c₂₁; I²₂], [+; [c₂₁; I²₂], [s;[c₂₂; I²₂]]])

(2) R( 1, [c₂; [c₂₂; I²₂], [+; [c₂₁; I²₁], [c₂₂; I²₂]])

(3) R( 2, [c₂; [c₂₂; I²₂], [s; [+; [c₂₁; I²₂], [c₂₂; I²₂]]])

(4) R( 1, [c₂; [c₂₂; I²₂], [+; [c₂₁; I²₂], [s; [c₂₂; I²₂]]])

(5) ни одна из выше перечисленных

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

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

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

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

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

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

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

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

(1) M1

(2) M2

(3) M3

(4) M4

(5) ни одна

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

(1) M1 = < {a, b}, {0, 1, 4 ,5}, 0, F1={0, 1, 5}, Φ1> с программой Φ1: 0 a → 1, 0 b → 1, 1 a → 1, 1 b → 4, 4 a → 5, 5 a → 1, 5 b → 4

(2) M2 = < {a, b}, {0, 1, 2, 5 }, 0, F2={1, 5}, Φ2> с программой Φ2: 0 a → 1, 0 b → 1, 0 b → 4, 1 a → 1, 1 b → 4, 4 a → 5, 5 a → 1, 5 b → 4

(3) M3 = < {a, b}, {0, 1, 4, 5 }, 0, F3={0, 1, 5}, Φ3> с программой Φ3: 0 a → 1, 0 b → 1, 0 b → 4, 1 a → 1, 1 b → 4, 4 a → 5, 5 a → 1, 5 b → 4

(4) M4 = < {a, b}, {0, 1, 3, 4, 5 }, 0, F4={0, 1, 3, 5}, Φ4> с программой Φ4: 0 a → 1, 0 b → 1, 0 b → 4, 1 a → 1, 1 b → 4, 3 a → 1, 3 b → 4, 4 a → 5, 5 a → 1, 5 b → 4

(5) ни один из выше приведенных автоматов M1, M2, M3, M4

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

(1) только M1

(2) только M2

(3) только M3

(4) M1 и M2

(5) M1 и M3

(6) M2 и M3

(7) ни один