É possível simplificar esta expressão regular mais longe?

Question

Eu estou trabalhando em algum trabalho de casa para minha classe compilador e eu tenho o seguinte problema:

Escrever uma expressão regular para todas as seqüências de a 's e b ' s que contêm um número ímpar de a 's ou um número ímpar de b s '(ou ambos).

Depois de um monte de trabalho whiteboard eu vim com a seguinte solução:

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

No entanto, é que este é o mais simplificado posso obtê-lo? Eu considerei a construção do DFA tentar minimizar o número de estados lá para ver se ele iria me ajudar a simplificar, mas eu percebi que eu iria pedir aos gurus regex no SO primeiro.

Answer 1

Tome recomendação de começar com um (aa) *, e indo de lá Greg D's. Sepp2k quase tem direito, mas a consideração real é que você não se preocupam com a outra carta. O que quero dizer é que, quando você está olhando para o "número ímpar de uma" restrição, você não se importa em tudo sobre o que b'S estão na cadeia. Assim, vara b * 's em qualquer lugar você pode:)

A resposta de Sepp2k é quase certo, mas isso é o correto:

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

Para elaborar, este figuras regex fora todas as cordas com um número ímpar de um de (primeira seção) e OR aquelas cordas com quaisquer strings contendo um número ímpar de b da.

Answer 2

Isso deve funcionar:

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

Answer 3

Eu tenho medo que eu não acredito que sua regex como escrito está correto. Considere a string:

aba

Nós temos um par de escolhas para os jogos, mas o fato de que é meio estranho de comprimento que deve corresponder a um um solitário na frente, assim:

(a)(ba)

Mas, infelizmente, é impossível para o seu segundo agrupamento principal lá para corresponder (BA).

Quando se tratar de uma restrição como este, eu achei mais fácil para começar a partir da restrição núcleo e de lá ir. Neste caso, a restrição é "estranho", assim que começar com

a(aa)*

para forçar um número ímpar de a de e de lá ir. :)

Answer 4

Eu acho que você precisa abordar o problema de maneira diferente.

Você está tentando combinar qualquer coisa que não tem mesmo números de ambos a e b.

Ele provavelmente seria mais fácil começar com algo que corresponde a até número de a e b. Tudo que você tem que fazer naquele momento seria adicionar algo na extremidade que corresponde ao menor seqüência que você realmente deseja corresponder.