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

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

• # Чему равна глубина схемы S3, реализующей функцию сложения трехбитовых чисел?
• # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв b превосходит количество букв a не менее чем на 2. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?
• # Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными. L1 = { wbw | w = an , n > 0 }, L2 = { bwwb | w = an , n > 0 }, L3 = { (ab)nam | n, m > 0 }.
• # Предположим, что в некоторой конфигурации машины Тьюринга M на ленте записано слово w в алфавите Σ, не содержащем символов ∧ и *, но головка "заблудилась" – она наблюдает символ ∧ и не знает левее или правее слова w находится. Какие из следующих программ помогут найти начало слова w, т.е. любую конфигурацию вида q ∧k w или w∧k q ∧ (k > 0) переведут в конфигурацию q'w ? (В текстах программ a – это произвольный символ из Σ, используемые состояния: q, q', l, r, l1, r1 , l2 , r2, l3, r3, l4) P1: q ∧ →​ l1 * Л, l1∧→​ r * П, l1a→​ l2a П, l2 a→​ l2 a Л, l2 ∧→​ q'∧ П, r∧ →​ r ∧ П, r *→​ r1 ∧ П, r1 ∧→​ l * Л, l ∧→​ l ∧ Л, l *→​ l1 ∧ Л, r1 a→​ r2a Л, r2 ∧→​ r2∧ Л, r2 *→​ r3∧ П, r3∧→​ r3∧ П, r3 a→​ q'a Н. P2: q ∧ →​ l1 * Л, l1∧→​ r * П, l1a→​ l2a П, l2 ∧→​ l2∧ П, l2 *→​ l3∧ Л, l3 ∧→​ l3∧ Л, l3 a→​ q'a Н, r∧ →​ r ∧ П, r *→​ r1 ∧ П, r1 ∧→​ l * Л, l ∧→​ l ∧ Л, l *→​ l1 ∧ Л, r1 a→​ r2a Л, r2 ∧→​ r2∧ Л, r2 *→​ r3∧ П, r3∧→​ r3∧ П, r3 a→​ q'a Н. P3: q ∧ →​ l1 * Л, l1∧→​ r * П, l1a→​ l2a П, l2 ∧→​ l2∧ П, l2 *→​ l3∧ Л, l3 ∧→​ l3∧ Л, l3 a→​ l4 a Л, l4 a→​ l4 a Л, l4 ∧→​ q'∧ П, r∧ →​ r ∧ П, r *→​ r1 ∧ П, r1 ∧→​ l * Л, l ∧→​ l ∧ Л, l *→​ l1 ∧ Л, r1 a→​ r2a Л, r2 ∧→​ r2∧ Л, r2 *→​ r3∧ П, r3∧→​ r3∧ П, r3 a→​ q'a Н.
• # Приведенные ниже машины Тьюринга Mi (i= 1,2,3,4) M1 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; Зам(#, |); Выч1) enddo; Выб22 M2 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; par# (Пуст, Коп#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб22 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 аргументов: x1*…*xi*…*xn ⇐ xi ,Нульin - выдает 1, если i-ый аргумент из n аргументов равен ∧ (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |i , i >0),Выч1 – вычитает единицу в унарной системе: |j ⇐ |j-1 (| ⇐ ∧, ∧ ⇐ ∧) Какая из этих машин вычисляет функцию f(x) = xx в унарном кодировании, т.е. переводит вход |x в выход |y, где y = xx (пусть f(0)=0) ?