È possibile semplificare ulteriormente questa espressione regolare?

Question

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.

Answer 1

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.

Answer 2

Questo dovrebbe funzionare:

b* a b* (a b* a b*)* |  a* b a* (b a* b a*)*

Answer 3

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ì. :)

Answer 4

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.