Пусть задан недетерминированный конечный автомат (без пустых переходов) M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программой Φ: q 0 →​ p, q 0 →​ s, p 0 →​ q, p 0 →​ s, p 1 →​ p, s 1 →​ p Какие из следующих трех ДКА эквивалентны M?

M1 = < {0, 1}, {q, p, ps, qs}, q, F1={p, ps}, Φ1> с программой Φ1: q 0 →​ ps, q 1 →​ p, p 0 →​ qs, p 1 →​ p, ps 0 →​ qs, ps 1 →​ p, qs 0 →​ ps, qs 1 →​ p

M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F2={p, ps, pq, qps}, Φ2> с программой Φ2: q 0 →​ ps, q 1 →​ p, p 0 →​ qs, p 1 →​ p, s 0→​ ∅, s 1→​ p, ps 0 →​ qs, ps 1 →​ p, qs 0 →​ ps, qs 1 →​ p, qp 0 →​ ps, qp 1 →​ p, qps 0 →​ qps, qps 1 →​ p, ∅ 0 →​∅, ∅ 1 →​∅.

M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F3={ p, ps, pq, qps }, Φ3> с программой Φ3: q 0 →​ ps, q 1 →​ p, p 0 →​ qs, p 1 →​ p, s 1→​ p, ps 0 →​ qs, ps 1 →​ p, qs 0 →​ qps, qs 1 →​qps, qp 0 →​ ps, qp 1 →​ p, qps 0 →​ qps, qps 1 →​ p. ∅ 0 →​∅, ∅ 1 →​ ∅

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

• # В теореме 20.5 была доказана неразрешимость проблемы останова: по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть Mh0= {n | ФПn,y (0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе бесконечности множества ее результатов: Minf = {n | множество значений ФПn,y (x) бесконечно}. Какие из следующих функций сводят Mh0 к Minf ? f1(n) = номер программы: ' x:= 0; Пn ; y:= x '. f2(n) = номер программы: 'xn:=x; x:= 0; Пn ; y:= xn '. (здесь переменная xn не входит в Пn )f3(n) = номер программы: 'y:= x; x:= 0; Пn ; y:= y+1'.
• # Пусть задан конечный автомат - преобразователь A = <ΣX ={0, 1} ΣY= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>, где [Большая Картинка] Какое входное слово автомат А перерабатывает в выходное слово ТАРАРА?
• # Какие из следующих трех конечных автоматов Ai = < {a,b}, {0, 1, 2, 3, 4}, 0, F={1}, Φi> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые начинаются на b и содержат число букв a , кратное 3 ? [Большая Картинка]
• # Пусть структурированная программа P: x:= y+1; y := u+1; v := z+1; если x < v то если x = y то z := y+1 иначе z := x конец иначе z :=x +1 конец начинает работу в состоянии σ : σ(x) =0, σ(y) =3, σ(z) =5, σ(u) = 4, σ(v) =2В каком из следующих состояний σ1 она завершит свою работу?
• # Пусть c2(x, y) = 2x(2y+1) -1 - это функция нумерации пар, а c21(z) и c22(z) - это соответствующие обратные функции такие, что c2(c21(z), c22(z)) = z для всех z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функций, значения которых на аргументе (y+1) зависят от их значений в двух предыдущих точках y-1 и y. Рассмотрим функцию F(x), заданную равенствами: F(0) = 1, F(1) = 2, F(y+2) = F(y) × F(y+1). Положим G(y) = c2(F(y), F(y+1)). Так как F(y) = c21(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность G. Определите, какая из следующих примитивных рекурсий задает G.