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

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

---

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

---

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

---

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

---

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

---

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

---

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



---

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






---

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



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

---

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



---

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



---


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



---

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



---

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

---


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

---

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



---

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



---


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

---

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



• a) x1 < x2 < x3 < x4 и
• b) x1 < x3 < x2 < x4.
Определите сложности этих двух схем.

---


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

---

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



• a) x1 < x2 < x3 < x4 и
• b) x1 < x3 < x2 < x4.
Определите сложности этих двух схем.

---

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






---

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



---


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

---

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



• a) x1 < x2 < x3 < x4 и
• b) x1 < x3 < x2 < x4.
Определите сложности этих двух схем.

---

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



---


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

---

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



---

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



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

---

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



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

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

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



---

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

---

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



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

---

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



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

---

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



---

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



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

C = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2), (p,3)}, (q,0), F={(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 >,



---

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



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

---

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



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

---

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



---

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



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

---

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



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

---

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



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

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

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



---

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



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

---

На следующем рисунке представлены диаграммы двух конечных автоматов 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 >,



---

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

где


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

---

На следующем рисунке представлены диаграммы двух конечных автоматов 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 >,



---

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



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

---

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



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

---

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



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

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

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



---

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



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

---

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



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

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

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



---

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

---

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



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

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

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



---

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



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

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

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



---

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

---

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



---

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



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

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

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



---

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



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

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

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



---

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



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

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

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



---

На следующем рисунке представлены диаграммы двух конечных автоматов 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 >,



---

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



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

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

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



---

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



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

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

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



---

На следующем рисунке представлены диаграммы двух конечных автоматов 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 >,



---

На следующем рисунке представлены диаграммы двух конечных автоматов 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 >,



---

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



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

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

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



---

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



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

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

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



---

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



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

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

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



---

Какие из следующих трех автоматов С₁ , С₂ , С₃ распознают язык, представляемый регулярным выражением (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}, ?₃> ,

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




---

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



---

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



---

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



---

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



A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ?_A > с программой
?_A: 0 a >? 1, 0 b >? 3, 1 a >? 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}, ?₃>, где программы заданы в следующих таблицах (? означает отсутствие соответствующего перехода).




---

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



---

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



---

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



---

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



---

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



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

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

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

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




---

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

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

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

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

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




---

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

L1 = { 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 }.

---

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


---

Пусть задан ДКА A =< {a, b, c}, {0, 1, 2}, 0, F= {2}, ?_A > с программой ?_A: { 0 a >? 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)}, ?₃>,

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




---

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


---

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


---

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


---

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

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

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

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

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




---

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



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 она завершит свою работу?

---

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



---

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



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 она завершит свою работу?

---

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



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

---

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




---

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



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 она завершит свою работу?

---

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



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 := u+1;  v := z+1;  
если  x < v  то
      если  x = y   то
                           z := y+1
                    иначе  z := x 
      конец 
                иначе  z :=x +1 
конец

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

---

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



---

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




---

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



---

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



---

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



---

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



---

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



---

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



---

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



---

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


---

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



---

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



---

Пусть функция 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?



---

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



---

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



---

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



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

• 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 аргументов: x₁*…*x_i*…*x_n ? x_i ,
• Нуль_in — выдает 1, если i-ый аргумент из n аргументов равен ? (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |ⁱ , i >0),
• Выч1 – вычитает единицу в унарной системе: |^j ? |^j-1 (| ? ?, ? ? ?)
Какая из этих машин вычисляет функцию f(x) = x^xв унарном кодировании, т.е. переводит вход |^xв выход |^y, где y = x^x(пусть f(0)=0) ?


---

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



P1: q a >? p^a ? П , q a’ >? p a’ Н , p^a b >? p^b a П, p^a b’ >? p^b a’ П, p^a # >? r a Л, p^a #’ >? r a’ Л, p^a ? >? r a Л, r a >? r a Л , r a’ >? r a’ Л , r ? >? q ? П.

P2: q a >? p^a ? П , p^a b >? p^b a П, p^a b’ >? p^b a’ П, p^a # >? r a Л, p^a #’ >? r a’ Л, p^a ? >? r a Л, r a >? r a Л , r a’ >? r a’ Л , r ? >? q ? П.

P3: q a >? p^a ? П , p^a b >? p^a b П, p^a # >? p^a # П, p^a #’ >? r a Л, p^a b’ >? p^a b’ П, p^a ? >? r a Л, r a >? r a Л , r a’ >? r a’ Л , r ? >? q ? П, q # >? q ? П , q a’ >? p a’ Н.

---

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





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

---

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



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

• 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 аргументов: x₁*…*x_i*…*x_n ? x_i ,
• Нуль_in — выдает 1, если i-ый аргумент из n аргументов равен ? (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |ⁱ , i >0),
• Выч1 – вычитает единицу в унарной системе: |^j ? |^j-1 (| ? ?)

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

---

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





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

---

