Построить DFA

[arhimedius]

Здравствуйте!
Заранее извиняюсь за перевод, задача такая:

Цитата:

Построить 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$

и так далее.

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

[Sphinx Pinastri]

Для начала представьте, что нужно решить ту же задачу, но входные цепочки -- десятичные числа.
Эту задачу, надеюсь, вы решить можете.
Осталось понять, что изменится у двоичных чисел.

[arhimedius]

Sphinx Pinastri в сообщении #951871 писал(а):

Для начала представьте, что нужно решить ту же задачу, но входные цепочки -- десятичные числа.
Эту задачу, надеюсь, вы решить можете.
Осталось понять, что изменится у двоичных чисел.

С десятичной справился, вроде.
Принцип такой:
При каждом добавлении нового числа, обеспечиваем, чтобы сумма цифр в числе была кратной 3.

Только, вот, принимает и такие числа:
000003, 0006 и т.д.
Но думаю, что это не страшно.

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

[Sonic86]

arhimedius в сообщении #951990 писал(а):

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

Сформулируйте признак делимости на $3$ в $10$-чной системе счисления. Как Вы используете его при написании ДКА.
Сформулируйте признак делимости на $3$ в $2$-чной системе счисления? Чем он сложнее? Как надо модифицировать ДКА, чтобы он мог работать в данном случае?