È possibile semplificare ulteriormente questa espressione regolare?

Question

Sto lavorando su alcuni compiti per la mia classe del compilatore e ho il seguente problema:

Scrivi un'espressione regolare per tutte le stringhe di un 's e b' s che contengono un numero dispari di a o un numero dispari di b (o entrambi).

Dopo un sacco di lavoro lavagna mi si avvicinò con la seguente soluzione:

(aa|bb)* (ab|ba|a|b) ((aa|bb)* (ab|ba) (aa|bb)* (ab|ba) (aa|bb)*)* 

tuttavia, è questo è il più semplificata posso farlo? Ho preso in considerazione la costruzione del DFA cercando di ridurre al minimo il numero di stati lì per vedere se mi avrebbe aiutato a semplificare, ma ho pensato di chiedere prima il gergo regex su SO.

Answer 1

Prendere Greg D's raccomandazione di iniziare con un (aa) *, e andare da lì. Sepp2k ha quasi ragione, ma la vera considerazione è che non ti interessa l'altra lettera. Quello che voglio dire è che quando guardi al vincolo "numero dispari di a", non ti importa di cosa sono i b nella tua stringa. Così, bastone b * 's ovunque è possibile :)

risposta di Sepp2k è quasi giusto, ma questo è corretto:

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

Elaborare, questa regex capisce tutte le stringhe con un numero dispari di una di (prima sezione) e OR quelle stringhe con qualsiasi stringa contenente un numero dispari di b.

Answer 2

Ho paura di non credere che la sua espressione regolare sia corretta. Si consideri la stringa:

aba 

Abbiamo una scelta di coppia per le gare, ma il fatto che è strano di lunghezza significa che dobbiamo abbinare un un solitario nella parte anteriore, in modo da:

(a)(ba) 

Ma, purtroppo , è impossibile che il tuo secondo gruppo principale vi corrisponda (ba).

Quando si ha a che fare con un vincolo come questo, ho trovato più semplice iniziare dal vincolo principale e andare da lì. In questo caso, il vincolo è "strano", in modo da iniziare con

a(aa)* 

per forzare un numero dispari di a 's e passare da lì. :)

Answer 3

Questo dovrebbe funzionare:

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

Answer 4

Penso che sia necessario affrontare il problema in modo diverso.

Si sta tentando di abbinare qualsiasi cosa che non ha numeri pari di entrambi a e b.

Probabilmente sarebbe più facile iniziare con qualcosa che corrisponde anche numero 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.