КР БИС 31з
.pdfКонтрольная работа
Задача 1. Составив таблицы истинности, выяснить равносильны ли следующие булевы функции:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1) |
f(x; y; z) = ((x ! y¹) _z) ^((x ^ y) $ z¹); g(x; y; z) = (x ^y ^z) _((x ! |
||||||||||||||||||
y¹) ^ z¹): |
|
|
|
|
|||||||||||||||
2) |
f(x; y; z) = ((x $ (y _ z¹)) |
^x¹) ! ((x _ y¹) $ z); g(x; y; z) = x_(y ! z): |
|||||||||||||||||
3) |
f(x; y; z) = |
((¹y _ z¹) $ x) ^ (¹x ^ (y ! z¹)) |
; g(x; y; z) = (x ^ y ^ z) _ x¹ _ |
||||||||||||||||
(x ^ y¹) _ (x ^ y ^ z¹): |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
4) |
f(x; y; z) = [¹x $ ((y _ z¹) ! |
|
|
|
|
|
|
|
|
|
|||||||||
(x _ y¹))]; g(x; y; z) = ((¹x ^z¹) _(x ^z)) ^y:¹ |
|||||||||||||||||||
5) |
f(x; y; z) = ((x^(y ! z))_ |
|
|
|
|
|
|
|
|
||||||||||
(x _ z¹)) $ (¹y $ z); g(x; y; z) = (x ! y) _ y: |
|||||||||||||||||||
6) |
f(x; y; z) = ((x ! y) ^ (y ! x)) ! (x _ y); g(x; y; z) = (x ^ y) ! (xjy): |
||||||||||||||||||
7) |
f(x; y; z) = ((x ! y) ^ (y ! x¹)) ! (z ! x); g(x; y; z) = ( |
x # y |
) _ (x ! |
||||||||||||||||
y): |
f(x; y; z) = ((x $ y) ^ (¹x $ y¹)) ! ((x _ y) ^ (¹x _ y¹)); g(x; y; z) = (x $ |
||||||||||||||||||
8) |
y¹) # (y _ z):
9) f(x; y; z) = ((x $ y¹) ! z) ! (x $ z¹); g(x; y; z) = (¹x $ y¹) ^(x _y) ^z: 10) f(x; y; z) = (x ! (y $ z)) $ ((x ! y) $ z); g(x; y; z) = (x !
y) ^ (z ^ x) ^ y:
Задача 2. Докажите, что следующие формулы являются тавтологиями:
1)(((p ^ q) ! r) ^ (¹r _ s¹)) ! (¹p _ q¹);
2)((p ! r) ^ (q ! s) ^ (¹r _ s¹)) ! (¹p _ q¹);
3)((p ! q) ^ (r ! s)) ^ (p _ r) ^ (q ^ s)) ! ((q ! p) ^ (s ! r))
4)((p ! q) ^ (r ! s) ^ (p _ r)) ! (q _ s);
5)(p ! q) ! ((r ! q¹) ! [((s ! p¹) ! ((t¹_ p) ! (t ! s)))])
6)(p ! q) ! ((q ! r) ! (p ! r));
7)(p ! q) ! ((p ! (q ! r)) ! (p ! r));
8)(p ! r) ! ((q ! r) ! ((p _ q) ! r));
9)(q ! r) ! ((p _ q) ! (p _ r));
10)(p ! q) ! ((p ! q¹) ! p¹):
Задача 3. Формулу f(x; y; z) из задачи 1 равносильными преобразованиями приведите сначала СДНФ, затем к СКНФ.
Задача 4. Используя СДНФ, найдите наиболее простую формулу от четырех переменных, принимающую значение 1 только на следующих наборах значений переменных:
1)f(0; 0; 1; 1) = f(1; 0; 0; 1) = f(0; 1; 0; 0) = f(0; 0; 1; 0) = 1;
2)f(1; 0; 0; 0) = f(0; 1; 0; 0) = f(0; 0; 1; 0) = f(0; 0; 0; 1) = f(0; 1; 1; 0) = 1;
3)f(1; 1; 1; 0) = f(1; 1; 0; 1) = f(1; 0; 1; 1) = f(0; 1; 1; 1) = f(1; 0; 0; 1) = 1;
4)f(1; 1; 0; 0) = f(1; 0; 0; 1) = f(0; 0; 1; 1) = f(1; 0; 1; 0) = f(0; 1; 0; 1) = f(1; 1; 1; 1);
5)f(0; 0; 0; 0) = f(1; 0; 1; 1) = f(0; 0; 0; 1) = f(1; 0; 0; 0) = f(1; 1; 1; 1) = f(0; 1; 1; 0) = 1;
6)f(1; 0; 1; 1) = f(1; 0; 0; 0) = f(0; 1; 0; 0) = f(0; 0; 1; 0) = 1;
7)f(1; 0; 1; 1) = f(0; 1; 0; 1) = f(0; 0; 1; 1) = f(0; 1; 0; 1) = f(0; 1; 1; 0) = 1;
8)f(1; 1; 1; 1) = f(1; 0; 0; 1) = f(1; 0; 1; 1) = f(0; 1; 0; 1) = f(1; 0; 0; 1) = 1;
1
9)f(1; 1; 0; 1) = f(1; 0; 0; 1) = f(0; 0; 0; 1) = f(1; 0; 1; 0) = f(1; 1; 0; 1) = f(1; 1; 1; 1);
10)f(0; 0; 0; 0) = f(1; 0; 0; 1) = f(0; 0; 0; 1) = f(1; 0; 1; 0) = f(1; 1; 1; 1) = f(0; 1; 1; 0) = 1:
Задача 5. Используя СКНФ, найдите наиболее простую формулу от четырех переменных, принимающую значение 0 только на следующих наборах переменных:
1)f(0; 0; 1; 1) = f(1; 0; 0; 1) = f(0; 1; 0; 0) = f(0; 0; 1; 0) = 0;
2)f(1; 0; 0; 0) = f(0; 1; 0; 0) = f(0; 0; 1; 0) = f(0; 0; 0; 1) = f(0; 1; 1; 0) = 0;
3)f(1; 1; 1; 0) = f(1; 1; 0; 1) = f(1; 0; 1; 1) = f(0; 1; 1; 1) = f(1; 0; 0; 1) = 0;
4)f(1; 1; 0; 0) = f(1; 0; 0; 1) = f(0; 0; 1; 1) = f(1; 0; 1; 0) = f(0; 1; 0; 1) = f(1; 1; 1; 1) = 0;
5)f(0; 0; 0; 0) = f(1; 0; 1; 1) = f(0; 0; 0; 1) = f(1; 0; 0; 0) = f(1; 1; 1; 1) = f(0; 1; 1; 0) = 0;
6)f(0; 1; 1; 1) = f(1; 0; 0; 0) = f(0; 1; 0; 1) = f(1; 0; 1; 0) = 0;
7)f(1; 0; 0; 0) = f(0; 1; 0; 0) = f(0; 0; 1; 0) = f(0; 0; 0; 1) = f(0; 1; 1; 0) = 0;
8)f(1; 1; 1; 1) = f(1; 0; 0; 1) = f(1; 0; 1; 0) = f(0; 1; 1; 1) = f(1; 0; 1; 1) = 0;
9)f(1; 1; 0; 0) = f(1; 1; 0; 1) = f(0; 0; 1; 1) = f(1; 1; 1; 0) = f(0; 1; 0; 1) = f(1; 1; 1; 1) = 0;
10)f(0; 0; 0; 0) = f(1; 0; 1; 1) = f(0; 0; 0; 1) = f(1; 0; 1; 0) = f(1; 1; 1; 1) = f(0; 1; 0; 0) = 0;
Задача 6. Используя при необходимости теорему дедукции и производные правила вывода, докажите, что следующие формулы являются теоремами исчисления высказываний:
1)(F ! G) ! ((G ! H) ! (F ! H));
2)(F ! (G ! H)) ! (G ! (F ! H));
3)F ! (G ! (F ^ G));
4)(F ! (G ! H)) ! ((F ^ G) ! H);
5)((F ^ G) ! H) ! (F ! (G ! H));
6)F ! F ;
7)F ! (F ! G);
8)(G ! F ) ! (F ! G);
9)(F ! G) ! (G ! F );
10)F ! (G ! (F ! G)):
Теорема дедукции. F1; : : : Fm¡1; Fm ` G , F1; : : : Fm¡1 ` Fm ! G:
Пример решения задачи.
Доказать правило силлогизма F ! G; G ! H ` F ! H: Применив теорему дедукции, перейдем к эквивалентной формулировке F; F ! G; G ! H ` H и решим задачу в этой формулировке.
1.F; F ! G ` G по modus ponens (MP);
2.G; G ! H ` H по MP.
Другие примеры и производные правила вывода в И.А. Лавров, Л.Л. Максимова Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физматлит. 1973, 1995, 2002.
Задача 7. Доказать, что формулы являются теоремами исчисления предикатов:
1) (8x)(8y)B(x; y) $ (8y)(8x)B(x; y);
2
2)(9x)(9y)B(x; y) $ (9y)(9x)B(x; y);
3)(8x)(8y)B(x; y) ! (8x)B(x; x);
4)(9x)B(x; x) ! (9x)(9y)B(x; y);
5)(9x)B(x) $ (8x)B(x);
6)(8x)B(x) $ (9x)B(x);
7)(8x)B(x) ^ (8x)C(x) $ (8x)(B(x) ^ C(x));
8)(9x)B(x) ^ (9x)C(x) $ (9x)(B(x) ^ C(x));
9)A ^ (8x)B(x) $ (8x)(A ^ B(x));
10)A ^ (9x)B(x) $ (9x)(A ^ B(x)):
Задача 8. Выяснить, являются ли следующие формулы общезначимыми формулами алгебры предикатов:
1)(9x)(9y)(P (x; y)) ! (9x)(P (x; x));
2)(8x)(F (x) ! G(x)) ! ((8x)(F (x)) ! (8x)(G(x)));
3)((8x)(9y)(P (x; y)) ! (9y)(8x)(P (x; y)));
4)(8x)(F (x) ! G(x)) ! ((9x)(F (x)) ! (9x)(G(x)));
5)((9x)(P (x)) ^ (9x)(F (x)) ! (9x)(G(x)));
6)(9x)(8y)(Q(x; x) ^ Q(x; y));
7)(9x)(9y)(P (x) ^ P (y));
8)(9x)(9y)(Q(x; y) ! (8z)R(x; y; z));
9)P (x) ! (8y)(P (y));
10)(9x)P (x) ! (8x)P (x):
Задача 9. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:
|
|
¸ |
1 |
q1 |
|
q2¸Л |
q01 |
q2 |
|
q5¸ |
q3¸ |
q3 |
|
q4¸Л |
q01 |
q4 |
|
q51 |
q41Л |
q5 |
|
q0¸ |
q61Л |
q6 |
|
q0¸ |
q7¸ |
q7 |
|
q8¸П |
q01 |
q8 |
|
q91 |
q81П |
q9 |
|
q0¸ |
q101Л |
q10 |
|
q0¸ |
q11¸ |
q11 |
|
q12¸Л |
q01 |
q12 |
|
q131 |
q121Л |
q13 |
|
q0¸ |
q01 |
Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина каждое из следующих слов (в начальный момент времени машина находится в состоянии q1
3
и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸;
вследующей слева ячейке уже записан символ 1):
1)¸1¸11¸; ¸111¸1¸; ¸11¸111¸11¸;
2)¸11¸111¸; ¸1111¸1¸; ¸1¸1¸1111¸;
3)¸1¸111¸; ¸1111¸11¸; ¸1¸11¸111¸;
4)¸111¸1111¸; ¸1¸1111¸; ¸111¸1¸11¸;
5)¸11¸1111¸; ¸111¸11¸; ¸11¸111¸1¸;
6)11¸11¸¸; 1¸111¸¸1; ¸111¸111;
7)1¸1¸1¸1¸; 11¸¸11¸¸; 111¸¸¸111;
8)1¸¸1¸11; 11¸11¸¸11; ¸1¸1¸11¸11;
9)¸111¸11¸11; ¸1¸1¸111; ¸¸1111¸11¸;
10)¸11¸111¸1; ¸¸11111¸; ¸11¸¸1111¸:
Задача 10. Применяя равносильные преобразования, преобразовать данные формулы к предваренной (пренексной) нормальной форме, т. е. к
форме вида (Q1x1) : : : (Qmxm)(F (x1; : : : xn)); где m · n; каждый Qi есть один из кванторов 8 или 9 и формула F (x1; x2; : : : ; xn) не содержит кван-
торов:
1)(8x)(P (x) ! Q(x)) ! [(9x)(P (x)) ! (9y)(Q(y))];
2)(8x)(P (x)) ! (8x)(Q(x));
3)(8x)(Q(x; y)) _ [(9x)(Q(x; x)) ! (8z)(R(t; z) ! (9x)(Q(x; x)))];
4)(8y)(Q(y; z)) ! (9x)(R(x; t; z));
5)(8y)(Q(x; y)) ! R(x; x);
6)P (y) ! [(8x)(Q(x; y)) ! P (y)];
7)(9x)(R(x; y; z)) ! (8x)(Q(x; y));
8)[(9x)(P (x)) _ (8x)(Q(x))] ^ [S(y) ! (8x)(R(x))];
9)(8x)(P (x; y)) _ [(9x)(P (x; x)) ! (8z)((Q(y; z) ! (9x)(P (x; z))))];
10)(P (y) ^ Q(x)) ! (8y)(R(y; z)):
Пример. Привести к пренексной нормальной форме. (9y)[P (x) ! Q(y)] ! (8y)[P (y)_
(8z)(Q(z))]:
Решение.
(9y)[P (x) ! Q(y)] ! (8y)[P (y) _ (8z)(Q(z))] =
=(9y)[P (x) ! Q(y)] ! (8t)[P (t) _ (8z)(Q(z))] =
=(8y)f[P (x) ! Q(y)] ! (8t)(8z)[P (t) _ Q(z)]g = = (8y)(8t)(8z)f[P (x) ! Q(y)] ! [P (t) _ Q(z)]g:
Задача 11.
Вариант 1. Орграф задан перечислением дуг: (1; 2); (1; 4); (2; 5); (2; 1); (3; 1); (3; 5); (4; 1); (4; 5); (5; 3): Для данного орграфа найти матрицу достижимости, решив систему уравнений в полукольце B .
Вариант 2. Орграф задан перечислением дуг: (1; 2); (1; 3); (2; 5); (2; 4); (3; 4); (2; 1); (3; 5); (5; 5): Для данного орграфа найти матрицу достижимости, решив систему уравнений в полукольце B .
Вариант 3. Орграф задан перечислением дуг: (1; 5); (2; 1); (2; 2); (2; 3); (2; 4); (3; 3); (3; 5); (4; 2); (4; 5); (5; 1): Для данного орграфа найти матрицу достижимости, решив систему уравнений в полукольце B .
4
Варинат 4. Орграф задан перечислением дуг: (1; 3); |
(1; 4); |
(2; 3); |
(2; 4); |
||||
(2; 5); |
(3; 5); |
(4; 4); |
(5; 1); |
(5; 2): Для данного орграфа найти матрицу |
|||
достижимости, решив систему уравнений в полукольце B . |
|
|
|||||
Вариант 5. Орграф задан перечислением дуг: (1; 2); |
(1; 4); |
(2; 6); |
(2; 1); |
||||
(3; 2); |
(3; 5); |
(4; 1); |
(4; 5); |
(5; 3): Для данного орграфа найти матрицу |
|||
достижимости, решив систему уравнений в полукольце B . |
|
|
|||||
Вариант 6. Орграф задан перечислением дуг: (1; 2); |
(1; 4); |
(2; 5); |
(2; 5); |
||||
(3; 4); |
(2; 1); |
(3; 5); |
(5; 5): |
Для данного орграфа найти матрицу достижи- |
|||
мости, решив систему уравнений в полукольце B . |
|
|
|
||||
Варинат 7. Орграф задан перечислением дуг: (1; 3); |
(1; 5); |
(2; 3); |
(2; 4); |
||||
(2; 5); |
(3; 5); |
(4; 4); |
(5; 3); |
(5; 2): Для данного орграфа найти матрицу |
|||
достижимости, решив систему уравнений в полукольце B . |
|
|
|||||
Вариант 8. Орграф задан перечислением дуг: (1; 5); |
(2; 5); |
(2; 2); |
(2; 3); |
||||
(2; 4); |
(3; 3); |
(3; 5); |
(4; 3); |
(4; 5); (5; 1): Для данного орграфа найти мат- |
|||
рицу достижимости, решив систему уравнений в полукольце B . |
|
||||||
Варинат 9. Орграф задан перечислением дуг: (1; 3); |
(1; 4); |
(2; 3); |
(2; 4); |
||||
(2; 5); |
(3; 5); |
(4; 5); |
(5; 2); |
(5; 2): Для данного орграфа найти матрицу |
|||
достижимости, решив систему уравнений в полукольце B . |
|
|
|||||
Варинат 10. Орграф задан перечислением дуг: (1; 5); |
(1; 4); |
(2; 3); |
|||||
(2; 4); |
(2; 5); |
(3; 5); |
(4; 4); |
(5; 4); (5; 2): Для данного орграфа найти мат- |
рицу достижимости, решив систему уравнений в полукольце B .
Задача 12.
Вариант 1. На дугах орграфа из задачи 11 задана функция весов:
'(1; 2) = 6; '(1; 4) = 2; '(2; 5) = 6; '(2; 1) = 3; '(3; 1) = 5; '(3; 5) = 4; '(4; 1) = 1; '(4; 5) = 1; '(5; 3) = 1: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .
Вариант 2. На дугах орграфа из задачи 11 задана функция весов:
'(1; 2) = 4; '(1; 3) = 2; '(2; 5) = 1; '(2; 4) = 2; '(3; 4) = 6; '(2; 1) = 4; '(3; 5) = 3; '(5; 5) = 1: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .
Вариант 3. На дугах орграфа из задачи 11 задана функция весов:
'(1; 5) = 1; '(2; 1) = 1; '(2; 2) = 2; '(2; 3) = 1; '(2; 4) = 2; '(3; 3) = 3; '(3; 5) = 6; '(4; 2) = 4; '(4; 5) = 3; '(5; 1) = 3: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .
Вариант 4. На дугах орграфа из задачи 11 задана функция весов:
'(1; 3) = 2; '(1; 4) = 4; '(2; 3) = 5; '(2; 4) = 1; '(2; 5) = 7; '(3; 5) = 1; '(4; 4) = 2; '(5; 1) = 5; '(5; 2) = 4: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .
Вариант 5. На дугах орграфа из задачи 11 задана функция весов:
'(1; 2) = 1; '(1; 4) = 2; '(2; 5) = 6; '(2; 1) = 3; '(3; 1) = 5; '(3; 5) = 4; '(4; 1) = 1; '(4; 5) = 1; '(5; 3) = 1: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .
Вариант 6. На дугах орграфа из задачи 11 задана функция весов:
'(1; 2) = 4; '(1; 4) = 2; '(2; 5) = 1; '(2; 4) = 2; '(3; 4) = 6; '(2; 3) = 4; '(3; 5) = 3; '(5; 5) = 1: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .
5
Вариант 7. На дугах орграфа из задачи 11 задана функция весов:
'(1; 5) = 1; '(2; 1) = 1; '(2; 2) = 1; '(2; 3) = 1; '(2; 4) = 2; '(3; 3) = 3; '(3; 5) = 6; '(4; 3) = 4; '(4; 5) = 3; '(5; 1) = 3: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .
Вариант 8. На дугах орграфа из задачи 11 задана функция весов:
'(1; 3) = 2; |
'(1; 4) = 4; '(2; 3) = 2; '(2; 4) = 1; '(2; 5) = 7; '(3; 5) = 1; |
'(4; 4) = 2; |
'(5; 3) = 5; '(5; 2) = 4: Найти матрицу стоимостей для дан- |
ного графа, решив систему уравнений в полукольце R .
Вариант 9. На дугах орграфа из задачи 11 задана функция весов:
'(1; 5) = 1; '(2; 1) = 5; '(2; 2) = 2; '(2; 3) = 1; '(2; 4) = 2; '(3; 3) = 3; '(3; 5) = 6; '(4; 2) = 4; '(4; 5) = 3; '(5; 1) = 3: Найти матрицу стоимостей для данного графа, решив систему уравнений в полукольце R .
Вариант 10. На дугах орграфа из задачи 11 задана функция весов:
'(1; 3) = 2; |
'(1; 4) = 4; '(2; 3) = 5; '(2; 4) = 2; '(2; 5) = 7; '(3; 5) = 1; |
'(4; 4) = 2; |
'(5; 1) = 5; '(5; 2) = 4: Найти матрицу стоимостей для дан- |
ного графа, решив систему уравнений в полукольце R .
Задача 13.
Вариант 1. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:
|
|
¸ |
1 |
q1 |
|
q2¸Л |
q01 |
q2 |
|
q5¸ |
q3¸ |
q3 |
|
q4¸Л |
q01 |
q4 |
|
q51 |
q41Л |
q5 |
|
q0¸ |
q61Л |
q6 |
|
q0¸ |
q7¸ |
q7 |
|
q8¸П |
q01 |
q8 |
|
q91 |
q81П |
q9 |
|
q0¸ |
q101Л |
q10 |
|
q0¸ |
q11¸ |
q11 |
|
q12¸Л |
q01 |
q12 |
|
q131 |
q121Л |
q13 |
|
q0¸ |
q01 |
Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина слово ¸111¸1111¸; (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).
Вариант 2. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:
6
|
|
¸ |
1 |
q1 |
|
q2¸Л |
q01 |
q2 |
|
q5¸ |
q3¸ |
q3 |
|
q4¸Л |
q01 |
q4 |
|
q51 |
q41Л |
q5 |
|
q0¸ |
q61Л |
q6 |
|
q0¸ |
q7¸ |
q7 |
|
q8¸П |
q01 |
q8 |
|
q91 |
q81П |
q9 |
|
q0¸ |
q101Л |
q10 |
|
q0¸ |
q11¸ |
q11 |
|
q12¸Л |
q01 |
q12 |
|
q131 |
q121Л |
q13 |
|
q0¸ |
q01 |
Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина слово ¸1¸111¸; (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).
Вариант 3. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:
|
|
¸ |
1 |
q1 |
|
q2¸Л |
q01 |
q2 |
|
q5¸ |
q3¸ |
q3 |
|
q4¸Л |
q01 |
q4 |
|
q51 |
q41Л |
q5 |
|
q0¸ |
q61Л |
q6 |
|
q0¸ |
q7¸ |
q7 |
|
q8¸П |
q01 |
q8 |
|
q91 |
q81П |
q9 |
|
q0¸ |
q101Л |
q10 |
|
q0¸ |
q11¸ |
q11 |
|
q12¸Л |
q01 |
q12 |
|
q131 |
q121Л |
q13 |
|
q0¸ |
q01 |
Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина слово ¸11¸111¸; (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).
7
Вариант 4. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:
|
|
¸ |
1 |
q1 |
|
q2¸Л |
q01 |
q2 |
|
q5¸ |
q3¸ |
q3 |
|
q4¸Л |
q01 |
q4 |
|
q51 |
q41Л |
q5 |
|
q0¸ |
q61Л |
q6 |
|
q0¸ |
q7¸ |
q7 |
|
q8¸П |
q01 |
q8 |
|
q91 |
q81П |
q9 |
|
q0¸ |
q101Л |
q10 |
|
q0¸ |
q11¸ |
q11 |
|
q12¸Л |
q01 |
q12 |
|
q131 |
q121Л |
q13 |
|
q0¸ |
q01 |
Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина ¸11¸11¸; слово (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).
Вариант 5. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:
|
|
¸ |
1 |
q1 |
|
q2¸Л |
q01 |
q2 |
|
q5¸ |
q3¸ |
q3 |
|
q4¸Л |
q01 |
q4 |
|
q51 |
q41Л |
q5 |
|
q0¸ |
q61Л |
q6 |
|
q0¸ |
q7¸ |
q7 |
|
q8¸П |
q01 |
q8 |
|
q91 |
q81П |
q9 |
|
q0¸ |
q101Л |
q10 |
|
q0¸ |
q11¸ |
q11 |
|
q12¸Л |
q01 |
q12 |
|
q131 |
q121Л |
q13 |
|
q0¸ |
q01 |
Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина слово
8
1¸111¸1111¸; (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).
Вариант 6. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:
|
|
¸ |
1 |
q1 |
|
q2¸Л |
q01 |
q2 |
|
q5¸ |
q3¸ |
q3 |
|
q4¸Л |
q01 |
q4 |
|
q51 |
q41Л |
q5 |
|
q0¸ |
q61Л |
q6 |
|
q0¸ |
q7¸ |
q7 |
|
q8¸П |
q01 |
q8 |
|
q91 |
q81П |
q9 |
|
q0¸ |
q101Л |
q10 |
|
q0¸ |
q11¸ |
q11 |
|
q12¸Л |
q01 |
q12 |
|
q131 |
q121Л |
q13 |
|
q0¸ |
q01 |
|
Изображая на каждом такте работы машины получающуюся кон- |
|
фигурацию, |
определите, в какое слово перерабатывает машина слово |
|
¸1¸111¸; 11 |
(в начальный момент времени машина находится в состоянии |
|
q1 |
и обозревает крайнюю правую ячейку, в которой записан пустой символ |
|
¸; |
в следующей слева ячейке уже записан символ 1). |
|
|
Вариант 7. Машина Тьюринга с внешним алфавитом A = f¸; 1g и ал- |
фавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:
|
|
¸ |
1 |
q1 |
|
q2¸Л |
q01 |
q2 |
|
q5¸ |
q3¸ |
q3 |
|
q4¸Л |
q01 |
q4 |
|
q51 |
q41Л |
q5 |
|
q0¸ |
q61Л |
q6 |
|
q0¸ |
q7¸ |
q7 |
|
q8¸П |
q01 |
q8 |
|
q91 |
q81П |
q9 |
|
q0¸ |
q101Л |
q10 |
|
q0¸ |
q11¸ |
q11 |
|
q12¸Л |
q01 |
q12 |
|
q131 |
q121Л |
q13 |
|
q0¸ |
q01 |
9
Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина слово 1¸11¸1111¸; (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).
Вариант 8. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:
|
|
¸ |
1 |
q1 |
|
q2¸Л |
q01 |
q2 |
|
q5¸ |
q3¸ |
q3 |
|
q4¸Л |
q01 |
q4 |
|
q51 |
q41Л |
q5 |
|
q0¸ |
q61Л |
q6 |
|
q0¸ |
q7¸ |
q7 |
|
q8¸П |
q01 |
q8 |
|
q91 |
q81П |
q9 |
|
q0¸ |
q101Л |
q10 |
|
q0¸ |
q11¸ |
q11 |
|
q12¸Л |
q01 |
q12 |
|
q131 |
q121Л |
q13 |
|
q0¸ |
q01 |
Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина 11¸1¸11¸; слово (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).
Вариант 9. Машина Тьюринга с внешним алфавитом A = f¸; 1g и алфавитом внутренних состояний Q = fq0; q1; : : : ; q12; q13g определяется следующей функциональной схемой:
|
|
¸ |
1 |
q1 |
|
q2¸Л |
q01 |
q2 |
|
q5¸ |
q3¸ |
q3 |
|
q4¸Л |
q01 |
q4 |
|
q51 |
q41Л |
q5 |
|
q0¸ |
q61Л |
q6 |
|
q0¸ |
q7¸ |
q7 |
|
q8¸П |
q01 |
q8 |
|
q91 |
q81П |
q9 |
|
q0¸ |
q101Л |
q10 |
|
q0¸ |
q11¸ |
q11 |
|
q12¸Л |
q01 |
10