Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть регулярное выражение b*(a+b)* определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:
Пусть регулярное выражение b*(a+b)*
определяет некоторый язык над алфавитом S={a, b}
. Другим регулярным выражением для этого языка может быть:
вопрос
Правильный ответ:
(b*+a)*
(a +b)*
b*ab*
подходит и 1, и 2
для этого языка существует только одно регулярное выражение
Сложность вопроса
88
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Кто ищет данные ответы по интуит? Это же элементарно (я не ботан)
09 сен 2018
Аноним
Если бы не данные ответы - я бы сломался c этими тестами intuit.
05 май 2017
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Пусть задана УБДР D=(V,E): V={v1(x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), , 0, 1} (в скобках после имени вершины указана переменная, которой она помечена), E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 0), (v2, v5; 1), (v3, v5; 1), (v3, v6; 0), (v4, v7; 0), (v4, v8; 1), (v5, v7; 0), (v5, v8; 1), (v6, v8; 1), (v6, v7; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 0), (v8, 1; 1)} ( для каждого ребра третий параметр после ; - его метка 0 или 1). Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.
- # Пусть задан конечный автомат - преобразователь A = <ΣX ={0, 1} ΣY= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>, где [Большая Картинка] Какое входное слово автомат А перерабатывает в выходное слово ТАРАРА?
- # Пусть задан недетерминированный конечный автомат 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 после применения процедуры устранения пустых переходов?
- # Пусть задан ДКА A =< {a, b, c}, {0, 1, 2}, 0, F= {2}, ΦA > с программой ΦA: { 0 a → 1, 0 b → 0, 0 c → 1, 1 a → 2, 1 b → 1, 1 c → 1, 2 a → 2, 2 b → 2, 2 c → 1} и гомоморфизм h: {a, b, c}* → {0, 1}*: h(a) = 01, h(b) = 1, 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>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
- # Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами? P1: x := y+1; z:= x + 1; если x +1 < z то y := z иначе y:=x конецP2: x := y+1; z:= x +1; если x = z то y := z иначе y:=x конецP3: x := y+1; u:= z +1; пока u = z +1 делай y := z; u := u+1 все