Rompecabezas de expresión regular

Question

Esto no es tarea, sino una vieja pregunta del examen. Tengo curiosidad por ver la respuesta.

Nos ha dado un alfabeto S = {0,1,2,3,4,5,6,7,8,9, +}. Definir el lenguaje L como el conjunto de cadenas w de este alfabeto de tal manera que w está en L si:

a) w es un número tal como 42 o W es el finito) suma de números tales como 34 (+ 16 o 34 + 2 + 10

y

b) El número representado por w es divisible por 3.

escribir una expresión regular (y un DFA) para L.

Answer 1

Esto debería funcionar:

 
^(?:0|(?:(?:[369]|[147](?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\ 
+)*[369]0*)*\+?(?:0\+)*[258])*(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]|0*(?: 
\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147])|[ 
258](?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0 
\+)*[147])*(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]|0*(?:\+?(?:0\+)*[369]0*) 
*\+?(?:0\+)*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]))0*)+)(?:\+(?:0|(?:(? 
:[369]|[147](?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\+)*[369]0*) 
*\+?(?:0\+)*[258])*(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]|0*(?:\+?(?:0\+)* 
[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147])|[258](?:0*(? 
:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147])* 
(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]|0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+) 
*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]))0*)+))*$ 

Funciona por tener tres estados que representan la suma de los dígitos hasta ahora modulo 3.No permite tener ceros a la izquierda en los números, y signos más al principio y al final de la cuerda, así como dos signos más consecutivos.

Generación de expresión y la prueba regular de la cama:

a = r'0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*' 
b = r'a[147]' 
c = r'a[258]' 

r1 = '[369]|[147](?:bc)*(?:c|bb)|[258](?:cb)*(?:b|cc)' 
r2 = '(?:0|(?:(?:' + r1 + ')0*)+)' 
r3 = '^' + r2 + r'(?:\+' + r2 + ')*$' 
r = r3.replace('b', b).replace('c', c).replace('a', a) 

print r 

# Test on 10000 examples. 

import random, re 
random.seed(1) 
r = re.compile(r) 
for _ in range(10000): 
    x = ''.join(random.choice('') for j in range(random.randint(1,50))) 
    if re.search(r'(?:\+|^)(?:\+|0[0-9])|\+$', x): 
     valid = False 
    else: 
     valid = eval(x) % 3 == 0 
    result = re.match(r, x) is not None 
    if result != valid: 
     print 'Failed for ' + x 

Answer 2

No es una solución completa, solo una idea:

(B) solo: los signos "más" no importan aquí. abc + def es la misma que abcdef por el bien de divisibilidad por 3. Para el último caso, hay una expresión regular aquí: http://blog.vkistudios.com/index.cfm/2008/12/30/Regular-Expression-to-determine-if-a-base-10-number-is-divisible-by-3

combinar esto con el requisito (A), podemos tomar la solución de (B) y modificar que:

• primer carácter de lectura debe estar en 0..9 (no es un plus)

• de entrada no debe terminar con un punto a favor, por lo que: Duplicar cada estado (S utilizará para el estado original y S' para que el duplicado distinga entre ellos) Si estamos en el estado S y leemos un plus, pasaremos al S'.

• Al leer un número iremos al nuevo estado como si estuviéramos en S. S' estados no pueden aceptar (otro) más.

• Además, S' no es "aceptar estado" incluso si S es. (porque la entrada no debe terminar con un más).

Answer 3

Tenga en cuenta que mi memoria de sintaxis de DFA está tristemente desactualizada, por lo que mi respuesta es indudablemente un poco rota. Espero que esto te dé una idea general. He elegido ignorar por completo el +. Como afirma AmirW, abc + def y abcdef son iguales para propósitos de divisibilidad.

Aceptar estado es C.

A=1,4,7,BB,AC,CA 
B=2,5,8,AA,BC,CB 
C=0,3,6,9,AB,BA,CC 

en cuenta que el lenguaje anterior utiliza todas las 9 posibles emparejamientos ABC. Siempre terminará en A, B o C, y el hecho de que cada uso de variable esté emparejado significa que cada iteración de procesamiento acortará la cadena de variables.

Ejemplo:

1490 = AACC = BCC = BC = B (Fail) 
1491 = AACA = BCA = BA = C (Success)