Пусть структурированная программа P: x:= y+1; z := x+1; y := z+1; y:= y+1; z:= y; z := z +1 ; x := x+1 начинает работу в состоянии σ : σ(x) = 2, σ(y) =3, σ(z) =2В каком из следующих состояний σ1 она завершит свою работу?

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

• # В теореме 20.5 была доказана неразрешимость проблемы останова: по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть Mh0= {n | ФПn,y (0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе независимости ее результата от входа: Mconst= {n | существует константа c ∈ N такая, что ФПn,y (x) = c для всех x}. Какие из следующих функций сводят Mh0 к Mconst ? f1(n) = номер программы: ' x:= 0; Пn ; y:= 0'. f2(n) = номер программы: 'Пn ; y:= x'. f3(n) = номер программы: ' x:= 0; Пn ; y:= 0; y:= y+1'.
• # Какие из следующих схем реализуют в вершине a функцию, заданную формулой A = ¬ (a ∧ ¬b) ∨ ((b∨ c) ∧ (a ∧ ¬b)) ? [Большая Картинка]
• # [Большая Картинка] Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?
• # Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>, [Большая Картинка] Какой из следующих языков распознает автомат A ?
• # Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными. L1 = { ww | w = b2anb , n > 0 }, L2 = { b2anb | n > 0 }, L3 = { (ab)nanb | n > 0 }.