Регулярные языки и делимость

[Xaositect]

Не знаю, насколько задачу можно назвать олимпиадной, но мне понравилась.

Назовем множество натуральных чисел регулярным, если множество их представлений в двоичной системе счисления регулярно (например, регулярное выражение $10^{*}$ задает множество степеней двойки).
Доказать, что множество чисел, делящихся на некоторое число $k$, регулярно.

[maxal]

Задача скорее учебная чем олимпиадная. Для решения достаточно лишь заметить, что проверку делимости заданного в бинарном виде числа на фиксированное число $k$ можно осуществить на конечном автомате. Например, заведя отдельное состояние для каждого возможного остатка по модулю $k$, и переходя от одного состояния к другому по мере прочтения входного числа, причем единственным допускающим состоянием является остаток равный нулю.

[Профессор Снэйп]

maxal в сообщении #214683 писал(а):

Задача скорее учебная чем олимпиадная. Для решения достаточно лишь заметить, что проверку делимости заданного в бинарном виде числа на фиксированное число $k$ можно осуществить на конечном автомате. Например, заведя отдельное состояние для каждого возможного остатка по модулю $k$, и переходя от одного состояния к другому по мере прочтения входного числа, причем единственным допускающим состоянием является остаток равный нулю.

Согласен. Но надо, наверное, для полноты решения ещё один фактик упомянуть.

Чтобы считать остатки, двоичную запись числа лучше читать с правого конца, задом наперёд. А подразумевается, вероятно, что она будет читаться автоматом слева направо. Ну и тут надо сказать, что язык регулярен тогда и только тогда, когда язык, состоящий из "перевёрнутых" слов, тоже регулярен.

Кстати, я как-то уже публиковал в этом разделе задачку про конечные автоматы.

post91785.html

Она более олимпиадная, чем эта