В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=2, j=4. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M24, в котором q - начальное, а p – заключительное состояние. Какие из следующих программ могут быть использованы в качестве программы для M24 ? (В текстах программ a,b,c,d – это произвольные символы из алфавита{∧, |})

P1: q <a, b, c, |> →​ q <a, | , c, | > П , s <a, | , c, | > →​ s <a, | , c, | > Л , q <a, |, c, ∧> →​ q <a, ∧ , c, ∧> П , s <∧, ∧, ∧, ∧> →​ p <∧, ∧ , ∧, ∧> П. q <a, ∧, c, ∧> →​ s <a, ∧ , c, ∧> Л ,

P2: q <a, |, c, d> →​ q <a, | , c, | > П , s <a, | , c, | > →​ s <a, | , c, | > Л , q <a, ∧, c, |> →​ q <a, ∧ , c, ∧> П , s <a, ∧, c, ∧> →​ p <a, ∧ , c, ∧> П. q <a, ∧, c, ∧> →​ s <a, ∧ , c, ∧> Л ,

P3: q <a, b, c, |> →​ q <a, | , c, | > П , s <a, | , c, | > →​ s <a, | , c, | > Л , q <a, b, c, ∧> →​ s <a, ∧ , c, ∧> Л , s <a, ∧, c, ∧> →​ p <a, ∧ , c, ∧> П.

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

• # В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M43, в котором q - начальное, а p – заключительное состояние. Какие из следующих программ могут быть использованы в качестве программы для M43 ? (В текстах программ a,b,c,d – это произвольные символы из алфавита{∧, |}) P1: q <a, b, |, d > →​ q < a, b , |, | > П , s < a, ,b | , | > →​ s < a, b, | , | > Л , q < ∧, b, ∧, d> →​ s < ∧ , b, ∧, d > Л , s < ∧, ∧, ∧, ∧> →​ p < ∧, ∧, ∧, ∧> П ,P2: : q <a, b, c, | > →​ q < a, b , c, | > П , s < a , b, |, d > →​ s < a , b, |, | > Л , q <a, b, |, d > →​ q < a, b, |, d > П , s < ∧, ∧, ∧, ∧> →​ p < ∧, ∧, ∧, ∧> П. q <a, b, ∧, ∧> →​ s < a , b, ∧, ∧ > Л , s < a , b, ∧, | > →​ s < a , b, ∧, ∧ > Л,P3: : q <a, b, |, d > →​ q < a, b , |, | > П , s < a, ,b | , | > →​ s < a, b, | , | > Л , q <a, b, ∧, | > →​ q < a, b, ∧, ∧ > П , s < ∧, ∧, ∧, ∧> →​ p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> →​ s < ∧ , b, ∧, d > Л ,
• # Пусть задан недетерминированный конечный автомат M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={4, 5}, Φ> с программой Φ: 0 b →​ 1, 1 a →​ 2, 1 b →​ 3, 2 a →​ 3, 2 b →​ 1, 3 →​ 4, 4 a →​ 5, 4 →​ 5, 5 →​ 2 Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?
• # Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными. L1 = { wbw | w = an , n > 0 }, L2 = { bwwb | w = an , n > 0 }, L3 = { (ab)nam | n, m > 0 }.
• # Пусть структурированная программа P: x:= y+1; v:= u+1; пока x < v делай если y < x то y := y+1; u := u+1 иначе x := x +1 конец все начинает работу в состоянии σ : σ(x) =0, σ(y) =2, σ(u) = 5, σ(v) =0В каком из следующих состояний σ1 она завершит свою работу?
• # Пусть функция rm(x, y) = y mod x равна остатку от деления y на x ( rm(0,y)=y), а функция p(n) принимает значение 1, если число n простое, и равна 0 для составных n (p(0)=p(1)=0, p(2)=p(3)=1, …). Какое из следующих выражений определяет при x >1 число mp(x), равное произведению различных простых делителей числа x? Например, mp(2)=mp(4)=mp(8) =2, mp(12)=2x3=6, … (Пусть mp(0)=mp(1)=1).