Главная /
Введение в схемы, автоматы и алгоритмы /
Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых есть по крайней мере два подряд идущих 0 ?
Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых есть по крайней мере два подряд идущих 0 ?
вопросПравильный ответ:
(1 + 01)*00(01 +1)*
(1 +00)*
(0 + 1)*10*1(0+1)*
1*00(0 + 10)*(0+1)*
(1 +01)*00(0 +1)*
Сложность вопроса
95
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Зачёт сдан. Лечу выпивать отмечать зачёт по тестам
17 авг 2019
Аноним
Спасибо за ответы по intuit.
25 ноя 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>, [Большая Картинка] Какой из следующих языков распознает автомат A ?
- # Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>, [Большая Картинка] Какой из следующих языков распознает автомат A ?
- # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв a превосходит количество букв b не менее чем на 2. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?
- # Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = (x+1)2 ?
- # В конструкции машины Тьюринга со стандартными заключительными конфигурациями нужна служебная машина Тьюринга, назовем ее MOVE, которая сдвигает полученный результат в начальную позицию, отмеченную символом со штрихом. Точнее, MOVE, начав работать в конфигурации вида q a w1 #k#' (a ∈Σ, w1 ∈Σ*, k ≥ 0), должна завершить работу в конфигурации ∧kpa'w1 Пусть алфавит ленты MOVE включает символы из Σ ∪ {a' | a ∈ Σ}∪ {∧, #, #'}, а алфавит состояний Q= {q, p, r} ∪ {pa | a ∈ Σ} Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для MOVE ? (В текстах программ a и b – это произвольные символы из Σ), P1: q a → pa ∧ П , q a' → p a' Н , pa b → pb a П, pa b' → pb a' П, pa # → r a Л, pa #' → r a' Л, pa ∧ → r a Л, r a → r a Л , r a' → r a' Л , r ∧ → q ∧ П. P2: q a → pa ∧ П , pa b → pb a П, pa b' → pb a' П, pa # → r a Л, pa #' → r a' Л, pa ∧ → r a Л, r a → r a Л , r a' → r a' Л , r ∧ → q ∧ П. P3: q a → pa ∧ П , pa b → pa b П, pa # → pa # П, pa #' → r a Л, pa b' → pa b' П, pa ∧ → r a Л, r a → r a Л , r a' → r a' Л , r ∧ → q ∧ П, q # → q ∧ П , q a' → p a' Н.