Проверить деление на 3 в двоичной форме программно (grep)

[akh]

Здраствуйте !

Помогите пожалуйста решить вот такую задачку. Надо проверить делимость на три числа в двоичной форме. Сделать это надо с помощью регулярных выражений. Ну скажем с помощью grep ?
Признаки делимости на три я вроде знаю, но вот как применить ? Или такие числа обладают некой регулярностью в записи ? Если обладают то где почитать ?

[tolstopuz]

Нужен признак делимости на $3$ для двоичной системы. Их есть два (хотя по сути они одинаковы):

1. Делимость на $2 + 1 = 3$ в двоичной системе - аналог делимости на $10 + 1 = 11$ в десятичной системе, знакопеременная сумма цифр должна делиться на $3$. Например, $75 = 1001011_{2}, 1-0+0-1+0-1+1 = 0$.
2. Делимость на $4 - 1 = 3$ в четверичной системе - аналог делимости на $10 - 1 = 9$ в десятичной системе, сумма двузначных групп двоичного числа должна делиться на $3$. Например, $75 = 1001011_{2}, 1_2+00_2+10_2+11_2 = 6$.

С точки зрения программы, работающей со строкой символов, можно попробовать переформулировать так: поделить строку на группы по две цифры справа налево (дополнить слева нулем, если число цифр нечетно), посчитать число групп "01" и вычесть из него число групп "10". Результат должен делиться на 3. Как реализовать это в регэкспах - не знаю.

[незваный гость]

Не знаю, но я бы пошел другим путем:

1) сделайте конечны автомат, проверяющий делимость числа (как цепочки) на три. В нем три вершины: $S_0$, $S_1$ и $S_2$, соответствующие текущему остатку. Переходы соответствуют приписыванию соответствующей младшей цифры.

2) Переведите его в регулярное выражение (есть конструктивные теоремы об эквивалентности).

[tolstopuz]

незваный гость писал(а):

1) сделайте конечны автомат, проверяющий делимость числа (как цепочки) на три.

Ой, а ведь и правда очень просто.

[akh]

Идея с конечным автоматом понравилась Ей наверное и воспользуюсь. А что это за теоремы об эквивалентности ? Ну то есть конечно интутивно (и по реализации) regexp можно перевести в конечный автомат и наверное наоборот. Но чтобы теорема.