Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ?

(a) если A ≤m B, то (N \A) ≤m (N \B) ,

(b) A ≤m C и B ≤m C для C= {2x | x ∈ A} ∪ {2x+1 | x ∈ B},

(c) сохраняет свойство неразрешимости: если A ≤m B и A - неразрешимо, то и B неразрешимо .

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

• # Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>, где [Большая Картинка] Какие из следующих трех слов распознаются автоматом A? W= aaabbabab, V= babbbabba, U= ababaaab
• # Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>, [Большая Картинка] Какой из следующих языков распознает автомат A ?
• # Пусть задан недетерминированный конечный автомат (без пустых переходов) M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программой Φ: q 0 →​ p, q 0 →​ s, q 1→​ q, p 0 →​ q, p 0 →​ p, s 1 →​ q, s 1 →​ p Какие из следующих трех ДКА эквивалентны M? M1 = < {0, 1}, {q, ps, pq, pqs}, q, F1={ ps, pq, pqs }, Φ1> с программой Φ1: q 0 →​ ps, q 1 →​ q, ps 0 →​ pq, ps 1 →​ pq, pq 0 →​ pqs, pq 1 →​ q, pqs 0 →​ pqs, pqs 1 →​ pq M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F2={p, ps, pq, pqs }, Φ2> с программой Φ2: q 0 →​ ps, q 1 →​ q, p 0 →​ pq, p 1 →​ q, ps 0 →​ qs, ps 1 →​ pq, pq 0 →​ pqs, pq 1 →​ q, qs 0 →​ ps, qs 1 →​q, pqs 0 →​ pqs, pqs 1 →​ pq, ∅ 0 →​∅, ∅ 1 →​∅ M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F3={ p, ps, pq, pqs }, Φ3> с программой Φ3: q 0 →​ ps, q 1 →​ q, p 0 →​ pq, p 1 →​ q, s 0 →​∅, s 1 →​pq, ps 0 →​ pq, ps 1 →​ pq, pq 0 →​ pqs, pq 1 →​ q, qs 0 →​ ps, qs 1 →​q, pqs 0 →​ pqs, pqs 1 →​ pq, ∅ 0 →​∅, ∅ 1 →​∅
• # Заданы два НКА: A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ΦA > с программой ΦA: 0 a →​ 1, 0 a →​ 2, 0 b →​ 0, 1 a →​ 2, 1 b →​ 1, 2 a →​ 3, 2 b →​ 2, 3 a →​ 3, 3b →​ 3 и B =< {a, b}, {q0, q1, q2}, q0, {q2}, ΦB > с программой ΦB: q0 a →​ q1, q1 b →​ q0, q1 a →​ q2, q2 b →​ q1 Какие из следующих трех НКА С1 , С2 , С3 распознают конкатенацию LA? LB языков, распознаваемых автоматами A и B? С1 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F1={ q2}, Φ1>, С2 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F2={ q2}, Φ2>, С3 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F3={ q2}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
• # Приведенные ниже машины Тьюринга 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) ?