Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами?

P1: x := y+1; z:= 1; если x < z то y := z иначе y:=x конец

P2: x := y+1; z:= x +1; если x < z то y := z иначе y:=x конец

P3: x := y+1; z:= x +1; пока u < z делай y := z; u := u+1 все

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

• # Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ? (a) если A ≤m B, то (N \A) ≤m (N \B) , (b) A ≤m C и B ≤m C для C= {2x | x ∈ A} ∪ {2x+1 | x ∈ B},(c) сохраняет свойство неразрешимости: если A ≤m B и A - неразрешимо, то и B неразрешимо .
• # [Большая Картинка] Какую булеву функцию реализует эта диаграмма? (В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)
• # [Большая Картинка] Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?
• # Пусть 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 →​ 2, 1 b →​ 1, 2 a →​ 1, 2 b →​ 3, 3 a →​ 3, 3b →​ 3 и B =< {a, b}, {q0, q1, q2}, q0, {q2}, ΦB > с программой ΦB: q0 b →​ q0, q0 b →​ q1, q1 a →​ q1, q1 a →​ q2, q2 b →​ q0 Какие из следующих трех НКА С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, q0, q1, q2}, 0, F3={ q2}, Φ3> , где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]