Введение в схемы, автоматы и алгоритмы

<<- Назад к вопросам

Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых есть по крайней мере два подряд идущих 0 ?

(Отметьте один правильный вариант ответа.)

Варианты ответа

(1 +01)*00(0 +1)*(Верный ответ)

(1 + 01)*00(01 +1)*

(1 +00)*

(0 + 1)*10*1(0+1)*

1*00(0 + 10)*(0+1)*

Похожие вопросы

Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых есть по крайней мере две подряд идущие 1-цы ?

Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых нет двух подряд идущих 0 ?

Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = (x+1)² ?

Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = x² + x?

Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = 2x² ?

Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?

Пусть функция rm(x, y) = y mod x равна остатку от деления y на x ( rm(0,y)=y )Какое из следующих выражений определяет число dn(x) различных делителей числа x, отличных от 1 и самого x?

Пусть c₂(x, y) = 2^x(2y+1) -1 - это функция нумерации пар, а c₂₁(z) и c₂₂(z) - это соответствующие обратные функции такие, что c₂(c₂₁(z), c₂₂(z)) = z для всех z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функций, значения которых на аргументе (y+1) зависят от их значений в двух предыдущих точках y-1 и y. Рассмотрим функцию F(x), заданную равенствами:F(0) = 1, F(1) = 2, F(y+2) = F(y) × F(y+1). Положим G(y) = c₂(F(y), F(y+1)). Так какF(y) = c₂₁(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность G. Определите, какая из следующих примитивных рекурсий задает G.