Come si scrive un'espressione regolare per definire tutte le stringhe di 0 e di 1, che, come numero binario, rappresentano un numero intero che è multiplo di 3.espressioni regolari per definire una certa sequenza binaria
Alcuni numeri binari validi farebbe be:
11 110 1001 1100 1111
Utilizzando DFA here possiamo fare un'espressione regolare nel modo seguente, dove A, B, C rappresentano gli stati di 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
Con conseguente un PCRE RegEx come:
/^(1(01*0)*1|0)+$/
Perl test/esempio:
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";
}
Uscite:
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
+1. Ora questo è fantastico. Non avevo idea che tu potessi creare un'espressione regolare facile da un DFA. –
Grazie per la masterclass. Penso che non segnerò questo compito su Codewars come completato, come non lo farei io stesso. – Minras
Non credo che lo fareste. Non posso credere in nessuna lingua usando un'espressione regolare potrebbe mai essere il modo migliore per farlo.
so che non è il modo migliore. So che si può fare ma non riesco a capire come. Si tratta di disegnare gli automi e di eliminare gli stati intermedi. – Jaelebi
@Dave Webb, puoi sicuramente farlo. In realtà, questo è un tipo piuttosto comune di esercizio in un corso di teoria della CS, ed è per questo che sono riluttante a rispondere a questa domanda. – BobbyShaftoe
sai come si può fare? qualche suggerimento? – Jaelebi
Se si divide un numero per tre, ci sono solo tre possibili remainder (0, 1 e 2). Quello a cui mirate è assicurarsi che il resto sia 0, quindi un multiplo di tre.
questo può essere fatto da un automa con i tre stati:
ora pensare di qualsiasi numero non negativo (questo è il nostro dominio) e moltiplicarlo per due (virare uno zero binario fino alla fine). Le transizioni per che sono:
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).
pensare anche un numero non negativo, moltiplicarlo per due poi aggiungere una (virare un uno binario fino alla fine). Le transizioni per questo sono:
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).
Questa idea è che, alla fine, è necessario finire nello stato ST0. Tuttavia, dato che può esserci un numero arbitrario di sottoespressioni (e sotto-sotto-espressioni), non si presta facilmente alla riduzione a un'espressione regolare.
Quello che devi fare è consentire qualsiasi delle sequenze di transizione che possono ottenere da ST0 a st0 poi basta ripeterle:
Questi riducono a due sequenze RE:
ST0 --> ST0 : 0+
[0]
ST0 --> ST1 (--> ST2 (--> ST2)* --> ST1)* --> ST0: 1(01*0)*1
[1] ([0] ([1] )* [0] )* [1]
o la regex:
(0+|1(01*0)*1)+
Questa cattura i multipli di tre, o almeno i primi dieci che ho testato.Puoi provare quanti ne vuoi, funzioneranno tutti, questa è la bellezza dell'analisi matematica piuttosto che delle prove aneddotiche.
La risposta è (1(01*0)*10*)*, che è l'unico finora che funziona per 110011
E 'questo il vostro lavoro teoria computazionale? – BobbyShaftoe
forse potresti dare qualche background come quello che vuoi fare e quale lingua vuoi usare. –
una parte di esso. Penso di avere l'NFA corretto ma non riesco a eliminare i passaggi intermedi perché è piuttosto complicato. – Jaelebi