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

Правильный ответ:

• # В доказательстве теоремы 10.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g1, f3), требовалась м.Т. M1, которая переводит конфигурацию вида |x* |y в конфигурацию |y * |x* ∧ *|g(x) , используя м.Т. Mg, вычисляющую функцию g(x). Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M1 ? P1 = Коп# ; par# (par* (Чист, Пуст); Зам(*,∧ ) , par* (Пуст ,Чист); Зам(*,∧ ) ); par# (Пуст, Коп* ); par* (Пуст, +1; +1; Зам(|,∧ ); Зам(|,* )); par* (Пуст, Пуст, Mg); Зам( #,* ) P2 = Коп# ; par# (par* (Чист, Пуст); Зам(*,∧ ) , par* (Пуст ,Чист); Зам(*,∧ ) ); par# (Пуст, Коп# ); par# (Пуст, Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* ) P3 = Коп* ; par* (Чист, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par# (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ) В этих определениях участвуют следующие простые машины Тьюринга: Копa – копирует вход после разделительного символа a : w ⇐ w a w;Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );Пуст – не изменяет аргумент: w ⇐ w ;Чист – стирает аргумент: w ⇐ ∧ ;+1 – прибавляет 1 к аргументу: |x ⇐ |x+1
• # Пусть язык 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 =< {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) = ε. Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный образ h(LA)? С1 = < {0, 1}, {0, 1, 2, q1, q2, q3}, 0, F1={2}, Φ1>, С2 = < {0, 1}, {0, 1, 2, q1, q2 }, 0, F2={2}, Φ2>, С3 = < {0, 1}, {0, 2, (q1, q2), (0,1), (1, 2), !}, 0, F3={2, (1,2)}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
• # Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = x2 + x?
• # Пусть c2(x, y) = 2x(2y+1) -1 - это функция нумерации пар, а c21(z) и c22(z) - это соответствующие обратные функции такие, что c2(c21(z), c22(z)) = z для всех z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функций, значения которых на аргументе (y+1) зависят от их значений в двух предыдущих точках y-1 и y. Рассмотрим функцию F(x), заданную равенствами: F(0) = 0, F(1) = 1, F(y+2) = F(y) + F(y+1) +1. Положим G(y) = c2(F(y), F(y+1)). Так как F(y) = c21(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность G. Определите, какая из следующих примитивных рекурсий задает G.