Пусть задана линейная программа P со входными переменными X1, X2, X3:

Y = ¬X1;

Z = ¬X2;

U = ¬X3;

Y = Y ∧ X2;

W = X2 ∧ X3;

Y = Y ∧ U;

Y = W ∨ Y ;

Z = Z ∨ Y.

Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?

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

• # Пусть задан недетерминированный конечный автомат M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={4, 5}, Φ> с программой Φ: 0 b →​ 1, 0 →​ 2, 1 a →​ 2, 1 b →​ 4, 2 →​ 3, 2 →​ 5, 3 a →​ 4, 3 b →​ 2, 4 →​ 5 Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?
• # Какой язык L является конкатенацией двух языков: L1= {a, ab, abba} и L2= { ε, a, b, ba}?
• # Какой язык L является конкатенацией двух языков: L1= {ε, b, ab, abba} и L2= { a, b, ba}?
• # Пусть S={aaa, aba, baa, bba} Какая из следующих фраз описывает итерацию 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>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]