2014 dxdy logo

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

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




 
 Построить DFA
Сообщение25.12.2014, 01:31 
Здравствуйте!
Заранее извиняюсь за перевод, задача такая:
Цитата:
Построить DFA распознающий язык, в котором слова - натуральные числа в двоичном виде написанные наоборот, которые делятся на 3.

Тоесть:
$L=\{0,11,011,1001,0011,1111,01001,10101,00011,11011,01111,100001,001001,111001,...\}$
Здесь:
$0 \Rightarrow 0 \Rightarrow 0$

$11 \Rightarrow 11 \Rightarrow 3$

$011 \Rightarrow 110 \Rightarrow 6$

$1001 \Rightarrow 1001 \Rightarrow 9$

$0011 \Rightarrow 1100 \Rightarrow 12$

$1111 \Rightarrow 1111 \Rightarrow 15$

$01001 \Rightarrow 10010 \Rightarrow 18$

$10101 \Rightarrow 10101 \Rightarrow 21$

и так далее.

У меня вообще нет идей. А у вас?

 
 
 
 Re: Построить DFA
Сообщение25.12.2014, 02:05 
Аватара пользователя
Для начала представьте, что нужно решить ту же задачу, но входные цепочки -- десятичные числа.
Эту задачу, надеюсь, вы решить можете.
Осталось понять, что изменится у двоичных чисел.

 
 
 
 Re: Построить DFA
Сообщение25.12.2014, 12:24 
Sphinx Pinastri в сообщении #951871 писал(а):
Для начала представьте, что нужно решить ту же задачу, но входные цепочки -- десятичные числа.
Эту задачу, надеюсь, вы решить можете.
Осталось понять, что изменится у двоичных чисел.

С десятичной справился, вроде.
Принцип такой:
При каждом добавлении нового числа, обеспечиваем, чтобы сумма цифр в числе была кратной 3.
Изображение
Только, вот, принимает и такие числа:
000003, 0006 и т.д.
Но думаю, что это не страшно.

Извиняюсь за свою несообразительность, но никак не могу уловить связь в двоичном написанным наоборот.

 
 
 
 Re: Построить DFA
Сообщение25.12.2014, 13:45 
arhimedius в сообщении #951990 писал(а):
Извиняюсь за свою несообразительность, но никак не могу уловить связь в двоичном написанным наоборот.
Сформулируйте признак делимости на $3$ в $10$-чной системе счисления. Как Вы используете его при написании ДКА.
Сформулируйте признак делимости на $3$ в $2$-чной системе счисления? Чем он сложнее? Как надо модифицировать ДКА, чтобы он мог работать в данном случае?

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


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