Hola usuario de nuestro sitio web, hemos encontrado la solución a tu búsqueda, continúa leyendo y la encontrarás un poco más abajo.
Solución:
Siguiendo lo que dice Oli Charlesworth, puede crear DFA para la divisibilidad de base b número por cierto divisor d, donde los estados en el DFA representan el resto de la división.
Para su caso (base 2 – número binario, divisor d = 310):
Tenga en cuenta que el DFA anterior acepta vacíos string como un “número” divisible por 3. Esto se puede solucionar fácilmente agregando un estado intermedio más al frente:
La conversión a una expresión regular teórica se puede realizar con el proceso normal.
La conversión a expresiones regulares prácticas en sabores que admiten expresiones regulares recursivas se puede hacer fácilmente, cuando tenga el DFA. Esto se muestra para el caso de (base b = 10, d = 710) en esta pregunta de CodeGolf.SE.
Permítanme citar la expresión regular en la respuesta de Lowjacker, escrita en sabor a expresiones regulares Ruby:
(?!$)(?>(|(?4g|5g|6g|[07]g|[18]g|[29]g|3g))(|(?[18]g|[29]g|3g|4g|5g|6g|[07]g))(|(?5g|6g|[07]g|[18]g|[29]g|3g|4g))(|(?[29]g|3g|4g|5g|6g|[07]g|[18]g))(|(?6g|[07]g|[18]g|[29]g|3g|4g|5g))(|(?3g|4g|5g|6g|[07]g|[18]g|[29]g)))(?$|[07]g|[18]g|[29]g|3g|4g|5g|6g)
Al desglosarlo, puedes ver cómo está construido. los atómico agrupación (o no retroceder grupo, o un grupo que se comporta posesivamente) se utiliza para asegurarse de que solo el vacío string se empareja la alternativa. Este es un truco para emular (?DEFINE) en Perl. Entonces los grupos A para G corresponden al resto de 0 a 6 cuando el número se divide por 7.
(?!$)
(?>
(|(?4 g|5 g|6 g|[07]g|[18]g|[29]g|3 g))
(|(?[18]g|[29]g|3 g|4 g|5 g|6 g|[07]g))
(|(?5 g|6 g|[07]g|[18]g|[29]g|3 g|4 g))
(|(?[29]g|3 g|4 g|5 g|6 g|[07]g|[18]g))
(|(?6 g|[07]g|[18]g|[29]g|3 g|4 g|5 g))
(|(?3 g|4 g|5 g|6 g|[07]g|[18]g|[29]g))
)
(?$| [07]g|[18]g|[29]g|3 g|4 g|5 g|6 g)
Tengo otra forma de resolver este problema y creo que es más fácil de entender. Cuando dividimos un número por 3, podemos tener tres residuos: 0, 1, 2. Podemos describir un número que es divisible por 3 usando la expresión 3t (t es un número natural).
Cuando sumamos 0 después de un número binario cuyo resto es 0, el número decimal real se duplicará. Porque cada dígito se mueve a una posición más alta.
3t * 2 = 6t, esto también es divisible por 3.
Cuando agregamos un 1 después de un número binario cuyo resto es 0, el número decimal real se duplicará más 1. Porque cada dígito se mueve a una posición más alta seguida de un 1;
3t * 2 + 1 = 6t + 1, el resto es 1.
Cuando agregamos un 1 después de un número binario cuyo resto es 1. El número decimal real se duplicará más uno, y el resto es 0;
(3t + 1)*2 + 1 = 6t + 3 = 3(2t + 1), esto es divisible por 3.
Cuando agregamos un 0 después de un número binario cuyo resto es 1. El número decimal real se duplicará. Y el resto serán 2.
(3t + 1)*2 = 6t + 2.
Cuando sumamos un 0 después de un número binario cuyo resto es 2. El resto será 1.
(3t + 2)*2 = 6t + 4 = 3(2t + 1) + 1
Cuando sumamos un 1 después de un número binario cuyo resto es 2. Entonces el resto seguirá siendo 2.
(3t + 2)*2 + 1 = 6t + 5 = 3(2t + 1) + 2.
No importa cuántos 1 agregue a un número binario cuyo resto es 2, el resto será 2 para siempre.(3(2t + 1) + 2)*2 + 1 = 3(4t + 2) + 5 = 3(4t + 3) + 2
Entonces podemos tener el DFA para describir el número binario:
Nota: Borde q2 -> q1 debe estar etiquetado como 0.
Los números binarios divisibles por 3 se dividen en 3 categorías:
- Números con dos unos consecutivos o dos unos separados por un número par de ceros. Efectivamente, cada par se “cancela” a sí mismo.
(ej. 11, 110, 1100,1001,10010, 1111)
(decimal: 3, 6, 12, 9, 18, 15)
- Números con tres unos separados cada uno por un número impar de ceros. Estos trillizos también se “cancelan” a sí mismos.
(ej. 10101, 101010, 1010001, 1000101)
(decimal: 21, 42, 81, 69)
- Alguna combinación de las dos primeras reglas (incluso una dentro de la otra)
(ej. 1010111, 1110101, 1011100110001)
(decimal: 87, 117, 5937)
Entonces, una expresión regular que tiene en cuenta estas tres reglas es simplemente:
0 * (1 (00) * 10 * | 10 (00) * 1 (00) * (11) * 0 (00) * 10 *) * 0 *
Cómo leerlo:
() encapsular
* significa que el número / grupo anterior es opcional
| indica una selección de opciones en cualquier lado entre paréntesis
valoraciones y comentarios
Tienes la posibilidad compartir este enunciado si lograste el éxito.