Главная /
Введение в схемы, автоматы и алгоритмы /
В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты н
В доказательстве теоремы 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 }
,– множество состояний M31
, в котором q - начальное, а p – заключительное состояние.
Какие из следующих программ могут быть использованы в качестве программы для M31
?
(В текстах программ a,b,c,d
– это произвольные символы из алфавита{∧, |}
)
P1: q <|, b, c, d > → q < |, b , |, d > П , s < | , b, |, d > → s < | , b, |, d > Л , q <∧, b, |, d > → q < ∧, b, ∧, d > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л ,
P2: : q <|, b, c, d > → q < |, b , c, d > П , s < ∧ , b, |, d > → s < | , b, ∧, d > Л , q <a, b, |, d > → q < a, b, |, d > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л , s < | , b, c, d > → s < | , b, |, d > Л ,
P3: : q <|, b, c, d > → q < |, b , |, d > П , s < | , b, |, d > → s < | , b, |, d > Л , q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П.
вопрос
P1: q <|, b, c, d > → q < |, b , |, d > П , s < | , b, |, d > → s < | , b, |, d > Л , q <∧, b, |, d > → q < ∧, b, ∧, d > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л ,
P2: : q <|, b, c, d > → q < |, b , c, d > П , s < ∧ , b, |, d > → s < | , b, ∧, d > Л , q <a, b, |, d > → q < a, b, |, d > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л , s < | , b, c, d > → s < | , b, |, d > Л ,
P3: : q <|, b, c, d > → q < |, b , |, d > П , s < | , b, |, d > → s < | , b, |, d > Л , q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П.
Правильный ответ:
только
P1
только
P2
только
P3
P1
и P2
P1
и P3
P2
и P3
ни одна
Сложность вопроса
95
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Я провалил сессию, какого чёрта я не нашёл этот великолепный сайт с ответами интуит до этого
13 май 2019
Аноним
Экзамен сдал и ладушки. лол
25 янв 2019
Аноним
Какой человек ищет эти вопросы интуит? Это же не сложно
12 окт 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # В теореме 20.5 была доказана неразрешимость проблемы останова: по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть Mh0= {n | ФПn,y (0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе монотонности вычисляемой ею функции: M mon = {n | для любых x1 и x2, если x1 < x2, то ФПn,y (x1) < ФПn,y (x2)}. Какие из следующих функций сводят Mh0 к M mon ? f1(n) = номер программы: 'xn:=x; x:= 0; Пn ; y:= xn'. (здесь переменная xn не входит в Пn ) f2(n) = номер программы: 'Пn ; y:= x'. f3(n) = номер программы: 'y:= x; x:= 0; Пn ; y:= y+1'.
- # Какие из следующих УБДР являются сокращенными? [Большая Картинка]
- # Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>, где [Большая Картинка] Какие из следующих трех слов распознаются автоматом A? W= aaabbabab, V= babbbabba, U= ababaaab
- # Заданы два НКА: 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> , где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
- # Три машины Тьюринга Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы: [Большая Картинка] Какие из этих машин переводят любую начальную конфигурацию вида q a2n b в заключительную конфигурацию ! b an (n ≥ 0 )?