Пусть задана логическая схема S=(V, E) : V= {a (X), b(Y), c(Z), d(V), e(∧), f(∧),g(¬),h(¬), i(∧), k(∧), m(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция), E= { (a, h), (b, f), (c, e), (c, g), (d, f), (e, i), (f ,i), (f ,k), (g,, k), (h,e),(i, m), (k, m) }. Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m? P1: P2: P3: X = ¬X; h = ¬X; X = ¬X; Z = ¬Z; g = ¬Z; X = X ∧ Z; X = X ∧ Z; e = h ∧ Z; Z = ¬Z; Y = Y ∧ V; f = Y ∧ V; V = Y ∧ V; Y = Y ∧ X; k = f ∧ g; V = X ∧ V; Z = Y ∧ Z; i = e ∧ f; Y = V ∧ Z; Z = Y ∨ Z. Z = i ∨ k. Z = Y ∨ V.

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

• # Постройте минимальные УБДР для функции f(x1, x2, x3, x4)= (x1 ∨ x2) + ( x3 ∨ x4) относительно двух упорядочений переменных: a) x1 < x2 < x3 < x4 иb) x1 < x3 < x2 < x4. Определите сложности этих двух схем.
• # Какие из следующих трех автоматов С1 , С2 , С3 распознают язык, представляемый регулярным выражением 1 (01)*? С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1>, С2 = < {0,1}, {q, p, r, s }, q, F2={p, s}, Φ2>, С3 = < {0,1}, {q, p, r, s, t}, q, F3={ p, s}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
• # Пусть язык 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
• # Пусть П× - это программа, которая вычисляет функцию Ф× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x целую часть частного [ x/y] (пусть при y=0 результат равен 0)? [Большая Картинка]
• # Пусть машина Тьюринга 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?