2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Регулярные языки и делимость
Сообщение17.05.2009, 13:43 
Аватара пользователя
Не знаю, насколько задачу можно назвать олимпиадной, но мне понравилась.

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

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

 
 
 
 Re: Регулярные языки и делимость
Сообщение21.05.2009, 10:08 
Аватара пользователя
maxal в сообщении #214683 писал(а):
Задача скорее учебная чем олимпиадная. Для решения достаточно лишь заметить, что проверку делимости заданного в бинарном виде числа на фиксированное число $k$ можно осуществить на конечном автомате. Например, заведя отдельное состояние для каждого возможного остатка по модулю $k$, и переходя от одного состояния к другому по мере прочтения входного числа, причем единственным допускающим состоянием является остаток равный нулю.


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

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

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

post91785.html

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

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group