È possibile semplificare ulteriormente questa espressione regolare?
-
07-07-2019 - |
Domanda
Sto lavorando ad alcuni compiti per la mia classe di compilatore e ho il seguente problema:
Scrivi un'espressione regolare per tutte le stringhe di a e b che contengono un numero dispari di a o un numero dispari di b (o entrambi).
Dopo molto lavoro sulla lavagna ho trovato la seguente soluzione:
(aa|bb)* (ab|ba|a|b) ((aa|bb)* (ab|ba) (aa|bb)* (ab|ba) (aa|bb)*)*
Tuttavia, è questo il più semplificato che posso ottenere? Ho pensato di costruire il DFA cercando di minimizzare il numero di stati lì per vedere se mi avrebbe aiutato a semplificare, ma ho pensato di chiedere prima ai guru del regex su SO.
Soluzione
Prendi la raccomandazione di Greg D di iniziare con un (aa) * e andare da lì. Sepp2k ha quasi ragione, ma la vera considerazione è che non ti importa dell'altra lettera. Quello che voglio dire è che quando stai guardando il "dispari numero di un" il vincolo, non ti importa niente di ciò che b sono nella tua stringa. Quindi, attacca b * ovunque tu sia :)
La risposta di Sepp2k è quasi giusta, ma questa è corretta:
b* a b* (a b* a b* )* | a* b a* (b a* b a* )*
Per elaborare, questa regex calcola tutte le stringhe con un numero dispari di a (prima sezione), e quelle stringhe OR con qualsiasi stringa contenente un numero dispari di b.
Altri suggerimenti
Questo dovrebbe funzionare:
b* a b* (a b* a b*)* | a* b a* (b a* b a*)*
Temo di non credere che la tua regex come scritta sia corretta. Considera la stringa:
aba
Abbiamo un paio di scelte per le partite, ma il fatto che sia di lunghezza dispari significa che dobbiamo abbinare una a sola nella parte anteriore, quindi:
(a)(ba)
Ma, purtroppo, è impossibile che il tuo secondo gruppo principale lì corrisponda (ba).
Quando ho a che fare con un vincolo come questo, ho trovato più facile partire dal vincolo principale e passare da lì. In questo caso, il tuo vincolo è "dispari", quindi inizia con
a(aa)*
per forzare un numero dispari di a
e andare da lì. :)
Penso che tu debba affrontare il problema in modo diverso.
Stai cercando di abbinare qualsiasi cosa che non abbia numeri pari sia di a
che b
.
Probabilmente sarebbe più facile iniziare con qualcosa che corrisponda a pari numeri di a
e b
. Tutto quello che devi fare a quel punto sarebbe aggiungere qualcosa alla fine che corrisponda alla stringa più piccola che vuoi effettivamente abbinare.