Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть задан недетерминированный конечный автомат M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={4, 5}, Φ> с программой Φ: 0 b → 1, 0 → 2, 1 a → 2, 1 b → 4, 2 → 3, 2 → 5, 3 a → 4, 3 b → 2, 4 → 5 Какой из следующих НКА получится из M после применени
Пусть задан недетерминированный конечный автомат
M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={4, 5}, Φ>
с программой
Φ: 0 b → 1, 0 → 2, 1 a → 2, 1 b → 4, 2 → 3, 2 → 5, 3 a → 4, 3 b → 2, 4 → 5
Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?
вопрос
Правильный ответ:
M1 = < {a, b}, {0, 1, 2, 4 ,5}, 0, F1={0, 2, 4, 5}, Φ1> с программой Φ1: 0 b → 1, 0 b → 2, 0 a → 4, 0 a → 5, 1 a → 2, 1 a → 5,1 b → 4, 2 a → 4, 2 b → 2
M2 = < {a, b}, {0, 1, 2, 4 }, 0, F2={0, 2, 4}, Φ2> с программой
Φ2: 0 b → 1, 0 b → 2, 0 a → 4, 1 a → 2, 1 b → 4, 2 a → 4, 2 b → 2
M3 = < {a, b}, {0, 1, 2, 3, 4 }, 0, F3={0, 2, 4}, Φ3> с программой
Φ3: 0 b → 1, 0 b → 2, 0 a → 4, 1 a → 2, 1 b → 4, 2 a → 4, 2 b → 2, 3 a → 4, 3 b → 2
M4 = < {a, b}, {0, 1, 2, 4 }, 0, F4={0, 2, 4}, Φ4> с программой
Φ4: 0 b → 1, 0 b → 2, 1 a → 2, 1 b → 4, 2 a → 4, 2 b → 2
ни один из выше приведенных автоматов
M1, M2, M3, M4
Сложность вопроса
83
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Если бы не опубликованные решения - я бы сломался c этими тестами intuit.
03 янв 2020
Аноним
Я помощник профессора! Незамедлительно заблокируйте сайт и ответы с интуит. Не ломайте образование
09 фев 2019
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # В теореме 20.5 была доказана неразрешимость проблемы останова: по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть Mh0= {n | ФПn,y (0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе независимости ее результата от входа: Mconst= {n | существует константа c ∈ N такая, что ФПn,y (x) = c для всех x}. Какие из следующих функций сводят Mh0 к Mconst ? f1(n) = номер программы: ' x:= 0; Пn ; y:= 0'. f2(n) = номер программы: 'Пn ; y:= x'. f3(n) = номер программы: ' x:= 0; Пn ; y:= 0; y:= y+1'.
- # Какие из следующих УБДР являются сокращенными? [Большая Картинка]
- # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые начинаются на aa и содержат подслово bb Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* → {0, 1}* где h(a) = 01, h(b) = 11, h(c) = ε ?
- # Обозначим через minus(x,y) функцию "усеченного" вычитания, равную (x – y) при x ≥ y и 0 – в противном случае. Для какой из следующих функций f(x,y, i) выражение μi [ f(x,y,i)= 0] задает функцию F(x,y) = [ y/x ] (целая часть частного от деления y на x) ?
- # Пусть машина Тьюринга M построена из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Большеij - выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn i-ый аргумент xi больше j-ого аргумента xj , иначе выдает 1, с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом: M = Коп# ; par#( par* (Коп*, Пуст ); Зам(*, |), Пуст ); if Больше21 then par#( Пуст, Сум ) else par#( Пуст, Умн ) endif; Зам(#, *); Выб33. Какие результаты она получит на входных данных вида |x1 * |x2 при x1 = 2, x2 = 7 и при x1 = 3, x2 = 5, соответственно?