Главная /
Введение в схемы, автоматы и алгоритмы /
Какие из следующих схем реализуют в вершине a функцию, заданную формулой A = ((a ∧ ¬b) ∨ ¬b) ∨ ¬ (b∨ c) ? [картинка]
Какие из следующих схем реализуют в вершине a
функцию, заданную формулой
A = ((a ∧ ¬b) ∨ ¬b) ∨ ¬ (b∨ c)
?
вопрос
Правильный ответ:
только
S1
только
S2
только
S3
S1
и S3
S2
и S3
S1
и S2
ни одна
Сложность вопроса
68
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Это очень легкий решебник intuit.
12 апр 2019
Аноним
Кто ищет вот эти ответы inuit? Это же не сложно
22 авг 2018
Аноним
Это очень не сложный решебник intuit.
09 мар 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Пусть задана логическая схема S=(V, E) : V= {a (X), b(Y), c(Z), d(V), e(∧), f(∧),g(¬),h(¬), i(∧), k(∧), m(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция), E= { (a, h), (b, f), (c, e), (c, g), (d, f), (e, i), (f ,i), (f ,k), (g,, k), (h,e),(i, m), (k, m) }. Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m? P1: P2: P3: X = ¬X; h = ¬X; X = ¬X; Z = ¬Z; g = ¬Z; X = X ∧ Z; X = X ∧ Z; e = h ∧ Z; Z = ¬Z; Y = Y ∧ V; f = Y ∧ V; V = Y ∧ V; Y = Y ∧ X; k = f ∧ g; V = X ∧ V; Z = Y ∧ Z; i = e ∧ f; Y = V ∧ Z; Z = Y ∨ Z. Z = i ∨ k. Z = Y ∨ V.
- # Пусть задан недетерминированный конечный автомат (без пустых переходов) 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 →∅
- # Пусть задан ДКА A =< {a, b, c}, {0, 1, 2, 3}, 0, F= {2}, ΦA > с программой ΦA: { 0 a → 1, 0 b → 1, 0 c → 0, 1 a → 1, 1 b → 2, 1 c → 2, 2 a → 3, 2 b → 3, 2 c → 2, 3 a → 3, 3 b → 3, 3 c → 3} и гомоморфизм h: {a, b, c}* → {0, 1}*: h(a) = 01, h(b) = 11, h(c) = ε Какие из следующих трех автоматов С1 , С2, С3 распознают гомоморфный образ h(LA)? С1 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2, q3, q4, q5, q6, q7}, 0, F1={1,2}, Φ1>, С2 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2 }, 0, F2={ 1,2}, Φ2>, С3 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2 }, 0, F3={0,1,2}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
- # Пусть задан ДКА A =< {a, b, c}, {0, 1, 2}, 0, F= {2}, ΦA > с программой ΦA: { 0 a → 0, 0 b → 1, 0 c → 1, 1 a → 1, 1 b → 2, 1 c → 1, 2 a → 2, 2 b → 2, 2 c → 1} и гомоморфизм h: {a, b, c}* → {0, 1}*: h(a) = 1, h(b) = 01, h(c) = ε. Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный образ h(LA)? С1 = < {0, 1}, {0, 1, 2, q1, q2, q3}, 0, F1={2}, Φ1>, С2 = < {0, 1}, {0, 1, 2, q1, q2 }, 0, F2={2}, Φ2>, С3 = < {0, 1}, {0, 2, (q1, q2), (0,1), (1, 2), !}, 0, F3={2, (1,2)}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
- # Три машины Тьюринга Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы: [Большая Картинка] Какие из этих машин переводят любую начальную конфигурацию вида q an b в заключительную конфигурацию ! b a2n (n ≥ 0 )?