Пусть задана УБДР D=(V,E): V={v1 (x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), v9(w), 0, 1} (в скобках после имени вершины указана переменная, которой она помечена), E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 1), (v2, v5; 0), (v3, v4; 1), (v3, v6; 0), (v4, v7; 1), (v4, v8; 0), (v5, v8; 1), (v5, v9; 0), (v6, v8; 1), (v6, v9; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 0), (v8, 1; 1), (v9, 0; 0), (v9, 1; 1) } ( для каждого ребра третий параметр после ; - его метка 0 или 1). Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.

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

• # Пусть задана логическая схема 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. Определите сложности этих двух схем.
• # Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>, где [Большая Картинка] Какие из следующих трех слов распознаются автоматом A? W= aaabaabab, V= abababaab, U= bbabbbababa
• # Пусть задан ДКА A =< {a, b, c}, {0, 1, 2, 3}, 0, F= {2}, ΦA > с программой ΦA: { 0 a →​ 1, 0 b →​ 1, 0 c →​ 0, 1 a →​ 1, 1 b →​ 2, 1 c →​ 2, 2 a →​ 3, 2 b →​ 3, 2 c →​ 2, 3 a →​ 3, 3 b →​ 3, 3 c →​ 3} и гомоморфизм h: {a, b, c}* →​ {0, 1}*: h(a) = 01, h(b) = 11, h(c) = ε Какие из следующих трех автоматов С1 , С2, С3 распознают гомоморфный образ h(LA)? С1 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2, q3, q4, q5, q6, q7}, 0, F1={1,2}, Φ1>, С2 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2 }, 0, F2={ 1,2}, Φ2>, С3 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2 }, 0, F3={0,1,2}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
• # Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами? P1: x := y+1; z:= x + 1; если x +1 < z то y := z иначе y:=x конецP2: x := y+1; z:= x +1; если x = z то y := z иначе y:=x конецP3: x := y+1; u:= z +1; пока u = z +1 делай y := z; u := u+1 все