Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть задан недетерминированный конечный автомат M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={3, 5}, Φ> с программой Φ: 0 b → 1, 0 → 2, 1 → 2, 2 → 3, 2 a → 1, 3 a → 1, 3 b → 4, 4 a → 5, 5 → 3. Какой из следующих НКА получится из M после применен
Пусть задан недетерминированный конечный автомат
M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={3, 5}, Φ> с программой
Φ: 0 b → 1, 0 → 2, 1 → 2, 2 → 3, 2 a → 1, 3 a → 1, 3 b → 4, 4 a → 5, 5 → 3.
Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?
вопрос
Правильный ответ:
M1 = < {a, b}, {0, 1, 4 ,5}, 0, F1={0, 1, 5}, Φ1> с программой
Φ1: 0 a → 1, 0 b → 1, 1 a → 1, 1 b → 4, 4 a → 5, 5 a → 1, 5 b → 4 M2 = < {a, b}, {0, 1, 2, 5 }, 0, F2={1, 5}, Φ2> с программой
Φ2: 0 a → 1, 0 b → 1, 0 b → 4, 1 a → 1, 1 b → 4, 4 a → 5, 5 a → 1, 5 b → 4 M3 = < {a, b}, {0, 1, 4, 5 }, 0, F3={0, 1, 5}, Φ3> с программой
Φ3: 0 a → 1, 0 b → 1, 0 b → 4, 1 a → 1, 1 b → 4, 4 a → 5, 5 a → 1, 5 b → 4 M4 = < {a, b}, {0, 1, 3, 4, 5 }, 0, F4={0, 1, 3, 5}, Φ4> с программой
Φ4: 0 a → 1, 0 b → 1, 0 b → 4, 1 a → 1, 1 b → 4, 3 a → 1, 3 b → 4, 4 a → 5, 5 a → 1, 5 b → 4
ни один из выше приведенных автоматов
M1, M2, M3, M4 Сложность вопроса
70
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Я помощник профессора! Тотчас удалите сайт vtone.ru с ответами интуит. Пишу жалобу
22 авг 2016
Аноним
Экзамен сдан на зачёт. Спасибо vtone
16 апр 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Пусть задана логическая схема S=(V, E) : V= {a (X1), b(X2), c(X3), d(¬),e(¬), f(∨),g(∨),h(∨), i(∧), k(∧) } (после имени вершины в скобках указана ее метка - переменная или булева функция), E= { (a, d), (a, g), (b, e), (b, f), (b, g), (c, f), (d, h), (e, h), (f,k), (g,i), (h, i), (i, k) }. Какую булеву функцию реализует схема S=(V, E) в вершине k? (В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов X1, X2 и X3)
- # На следующем рисунке представлены диаграммы двух конечных автоматов A =< {a,b}, {q,p}, q, {p}, ΦA> и B =< {a,b}, {1, 2, 3}, 1, {1, 2}, ΦB>, [Большая Картинка] распознающих языки LA и LB, соответственно. Какой из следующих автоматов является произведением A × B и какой язык он реализует? C = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2), (p,3)}, (q,0), F={(q, 1), (q, 2)}, ΦC >, D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,3)}, ΦD >, [Большая Картинка]
- # Какой язык L является конкатенацией двух языков: L1= {a, ab, abba} и L2= { ε, a, b, ba}?
- # Заданы два НКА: A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ΦA > с программой ΦA: 0 a → 1, 0 b → 3, 1 a → 2, 1 b → 1, 2 a → 1, 2 b → 3, 3 a → 3, 3b → 3 и B =< {a, b}, {q0, q1, q2}, q0, {q2}, ΦB > с программой ΦB: q0 b → q0, q0 b → q1, q1 a → q1, q1 a → q2, q2 b → q0 Какие из следующих трех НКА С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, q0, q1, q2}, 0, F3={ q2}, Φ3> , где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
- # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые начинаются на cac и содержат подслово bcb Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* → {0, 1}* где h(a) = 0, h(b) = 11, h(c) = ε ?