Puzzle con espressioni regolari

Question

Questo non è compito a casa, ma una vecchia domanda d'esame. Sono curioso di vedere la risposta.

Ci viene dato un alfabeto S = {0,1,2,3,4,5,6,7,8,9, +}. Definire la lingua L come l'insieme di stringhe W da questo alfabeto tale che w è in L se:

a) w è un numero come 42 o w è il finito) somma di numeri come 34 (+ 16 o 34 + 2 + 10

e

b) Il numero rappresentato da w è divisibile per 3.

scrive un'espressione regolare (e DFA) per L.

Answer 1

Questo dovrebbe funzionare:

 
^(?: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*)+))*$ 

Funziona avendo tre stati che rappresentano la somma delle cifre finora modulo 3.Non consente gli zeri iniziali sui numeri e i segni più all'inizio e alla fine della stringa, oltre a due segni più consecutivi.

Generazione di espressioni regolari e test di letto:

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

Non soluzione completa, solo un'idea:

(B) da solo: i segni "più" non contano qui. abc + def è la stessa abcdef per motivi di divisibilità per 3. In quest'ultimo caso, v'è una regexp qui: http://blog.vkistudios.com/index.cfm/2008/12/30/Regular-Expression-to-determine-if-a-base-10-number-is-divisible-by-3

combinare questo con il requisito (A), si può prendere la soluzione di (B) e modificare iT:

• il primo carattere di lettura deve essere in 0..9 (non un plus)

• ingresso non deve terminare con un plus, così: Duplicate ogni stato (utilizzerà S per lo stato originale e S' affinché il duplicato possa distinguerli). Se siamo nello stato S e leggiamo un plus, passeremo a S'.

• Quando si legge un numero, si passa al nuovo stato come se fossimo nello S. Gli stati S' non possono accettare (altro) più.

• Inoltre, S' non è "stato di accettazione" anche se S è. (perché l'input non deve finire con un plus).

Answer 3

Nota che la mia memoria di sintassi DFA è tristemente fuori moda, quindi la mia risposta è senza dubbio un po 'rotto. Spero che questo ti dia un'idea generale. Ho scelto di ignorare completamente +. Come afferma AmirW, abc + def e abcdef sono gli stessi per scopi di divisibilità.

Accetta Stato è C.

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

Si noti che il linguaggio precedente utilizza tutti i 9 possibili accoppiamenti ABC. Si concluderà sempre con A, B o C, e il fatto che ogni variabile utilizzata sia abbinata significa che ogni iterazione di elaborazione accorcerà la stringa di variabili.

Esempio:

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