Пусть машина Тьюринга 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  Больше21  then par#(  Пуст, Умн ) else  par#(  Пуст, Сум ) endif;
Зам(#, *); Выб33.

Какие результаты она получит на входных данных вида |^x1 * |^x2
при x₁ = 4, x₂ = 8 и при x₁ = 1, x₂ = 5, соответственно?

---

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



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

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

• Коп_a –копирует вход после разделительного символа a : w ? w a w;
• Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ? w₁ b w₂ ( a ? w₁ );
• Пуст — не изменяет аргумент: w ? w ;
• Чист – стирает аргумент: w ? ? ;
• Выч1 – вычитает единицу в унарной системе: |^j ? |^j-1 (| ? ?, ? ? ?);
• +1 — прибавляет 1 к аргументу: |^x? |^x+1

---

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



• P1: q <a, b, c, |> >? q <a, | , c, | > П , s <a, | , c, | > >? s <a, | , c, | > Л , q <a, |, c, ?> >? q <a, ? , c, ?> П , s <?, ?, ?, ?> >? p <?, ? , ?, ?> П. q <a, ?, c, ?> >? s <a, ? , c, ?> Л ,
• P2: q <a, |, c, d> >? q <a, | , c, | > П , s <a, | , c, | > >? s <a, | , c, | > Л , q <a, ?, c, |> >? q <a, ? , c, ?> П , s <a, ?, c, ?> >? p <a, ? , c, ?> П. q <a, ?, c, ?> >? s <a, ? , c, ?> Л ,
• P3: q <a, b, c, |> >? q <a, | , c, | > П , s <a, | , c, | > >? s <a, | , c, | > Л , q <a, b, c, ?> >? s <a, ? , c, ?> Л , s <a, ?, c, ?> >? p <a, ? , c, ?> П.

---

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



• (a) если x < y то P1 иначе P2 конец,
• (b) если x = y то P1 иначе P2 конец.,
• (c) x := 0.

---

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

---

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



• (a) x := x +1,
• (b) пока x < y делай P все,
• (c) пока x = y делай P все.
.

---

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

---

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



• (a) является отношением эквивалентности,
• (b) рефлексивно и транзитивно,
• (c) сохраняет свойство разрешимости: если A ? m B и B — разрешимо, то и A разрешимо.

---

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

---

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

---


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

---

Пусть задана логическая схема 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 =< {a,b}, {q,p}, q, {p}, ?_A> и B =< {a,b}, {1, 2, 3}, 1, {1, 2}, ?_B>,



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

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

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



---

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


---

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

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

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

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

---

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


---

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

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

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

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

---

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



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она завершит свою работу?

---

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



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

---

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



---

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



P1: q ? >? l₁ * Л, l₁?>? r * П, l₁a>? l₂a П, l₂ a>? l₂ a Л, l₂ ?>? q’? П, r? >? r ? П, r *>? r₁ ? П, r₁ ?>? l * Л, l ?>? l ? Л, l *>? l₁ ? Л, r₁ a>? r₂a Л, r₂ ?>? r₂? Л, r₂ *>? r₃? П, r₃?>? r₃? П, r₃ a>? q’a Н.

P2: q ? >? l₁ * Л, l₁?>? r * П, l₁a>? l₂a П, l₂ ?>? l₂? П, l₂ *>? l₃? Л, l₃ ?>? l₃? Л, l₃ a>? q’a Н,
r? >? r ? П, r *>? r₁ ? П, r₁ ?>? l * Л, l ?>? l ? Л, l *>? l₁ ? Л,
r₁ a>? r₂a Л, r₂ ?>? r₂? Л, r₂ *>? r₃? П, r₃?>? r₃? П, r₃ a>? q’a Н.

P3: q ? >? l₁ * Л, l₁?>? r * П, l₁a>? l₂a П, l₂ ?>? l₂? П, l₂ *>? l₃? Л, l₃ ?>? l₃? Л, l₃ a>? l₄ a Л,
l₄ a>? l₄ a Л, l₄ ?>? q’? П, r? >? r ? П, r *>? r₁ ? П, r₁ ?>? l * Л, l ?>? l ? Л, l *>? l₁ ? Л,
r₁ a>? r₂a Л, r₂ ?>? r₂? Л, r₂ *>? r₃? П, r₃?>? r₃? П, r₃ a>? q’a Н.

---

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





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

---

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

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



---

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

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



---

В конструкции для параллельной композиции машин Тьюринга на этапах 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 Л.

---

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

---

Пусть машина Тьюринга 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  Больше21  then par#(  Пуст, Сум  ) else  par#(  Пуст, Умн ) endif;
Зам(#, *); Выб33.

Какие результаты она получит на входных данных вида |^x1 * |^x2
при x₁ = 2, x₂ = 7 и при x₁ = 3, x₂ = 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 > Л ,

---

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



• (a) если A ?m B, то (N \A) ?m (N \B) ,
• (b) A ?m C и B ?m C для C= {2x | x ? A} ? {2x+1 | x ? B},
• (c) сохраняет свойство неразрешимости: если A ?m B и A — неразрешимо, то и B неразрешимо .

---

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

---

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



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

---


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

---

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



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

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

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



---

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



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 (01)*?



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

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

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

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




---

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



---

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



---

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


---

4.



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

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

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

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

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




---

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



---