Geek asks and answers

Regular expression for binary numbers divisible by 3

I myself study regular expressions and found an interesting practical problem online that involves writing a regular expression to recognize all binary numbers divisible by 3 (and only such numbers). Honestly, the problem was to create a DFA for such a scenario, but I decided that this should be equivalently possible using regular expressions.

I know that there is a small rule to find out if a binary number is divisible by 3: take the number of units in even places in a digit and subtract from the number of units in odd places in a digit - if it is zero, the number is divided by 3 (example: 110 - 1 in an even 2 slot and 1 in an odd 1 slot). However, I have some problems adapting this to regex.

The closest I came, realizing that the number could be 0, so this will be the first state. I also saw that all binary numbers divisible by 3 start with 1, so this will be the second state, but I'm stuck from there. Can anyone help?

+5
source share
4 answers

, , DFA b d, DFA .

( 2 - , divisor d= 3 10):

Initial DFA

, DFA "", 3. , :

Fixed DFA

.

, , , DFA. (base b= 10, d= 7 10) CodeGolf.SE.

Lowjacker, Ruby regex:

(?!$)(?>(|(?<B>4\g<A>|5\g<B>|6\g<C>|[07]\g<D>|[18]\g<E>|[29]\g<F>|3\g<G>))(|(?<C>[18]\g<A>|[29]\g<B>|3\g<C>|4\g<D>|5\g<E>|6\g<F>|[07]\g<G>))(|(?<D>5\g<A>|6\g<B>|[07]\g<C>|[18]\g<D>|[29]\g<E>|3\g<F>|4\g<G>))(|(?<E>[29]\g<A>|3\g<B>|4\g<C>|5\g<D>|6\g<E>|[07]\g<F>|[18]\g<G>))(|(?<F>6\g<A>|[07]\g<B>|[18]\g<C>|[29]\g<D>|3\g<E>|4\g<F>|5\g<G>))(|(?<G>3\g<A>|4\g<B>|5\g<C>|6\g<D>|[07]\g<E>|[18]\g<F>|[29]\g<G>)))(?<A>$|[07]\g<A>|[18]\g<B>|[29]\g<C>|3\g<D>|4\g<E>|5\g<F>|6\g<G>)

, , . ( , ) . , (?DEFINE) Perl. A to G 0 6, 7.

(?!$)
(?>
  (|(?<B>4   \g<A>|5   \g<B>|6   \g<C>|[07]\g<D>|[18]\g<E>|[29]\g<F>|3   \g<G>))
  (|(?<C>[18]\g<A>|[29]\g<B>|3   \g<C>|4   \g<D>|5   \g<E>|6   \g<F>|[07]\g<G>))
  (|(?<D>5   \g<A>|6   \g<B>|[07]\g<C>|[18]\g<D>|[29]\g<E>|3   \g<F>|4   \g<G>))
  (|(?<E>[29]\g<A>|3   \g<B>|4   \g<C>|5   \g<D>|6   \g<E>|[07]\g<F>|[18]\g<G>))
  (|(?<F>6   \g<A>|[07]\g<B>|[18]\g<C>|[29]\g<D>|3   \g<E>|4   \g<F>|5   \g<G>))
  (|(?<G>3   \g<A>|4   \g<B>|5   \g<C>|6   \g<D>|[07]\g<E>|[18]\g<F>|[29]\g<G>))
)
(?<A>$|  [07]\g<A>|[18]\g<B>|[29]\g<C>|3   \g<D>|4   \g<E>|5   \g<F>|6   \g<G>)
+8

, , . 3, : 0,1,2. , 3, 3t (t - ).

0 , 0, . . 3t * 2 = 6t, 3.

1 , 0, 1. , 1; 3t * 2 + 1, 1.

1 , 1. , 0; (3t + 1) * 2 + 1 = 6t + 3, 3.

0 , 1. . 2 (3t + 1) * 2 = 6t + 2.

0 , 2. 1. (3t + 2) * 2 = 3t + 4 = 3 (2t + 1) + 1

1 , 2. - 2. (3t + 2) * 2 + 1 = t + 5 = 3 (2t + 1) + 2. , 1 , 2, 2 . (3 (t + 1) + 2) * 2 + 1 = 3 (t + 2) + 5 = 3 (t + 3) + 2

, DFA : DFA describing binary numbers divisible by 3

+2

, , , , () , DFA ( , ).

- , ( MSB LSB) i - , x[i], 0, 1 2 3; S[i]. x[i+1] 0, 1, 2 , , 1.

, S[i] x[i+1], S[i+1]. ?

+1

, 3, 3 :

  • 1 1, 0. "" .

(, 11, 110, 1100, 1001, 10010, 1111)

(: 3, 6, 12, 9, 18, 15)

  1. Numbers with three 1s, each of which is divided by an odd number 0. These triplets also “cancel” themselves.

(e.g. 10101, 101010, 1010001, 1000101)

(decimal: 21, 42, 81, 69)

  1. Some combination of the first two rules (including inside each other)

(e.g. 1010111, 1110101, 1011100110001)

(decimal: 87, 117, 5937)

So a regular expression that takes these three rules into account is simple:

0 * (1 (00) * 10 * | 10 (00) * 1 (00) * (11) * 0 (00) * 10 *) * 0 *

How to read:

() encapsulate

* means previous number / group is optional

| indicates choices on both sides in parentheses

0
source

More articles:


All Articles