Question

№ 1. Какие из следующих языков над алфавитом {0, 1} являются регулярными? (несколько вариантов ответа)

1 строки из числа нулей

2 строки из составного числа нулей

3 строки, в которых число единиц сравнимо с числом нулей по модулю n для фиксированного n

4 строки, в которых сумма числа нулей и удвоенного числа единиц делится на n для фиксированного n

5 строки, в любом префиксе которых нулей строго больше, чем единиц

6 строки, начинающиеся на 010 и не являющиеся палиндромами

№ 2.

A — подмножество натуральных чисел.

U = {0^n | n ∈ A}

B = {bin(n) | n ∈ A}, где bin(n) — двоичное представление числа n.

Какие из следующих утверждений верны?

1 Если U — регулярный язык, то и B — регулярный язык.

2 Если B — регулярный язык, то и U — регулярный язык.