Regulärer Ausdruck einige binäre Sequenz

Question

zu definieren Wie würden Sie einen regulären Ausdruck schreiben alle Strings von 0 und 1 ist, dass, als binäre Zahl zu definieren, eine ganze Zahl darstellen, die 3. Vielfaches von

einige gültige Binärzahlen ist würde be:

 
11 
110 
1001 
1100 
1111 

Answer 1

Mit dem DFA here können wir einen regulären Ausdruck auf die folgende Weise machen, wobei A, B, C die Zustände des DFA darstellen.

A = 1B + 0A 
B = 1A + 0C 
C = 1C + 0B 

C = 1*0B // Eliminate recursion 

B = 1A + 0(1*0B) 
B = 01*0B + 1A 
B = (01*0)*1A // Eliminate recursion 

A = 1(01*0)*1A + 0A 
A = (1(01*0)*1 + 0)A 
A = (1(01*0)*1 + 0)* // Eliminate recursion 

in einer PCRE Resultierende regex wie:

/^(1(01*0)*1|0)+$/ 

Perl-Test/Beispiel:

use strict; 

for(qw(
11 
110 
1001 
1100 
1111 
0 
1 
10 
111 
)){ 
    print "$_ (", eval "0b$_", ") "; 
    print /^(1(01*0)*1|0)+$/? "matched": "didnt match"; 
    print "\n"; 
} 

Ausgänge:

11 (3) matched 
110 (6) matched 
1001 (9) matched 
1100 (12) matched 
1111 (15) matched 
0 (0) matched 
1 (1) didnt match 
10 (2) didnt match 
111 (7) didnt match 

Answer 2

Ich glaube nicht, dass Sie würden. Ich kann nicht an irgendeine Sprache glauben, mit einem regulären Ausdruck könnte jemals der beste Weg sein, dies zu tun.

Answer 3

Wenn Sie eine Zahl von drei teilen, Es gibt nur drei mögliche Reste (0, 1 und 2). Was Sie anstreben, ist sicherzustellen, dass der Rest 0 ist, also ein Vielfaches von Drei.

Dies kann durch einen Automaten mit drei Zuständen durchgeführt werden:

• ST0, mehr von 3 (0, 3, 6, 9, ....).
• ST1, mehrere von 3 plus 1 (1, 4, 7, 10, ...).
• ST2, mehrere von 3 plus 2 (2, 5, 8, 11, ...).

denken jetzt von jede nicht-negativen Zahl (das ist unsere Domäne) und multipliziert es mit zwei (bis zum Ende einer binäre Null tack). Die Übergänge für die sind:

ST0 -> ST0 (3n * 2 = 3 * 2n, still a multiple of three). 
ST1 -> ST2 ((3n+1) * 2 = 3*2n + 2, a multiple of three, plus 2). 
ST2 -> ST1 ((3n+2) * 2 = 3*2n + 4 = 3*(2n+1) + 1, a multiple of three, plus 1). 

denken auch an beliebigen nicht negative Zahl, multipliziert es mit zwei dann fügen eine (auf das Ende, das eine binäre Eins Tack). Die Übergänge dafür sind:

ST0 -> ST1 (3n * 2 + 1 = 3*2n + 1, a multiple of three, plus 1). 
ST1 -> ST0 ((3n+1) * 2 + 1 = 3*2n + 2 + 1 = 3*(2n+1), a multiple of three). 
ST2 -> ST2 ((3n+2) * 2 + 1 = 3*2n + 4 + 1 = 3*(2n+1) + 2, a multiple of three, plus 2). 

Diese Idee ist, dass Sie am Ende in Staat ST0 beenden müssen. Da jedoch eine beliebige Anzahl von Unterausdrücken (und Unterunterausdrücken) vorhanden sein kann, eignet sie sich nicht leicht für die Reduktion auf einen regulären Ausdruck.

Was Sie tun müssen, ist für jede der Übergangssequenzen zu erlauben, die von ST0 bekommen können dann ST0 sie nur wiederholen:

Diese laufen auf den beiden RE Sequenzen:

ST0 --> ST0          : 0+ 
    [0] 
ST0 --> ST1 (--> ST2 (--> ST2)* --> ST1)* --> ST0: 1(01*0)*1 
    [1]  ([0]  ([1] )* [0] )* [1] 

oder die Regex:

Dies erfasst die Vielfachen von drei, oder zumindest die ersten zehn, die ich getestet habe.Du kannst so viele ausprobieren, wie du willst, sie werden alle funktionieren, das ist die Schönheit der mathematischen Analyse und nicht der anekdotische Beweis.

Answer 4

Die Antwort ist (1(01*0)*10*)*, die die einzige ist, so weit, die für 110011