2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



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


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

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

 Профиль  
                  
 
 Re: Регулярные языки и делимость
Сообщение17.05.2009, 16:05 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Регулярные языки и делимость
Сообщение21.05.2009, 10:08 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
maxal в сообщении #214683 писал(а):
Задача скорее учебная чем олимпиадная. Для решения достаточно лишь заметить, что проверку делимости заданного в бинарном виде числа на фиксированное число $k$ можно осуществить на конечном автомате. Например, заведя отдельное состояние для каждого возможного остатка по модулю $k$, и переходя от одного состояния к другому по мере прочтения входного числа, причем единственным допускающим состоянием является остаток равный нулю.


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

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

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

post91785.html

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group