expresión regular para definir alguna secuencia binaria

Question

¿Cómo escribir una expresión regular para definir todas las cadenas de 0 y 1. que, como un número binario, representan un entero que es múltiplo de 3.

Algunos números binarios válidos haría se:

 
11 
110 
1001 
1100 
1111 

Answer 1

Usando el DFA here podemos hacer una expresión regular de la siguiente manera, donde A, B, C representan los estados del DFA.

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 

que resulta en un PCRE expresiones regulares como:

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

prueba de Perl/ejemplo:

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"; 
} 

Salidas:

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

No creo que lo haría. No puedo creer que cualquier lenguaje que use una expresión regular pueda ser la mejor manera de hacerlo.

Answer 3

Cuando se divide un número por tres, solo hay tres restos posibles (0, 1 y 2). Lo que pretendes es garantizar que el resto sea 0, por lo tanto, un múltiplo de tres.

Esto se puede hacer por un autómata con los tres estados:

• ST0, múltiplo de 3 (0, 3, 6, 9, ....).
• ST1, múltiplo de 3 más 1 (1, 4, 7, 10, ...).
• ST2, múltiplo de 3 más 2 (2, 5, 8, 11, ...).

Ahora piensa en cualquier número no negativo (que es nuestro dominio) y se multiplica por dos (virar un binario cero hasta el final). Las transiciones para que son:

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). 

también pienso de cualquier número no negativo, se multiplica por dos, entonces añadir una (clavar un uno binario hasta el final). Las transiciones para eso son:

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). 

Esta idea es que, al final, debe terminar en estado ST0. Sin embargo, dado que puede haber un número arbitrario de subexpresiones (y sub-subexpresiones), no se presta fácilmente a la reducción a una expresión regular.

Lo que tienes que hacer es permitir que cualquiera de las secuencias de transición que se pueden obtener de ST0 a st0 a continuación, sólo repetirlas:

Estos se reducen a las dos secuencias RE:

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

o el regex:

(0+|1(01*0)*1)+ 

Esto captura los múltiplos de tres, o al menos los primeros diez que probé.Puedes probar tantas como quieras, todas funcionarán, esa es la belleza del análisis matemático en lugar de la evidencia anecdótica.

Answer 4

La respuesta es (1(01*0)*10*)*, que es el único hasta ahora que trabaja para 110011