Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть задан недетерминированный конечный автомат (без пустых переходов) 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 = < {
Пусть задан недетерминированный конечный автомат
(без пустых переходов)
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 →∅
Правильный ответ:
только
M1
только
M2
только
M3
M1
и M2
M1
и M3
M2
и M3
ни один
Сложность вопроса
90
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Это очень элементарный решебник по интуиту.
23 июл 2018
Аноним
Если бы не данные ответы - я бы не смог решить c этими тестами intuit.
13 июл 2017
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ? (a) является отношением эквивалентности,(b) рефлексивно и транзитивно,(c) сохраняет свойство разрешимости: если A ≤ m B и B - разрешимо, то и A разрешимо.
- # Какие из следующих схем реализуют в вершине a функцию, заданную формулой A = ¬ (a ∧ ¬b) ∨ ((b∨ c) ∧ (a ∧ ¬b)) ? [Большая Картинка]
- # Какие из следующих трех конечных автоматов Ai = < {a,b}, {0, 1, 2, 3, 4}, 0, F={1}, Φi> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые начинаются на b и содержат число букв a , кратное 3 ? [Большая Картинка]
- # Заданы два НКА: A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ΦA > с программой ΦA: 0 a → 1, 0 b → 3, 1 a → 3 1 b → 2, 2 a → 3, 2 b → 2, 3 a → 3, 3b → 3 и B =< {a, b}, {q0, q1, q2}, q0, {q2}, ΦB > с программой ΦB: q0 a → q0, q0 b → q1, q1 a → q1, q1 a → q2 Какие из следующих трех НКА С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, q1, q2}, 0, F3={ q2}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
- # Пусть машина Тьюринга M построена из следующих простых машин Тьюринга: Копa –копирует вход после разделительного символа a : w ⇐ w a w; Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );Сум - складывает два аргумента в унарной системе: |x * |y ⇐ |x+y ;Умн - умножает два аргумента в унарной системе: |x * |y ⇐ |xy ;Пуст - не изменяет аргумент: w ⇐ w с помощью операций последовательного и параллельного применения следующим образом: M = Коп# ; par#( Коп* ; Умн, Пуст ); par#( Коп* ; Сум , Пуст ); Зам(#,?); Сум Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?