Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть задан недетерминированный конечный автомат (без пустых переходов) M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программой Φ: q 0 → q, q 1 → s, q 1→ p, p 0 → q, p 0 → p, s 0 → q, s 1 → p Какие из следующих трех ДКА эквивалентны M? M1 = < {
Пусть задан недетерминированный конечный автомат
(без пустых переходов)
M = < {0, 1}, {q, p, s}, q, F={p}, Φ>
с программой
Φ: q 0 → q, q 1 → s, q 1→ p, p 0 → q, p 0 → p, s 0 → q, s 1 → p
Какие из следующих трех ДКА эквивалентны M
?
M1 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F1={p, ps, pq, pqs }, Φ1>
с программой Φ1:
q 0 → q, q 1 → ps, p 0 → pq, p 1 → ∅, s 0 → q, s 1 → pq, ps 0 → pq, ps 1 → p, pq 0 → pq, pq 1 → p, qs 0 → q, qs 1 →pq, pqs 0 → pq, pqs 1 → ps, ∅ 0 →∅, ∅ 1 →∅
M2 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F2={ p, ps, pq, pqs }, Φ2>
с программой Φ2:
q 0 → q, q 1 → ps, p 0 → pq, p 1 → q, s 0 → q, s 1 → pq, ps 0 → pq, ps 1 → p, pq 0 → pq, pq 1 → ps, qs 0 → q, qs 1 →pq, pqs 0 → pq, pqs 1 → ps, ∅ 0 →∅, ∅ 1 →∅
M3 = < {0, 1}, {q, p, ps, pq, ∅ }, q, F3={ ps, pq, p }, Φ3>
с программой Φ3:
q 0 → q, q 1 → ps, ps 0 → pq, ps 1 → p, pq 0 → pq, pq 1 → ps, p 0 → pq, p 1 → ∅, ∅ 0 →∅, ∅ 1 →∅
Правильный ответ:
только
M1
только
M2
только
M3
M1
и M2
M1
и M3
M2
и M3
ни один
Сложность вопроса
82
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Нереально сложно
19 апр 2020
Аноним
Я сотрудник университета! Немедленно заблокируйте сайт vtone.ru с ответами по интуит. Умоляю
07 июн 2017
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении. Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка. (a) x := x+1, (b) x := 0, (c) x := y.
- # Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>, где [Большая Картинка] Какие из следующих трех слов распознаются автоматом A? W= aaabaabab, V= abababaab, U= bbabbbababa
- # Пусть структурированная программа P: x:= y+1; v:= u+1; y := z+1; пока x < v делай если x < y то x := y+1 иначе y := x +1 конец все начинает работу в состоянии σ : σ(x) =0, σ(y) =2, σ(z) =2, σ(u) = 5, σ(v) =0В каком из следующих состояний σ1 она завершит свою работу?
- # В конструкции для параллельной композиции машин Тьюринга на этапах 3 и 5 участвует служебная машина, назовем ее CHANGE, меняющая местами аргументы, точнее переводящая любую конфигурацию вида x * q y (x и y – слова в алфавите Σ, не содержащем символов ∧, * и # , q – начальное состояние) в конфигурацию y* q’ x (q' – заключительное состояние). Пусть Q={ q, s, p, r, q'}∪ {pa | a ∈ Σ} – множество состояний CHANGE. Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для CHANGE ? (В текстах программ a – это произвольный символ из Σ, а b - это произвольный символ из Σ ∪ {*, #} ). P1: q b → q b П , q ∧ → s # Л, s b → s b Л, s ∧ → p ∧ П, p a → pa ∧П, p * → r ∧П, pa b → pa b П, pa ∧ → s a Л, r a → r a П , r # → q’ * П. P2: q a → q a П , q ∧ → s * Л, s b → s b Л, s ∧ → p ∧ П, p a → pa ∧П, p * → r ∧П, pa b → pa b П, pa ∧ → s a Л, r a → r a П , r*→ q’ * П. P3: q a → q a П , q ∧ → s * Л, s b → s b Л, s ∧ → p ∧ П, p a → pa ∧П, p * → q’ * П, pa b → pa b П, pa ∧ → s a Л.
- # Приведенные ниже машины Тьюринга Mi (i= 1,2,3,4) M1 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; Зам(#, |); Выч1) enddo; Выб22 M2 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; par# (Пуст, Коп#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб22 M3 = if Нуль11 then Пуст else Коп* Зам(∧, *); Зам(∧,|); while Нуль13 do par*( Выч1, Коп#, Пуст); par# (Пуст, Умн); Зам(#, *)) enddo; Выб33 endif. M4 = if Нуль11 then Пуст else Коп* Зам(∧, *); while Нуль13 do par*( Выч1, Коп#, Пуст); par# (Пуст, Сум); Зам(#, *)) enddo; Выб33 endif. построены из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Нульin - выдает 1, если i-ый аргумент из n аргументов равен ∧ (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |i , i >0),Выч1 – вычитает единицу в унарной системе: |j ⇐ |j-1 (| ⇐ ∧) Какая из этих машин вычисляет функцию f(x) = 2x в унарном кодировании, т.е. переводит вход |x в выход |y, где y = 2x?