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

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

• # Какие из следующих трех автоматов С1 , С2 , С3 распознают язык, представляемый регулярным выражением 0(10 +1)*? С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1>, С2 = < {0,1}, {q, p, r, s }, q, F2={p, r}, Φ2>, С3 = < {0,1}, {q, p, r, s, t}, q, F3={ p, r, s}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
• # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые начинаются на aa и содержат подслово bb Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* →​ {0, 1}* где h(a) = 01, h(b) = 11, h(c) = ε ?
• # Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {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 Н.
• # Пусть машина Тьюринга M построена из следующих простых машин Тьюринга: Копa –копирует вход после разделительного символа a : w ⇐ w a w; Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 ); Сум - складывает два аргумента в унарной системе: |x * |y ⇐ |x+y ; Умн - умножает два аргумента в унарной системе: |x * |y ⇐ |xy; с помощью операций последовательного и параллельного применения следующим образом: M = Коп# ; par#( Коп* , Коп* ); par#( Умн, Сум); Зам(#, *); Сум Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?