КР БИС 31з
.pdfq12 |
|
q131 |
q121Л |
q13 |
|
q0¸ |
q01 |
Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина слово ¸11¸111¸; 11 (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ ¸; в следующей слева ячейке уже записан символ 1).
Вариант 10. Машина Тьюринга с внешним алфавитом 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).
Задача 14.
Вариант 1. Дан автомат функцией меток дуг: '(q0; q1) = b; c; '(q0; q2) =
a; '(q0; q3) = a; '(q1; q0) = a; c; '(q1; q2) = a; b; '(q1; q3) = a; c; '(q2; q1) = c; a; '(q2; q3) = c; Найти язык автомата и привести пример какого либо
слова из этого языка.
Вариант 2. Дан автомат функцией меток дуг: '(q0; q1) = ¸; '(q0; q2) =
a; '(q1; q0) = b; a; '(q1; q2) = a; '(q1; q3) = b; '(q2; q3) = b: Найти язык автомата и привести пример какого либо слова из этого языка.
Вариант 3. Дан автомат функцией меток дуг: '(q0; q1) = a; c; '(q0; q3) =
a; b; '(q0; q2) = c; '(q1; q3) = a; '(q2; q3) = c; a; '(q3; q1) = b; '(q1; q1) = a: Найти язык автомата и привести пример какого либо слова из этого
языка.
11
Вариант 4. Дан автомат функцией меток дуг: '(q0; q1) = ¸; '(q0; q2) =
a; '(q1; q0) = b; a; '(q1; q2) = a; '(q1; q3) = b; '(q2; q3) = b: Найти язык автомата и привести пример какого либо слова из этого языка.
Вариант 5. Дан автомат функцией меток дуг: '(q0; q1) = a; b; c;
'(q0; q2) = a; '(q0; q3) = a; '(q1; q0) = a; c; '(q1; q2) = a; b; '(q1; q3) = a; '(q2; q1) = c; a; '(q2; q3) = c; Найти язык автомата и привести пример
какого либо слова из этого языка.
Вариант 6. Дан автомат функцией меток дуг: '(q0; q1) = ¸; '(q0; q2) =
a; b; '(q1; q0) = b; a; '(q1; q2) = a; '(q1; q3) = b; '(q2; q3) = b: Найти язык автомата и привести пример какого либо слова из этого языка.
Вариант 7. Дан автомат функцией меток дуг: '(q0; q1) = a; '(q0; q3) =
a; b; '(q0; q2) = c; '(q1; q3) = a; '(q2; q3) = c; a; '(q3; q1) = b; c; '(q1; q1) = a: Найти язык автомата и привести пример какого либо слова из этого
языка.
Вариант 8. Дан автомат функцией меток дуг: '(q0; q1) = ¸; '(q0; q2) =
a; '(q1; q0) = a; '(q1; q2) = a; '(q1; q3) = b; c; '(q2; q3) = b: Найти язык автомата и привести пример какого либо слова из этого языка.
Вариант 9. Дан автомат функцией меток дуг: '(q0; q1) = a; c; '(q0; q3) =
a; '(q0; q2) = c; '(q1; q3) = a; '(q2; q3) = c; a; '(q3; q1) = b; c '(q1; q1) = a:
Найти язык автомата и привести пример какого либо слова из этого языка.
|
Вариант 10. Дан автомат функцией меток дуг: '(q0; q1) = ¸; '(q0; q2) = |
||||
a; |
'(q1; q0) = b; a; '(q1; q2) = a; c; b |
'(q1; q3) = b; |
'(q2; q3) = b: Найти язык |
||
автомата и привести пример какого либо слова из этого языка. |
|||||
|
Задача 15. |
|
|
|
|
|
Вариант 1. Сконструировать машину Тьюринга, которая вычисляет |
||||
функцию f(x; y) = x + y; |
x; y – натуральные числа. Исходные данные |
||||
кодированы в алфавите V |
= f¸; 1g: |
|
|
|
|
|
Вариант 2. Сконструировать машину Тьюринга, которая вычисляет |
||||
функцию |
|
0; |
если |
x = 0; |
|
|
|
: |
|||
|
f(x) = x¡1 = ½ x ¡ 1; |
если |
x > 0 |
||
x |
– натуральное число. Исходные данные кодированы в алфавите V = |
||||
f¸; 1g: |
|
|
|
|
|
|
Вариант 3. Сконструировать машину Тьюринга, которая вычисляет |
||||
функцию |
0; |
если |
x = 0; |
||
|
|
||||
|
sg(x) = ½ 1; |
если |
x > 0 |
||
x |
– натуральное число. Исходные данные кодированы в алфавите V = |
||||
f¸; 1g: |
|
|
|
|
|
|
4. Сконструировать машину Тьюринга, которая вычисляет функцию |
||||
|
|
0; |
если |
x = 0; |
|
|
sg(x) = ½ 1; |
если |
x > 0 |
||
x – натуральное число. Исходные данные кодированы в алфавите V = f¸; 1g:
12
Вариант 5. Сконструировать машину Тьюринга, которая вычисляет
функцию f(x; y) = x ¡ y; x; y |
– натуральные числа, x > y . Исходные |
данные кодированы в алфавите V |
= f¸; 1g: |
Вариант 6. Сконструировать машину Тьюринга, которая вычисляет
функцию |
½ x + 1; |
если |
x > 0 |
f(x) = x¡1 = |
|||
: |
0; |
если |
x = 0; |
x; – натуральное число. Исходные данные кодированы в алфавите V = f¸; 1g:
Вариант 7. Сконструировать машину Тьюринга, которая вычисляет
функцию |
½ |
11; |
если |
x > 0 |
g(x) = |
||||
|
|
1; |
если |
x = 0; |
x – натуральное число. Исходные данные кодированы в алфавите V = f¸; 1g:
8. Сконструировать машину Тьюринга, которая вычисляет функцию
g(x) = ½ |
111; |
если |
x = 0; |
11; |
если |
x > 0 |
x – натуральное число. Исходные данные кодированы в алфавите V = f¸; 1g:
Вариант 9. Сконструировать машину Тьюринга, которая вычисляет
функцию |
|
|
|
g(x) = ½ |
0; |
если |
x = 11; |
1; |
если |
x 6= 0 |
x – натуральное число. Исходные данные кодированы в алфавите V = f¸; 1g:
10. Сконструировать машину Тьюринга, которая вычисляет функцию
g(x) = ½ |
111; |
если |
x > 0 |
|
0; |
если |
x = 0; |
x – натуральное число. Исходные данные кодированы в алфавите V = f¸; 1g:
13