Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?

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

• # Постройте минимальные УБДР для функции f(x1, x2, x3, x4)= (x1 ∨ x2) + ( x3 ∨ x4) относительно двух упорядочений переменных: a) x1 < x2 < x3 < x4 иb) x1 < x3 < x2 < x4. Определите сложности этих двух схем.
• # Пусть S={aaa, aab, aba, abb, baa, bab, bba, bbb} Какая из следующих фраз описывает итерацию S* этого языка?
• # Заданы два НКА: A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ΦA > с программой ΦA: 0 a →​ 1, 0 b →​ 3, 1 a →​ 3 1 b →​ 2, 2 a →​ 3, 2 b →​ 2, 3 a →​ 3, 3b →​ 3 и B =< {a, b}, {q0, q1, q2}, q0, {q2}, ΦB > с программой ΦB: q0 a →​ q0, q0 b →​ q1, q1 a →​ q1, q1 a →​ q2 Какие из следующих трех НКА С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, q1, q2}, 0, F3={ q2}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
• # Пусть заданы три функции: f(x,y,z) = xy +z, g(x,y) = 2x + y, h(x) =2x2 Какую функцию F(x1,x2) задает выражение [f; [h; I21 ] [g; [h; I22 ], I22], I22] ?
• # В конструкции для параллельной композиции машин Тьюринга на этапах 3 и 5 участвует служебная машина, назовем ее CHANGE, меняющая местами аргументы, точнее переводящая любую конфигурацию вида x * q y (x и y – слова в алфавите Σ, не содержащем символов ∧, * и # , q – начальное состояние) в конфигурацию y* q’ x (q' – заключительное состояние). Пусть Q={ q, s, p, r, q'}∪ {pa | a ∈ Σ} – множество состояний CHANGE. Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для CHANGE ? (В текстах программ a – это произвольный символ из Σ, а b - это произвольный символ из Σ ∪ {*, #} ). P1: q b →​ q b П , q ∧ →​ s # Л, s b →​ s b Л, s ∧ →​ p ∧ П, p a →​ pa ∧П, p * →​ r ∧П, pa b →​ pa b П, pa ∧ →​ s a Л, r a →​ r a П , r # →​ q’ * П. P2: q a →​ q a П , q ∧ →​ s * Л, s b →​ s b Л, s ∧ →​ p ∧ П, p a →​ pa ∧П, p * →​ r ∧П, pa b →​ pa b П, pa ∧ →​ s a Л, r a →​ r a П , r*→​ q’ * П. P3: q a →​ q a П , q ∧ →​ s * Л, s b →​ s b Л, s ∧ →​ p ∧ П, p a →​ pa ∧П, p * →​ q’ * П, pa b →​ pa b П, pa ∧ →​ s a Л.