Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть задана логическая схема S=(V, E) : V= {a (X), b(Y), c(Z), d(V), e(∧), f(¬),g(¬),h(∧), i(∧), k(¬), m(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция), E= { (a, e), (b, f), (c, g), (d, e), (d, i), (e, k), (f, h), (
Пусть задана логическая схема S=(V, E)
:
V= {a (X), b(Y), c(Z), d(V), e(∧), f(¬),g(¬),h(∧), i(∧), k(¬), m(∨) }
(после имени вершины в скобках указана ее метка - переменная или булева функция),
E= { (a, e), (b, f), (c, g), (d, e), (d, i), (e, k), (f, h), (g,, h), (h, i),(i, m), (k, m) }
.
Какие из следующих линейных программ вычисляют в переменной Z
ту же функцию F(X,Y,Z,V)
, что и схема S
в вершине m
?
P1: P2: P3:
V = X ∧ V; f = ¬Y; Y = ¬Y;
V = ¬V; g = ¬Z; Z = ¬Z;
Y = ¬Y; e = X ∧ V; Z = Y ∧Z;
Z = ¬Z; k = ¬e; Z = Z ∧V;
Y = Y ∧ Z; h = f ∧ g; V = X ∧ V;
Z = Y ∧ V; i = h ∧ V; V = ¬V;
Z = V ∨ Z . Z = h ∨ k. Z = Z ∧ V.
вопрос
Правильный ответ:
только
P1
только
P2
только
P3
только
P1
и P3
только
P2
и P3
только
P1
и P2
P1
, P2
и P3
Сложность вопроса
91
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
спасибо за пятёрку
14 авг 2019
Аноним
Я провалил зачёт, какого чёрта я не нашёл этот чёртов сайт с решениями интуит до того как забрали в армию
08 дек 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # В доказательстве теоремы 10.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g1, f3), требовалась м.Т. M1, которая переводит конфигурацию вида |x* |y в конфигурацию |y * |x* ∧ *|g(x) , используя м.Т. Mg, вычисляющую функцию g(x). Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M1 ? P1 = Коп# ; par# (par* (Чист, Пуст); Зам(*,∧ ) , par* (Пуст ,Чист); Зам(*,∧ ) ); par# (Пуст, Коп* ); par* (Пуст, +1; +1; Зам(|,∧ ); Зам(|,* )); par* (Пуст, Пуст, Mg); Зам( #,* ) P2 = Коп# ; par# (par* (Чист, Пуст); Зам(*,∧ ) , par* (Пуст ,Чист); Зам(*,∧ ) ); par# (Пуст, Коп# ); par# (Пуст, Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* ) P3 = Коп* ; par* (Чист, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par# (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ) В этих определениях участвуют следующие простые машины Тьюринга: Копa – копирует вход после разделительного символа a : w ⇐ w a w;Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );Пуст – не изменяет аргумент: w ⇐ w ;Чист – стирает аргумент: w ⇐ ∧ ;+1 – прибавляет 1 к аргументу: |x ⇐ |x+1
- # Пусть задан недетерминированный конечный автомат (без пустых переходов) M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программой Φ: q 0 → p, q 0 → s, q 1→ q, p 0 → q, p 0 → p, s 1 → q, s 1 → p Какие из следующих трех ДКА эквивалентны M? M1 = < {0, 1}, {q, ps, pq, pqs}, q, F1={ ps, pq, pqs }, Φ1> с программой Φ1: q 0 → ps, q 1 → q, ps 0 → pq, ps 1 → pq, pq 0 → pqs, pq 1 → q, pqs 0 → pqs, pqs 1 → pq M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F2={p, ps, pq, pqs }, Φ2> с программой Φ2: q 0 → ps, q 1 → q, p 0 → pq, p 1 → q, ps 0 → qs, ps 1 → pq, pq 0 → pqs, pq 1 → q, qs 0 → ps, qs 1 →q, pqs 0 → pqs, pqs 1 → pq, ∅ 0 →∅, ∅ 1 →∅ M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F3={ p, ps, pq, pqs }, Φ3> с программой Φ3: q 0 → ps, q 1 → q, p 0 → pq, p 1 → q, s 0 →∅, s 1 →pq, ps 0 → pq, ps 1 → pq, pq 0 → pqs, pq 1 → q, qs 0 → ps, qs 1 →q, pqs 0 → pqs, pqs 1 → pq, ∅ 0 →∅, ∅ 1 →∅
- # Пусть S={aa, ab, ba, bb} Какая из следующих фраз описывает итерацию S* этого языка?
- # Какие из следующих трех автоматов С1 , С2 , С3 распознают язык, представляемый регулярным выражением (00 + 1)*1? С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1> , С2 = < {0,1}, {q, p, r, s }, q, F2={ s}, Φ2> , С3 = < {0,1}, {q, p, r, s, t}, q, F3={ s}, Φ3> , где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
- # Три машины Тьюринга Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы: [Большая Картинка] Какие из этих машин переводят любую начальную конфигурацию вида q an b в заключительную конфигурацию ! b an (n ≥ 0 )?