Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть задан недетерминированный конечный автомат M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={4, 5}, Φ> с программой Φ: 0 b → 1, 1 a → 2, 1 b → 3, 2 a → 3, 2 b → 1, 3 → 4, 4 a → 5, 4 → 5, 5 → 2 Какой из следующих НКА получится из M после примене
Пусть задан недетерминированный конечный автомат
M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={4, 5}, Φ> с программой
Φ: 0 b → 1, 1 a → 2, 1 b → 3, 2 a → 3, 2 b → 1, 3 → 4, 4 a → 5, 4 → 5, 5 → 2
Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?
вопрос
Правильный ответ:
M1 = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F1={3, 4, 5}, Φ1> с программой
Φ1: 0 b → 1, 1 a → 2, 1 b → 3, 1 b → 4, 2 a → 3, 2 b → 1, 3 a → 5, 3 a → 3, 3 b → 1,
4 a → 5, 5 a → 3, 5 b → 1 M2 = < {a, b}, {0, 1, 3, 5 }, 0, F2={3, 5}, Φ2> с программой
Φ2: 0 b → 1, 1 a → 2, 1 b → 3, 2 a → 3, 2 b → 1, 3 a → 5, 3 a → 3, 5 a → 3 M3 = < {a, b}, {0, 1, 2, 3, 5 }, 0, F3={5}, Φ3> с программой
Φ3: 0 b → 1, 1 a → 2, 1 b → 3, 2 a → 3, 2 b → 1, 3 a → 5, 3 b → 1, 5 a → 3, 5 b → 1 M4 = < {a, b}, {0, 1, 2, 3, 5}, 0, F4={3, 5}, Φ4> с программой
Φ4: 0 b → 1, 1 a → 2, 1 b → 3, 2 a → 3, 2 b → 1, 3 a → 5, 3 a → 3, 3 b → 1, 5 a → 3,
5 b → 1
ни один из выше приведенных автоматов
M1, M2, M3, M4 Сложность вопроса
49
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Зачёт прошёл. Мчусь выпивать отмечать отлично в зачётке по интуит
12 апр 2017
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Какие из следующих УБДР являются сокращенными? [Большая Картинка]
- # Пусть задан конечный автомат - преобразователь A = <ΣX ={0, 1} ΣY= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>, где [Большая Картинка] Какое входное слово автомат А перерабатывает в выходное слово ТАРТАР?
- # Пусть задан ДКА 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>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
- # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв a превосходит количество букв b не менее чем на 2. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?
- # Пусть структурированная программа P: x:= y+1; v:= u+1; пока x < v делай если y < x то y := y+1; u := u+1 иначе x := x +1 конец все начинает работу в состоянии σ : σ(x) =0, σ(y) =2, σ(u) = 5, σ(v) =0В каком из следующих состояний σ1 она завершит свою работу?