Пусть задана логическая схема S=(V, E) : V= {a (X1), b(X2), c(X3), d(¬),e(¬), f(∨),g(∨),h(∨), i(∧), k(∧) } (после имени вершины в скобках указана ее метка - переменная или булева функция), E= { (a, d), (a, g), (b, e), (b, f), (b, g), (c, f), (d, h), (e, h), (f,k), (g,i), (h, i), (i, k) }. Какую булеву функцию реализует схема S=(V, E) в вершине k? (В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов X1, X2 и X3)

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

• # Чему равна глубина схемы Sodd , реализующей функцию odd(X1, X2, …,Xn) = X1 + X2 + … Xn ?
• # Пусть задана УБДР D=(V,E): V={v1 (x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), , 0, 1} (в скобках после имени вершины указана переменная, которой она помечена), E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 0), (v2, v5; 1), (v3, v5; 1), (v3, v6; 0), (v4, v7; 0), (v4, v8; 1), (v5, v7; 0), (v5, v8; 1), (v6, v8; 1), (v6, v7; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 1), (v8, 1; 0)} ( для каждого ребра третий параметр после ; - его метка 0 или 1). Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.
• # На следующем рисунке представлены диаграммы двух конечных автоматов A =< {a,b}, {q,p}, q, {p}, ΦA> и B =< {a,b}, {1, 2, 3}, 1, {1, 2}, ΦB>, [Большая Картинка] распознающих языки LA и LB, соответственно. Какой из следующих автоматов является произведением A × B и какой язык он реализует? C = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2), (p,3)}, (q,0), F={(p,3)}, ΦC >, D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,1), (p,2)}, ΦD >, [Большая Картинка]
• # Пусть задан недетерминированный конечный автомат (без пустых переходов) M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программой Φ: q 0 →​ q, q 1 →​ s, q 1→​ p, p 0 →​ q, p 0 →​ p, s 0 →​ q, s 1 →​ p Какие из следующих трех ДКА эквивалентны M? M1 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F1={p, ps, pq, pqs }, Φ1> с программой Φ1: q 0 →​ q, q 1 →​ ps, p 0 →​ pq, p 1 →​ ∅, s 0 →​ q, s 1 →​ pq, ps 0 →​ pq, ps 1 →​ p, pq 0 →​ pq, pq 1 →​ p, qs 0 →​ q, qs 1 →​pq, pqs 0 →​ pq, pqs 1 →​ ps, ∅ 0 →​∅, ∅ 1 →​∅ M2 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F2={ p, ps, pq, pqs }, Φ2> с программой Φ2: q 0 →​ q, q 1 →​ ps, p 0 →​ pq, p 1 →​ q, s 0 →​ q, s 1 →​ pq, ps 0 →​ pq, ps 1 →​ p, pq 0 →​ pq, pq 1 →​ ps, qs 0 →​ q, qs 1 →​pq, pqs 0 →​ pq, pqs 1 →​ ps, ∅ 0 →​∅, ∅ 1 →​∅ M3 = < {0, 1}, {q, p, ps, pq, ∅ }, q, F3={ ps, pq, p }, Φ3> с программой Φ3: q 0 →​ q, q 1 →​ ps, ps 0 →​ pq, ps 1 →​ p, pq 0 →​ pq, pq 1 →​ ps, p 0 →​ pq, p 1 →​ ∅, ∅ 0 →​∅, ∅ 1 →​∅
• # Пусть машина Тьюринга 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 ;Пуст - не изменяет аргумент: w ⇐ w с помощью операций последовательного и параллельного применения следующим образом: M = Коп# ; par#( Коп* ; Умн, Пуст ); par#( Коп* ; Сум , Пуст ); Зам(#,?); Сум Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?