Est-il possible de simplifier davantage cette expression régulière?

Question

Je travaille sur des devoirs pour ma classe de compilateur et j'ai le problème suivant:

Écrivez une expression régulière pour toutes les chaînes de a et b contenant un nombre impair de a ou un nombre impair de b (ou des deux).

Après beaucoup de travail au tableau blanc, j'ai proposé la solution suivante:

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

Cependant, est-ce le plus simplifié que je puisse l’obtenir? J'ai envisagé de construire le DFA en essayant de minimiser le nombre d'états là-bas pour voir si cela pourrait m'aider à simplifier les choses, mais je me suis dit que je demanderais d'abord aux gourous des expressions régulières sur SO.

Answer 1

Prenez la recommandation de Greg D de commencer par un (aa) * et d’aller de là. Sepp2k a presque tout à fait raison, mais la véritable considération est que vous ne vous souciez pas de l'autre lettre. Ce que je veux dire, c’est, quand vous regardez le "nombre impair de" contrainte, vous ne vous souciez pas du tout de ce que les b sont dans votre chaîne. Ainsi, collez des b * partout où vous pouvez:)

La réponse de Sepp2k est presque exacte, mais celle-ci est correcte:

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

Pour préciser, cette expression rationnelle répertorie toutes les chaînes avec un nombre impair de a (première section) et les unités OR avec ces chaînes avec des chaînes contenant un nombre impair de b.

Answer 2

Cela devrait fonctionner:

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

Answer 3

J'ai bien peur de ne pas croire que votre expression rationnelle est correcte. Considérons la chaîne:

aba

Nous avons plusieurs choix pour les matchs, mais le fait qu’il soit de longueur impaire signifie que nous devons faire correspondre un seul à l’avant, donc:

(a)(ba)

Mais, malheureusement, il est impossible pour votre deuxième groupe principal de correspondre (ba).

Lorsqu’il s’agissait d’une contrainte de ce type, j’ai trouvé plus facile de partir de la contrainte principale et de partir de là. Dans ce cas, votre contrainte est " impair, " alors commencez avec

a(aa)*

pour forcer un nombre impair de a et partir de là. :)

Answer 4

Je pense que vous devez aborder le problème différemment.

Vous essayez de faire correspondre tout ce qui ne contient pas les nombres pairs a et b .

Il serait probablement plus facile de commencer par quelque chose qui correspond aux numéros même de a et de b . À ce stade, tout ce que vous avez à faire est d’ajouter quelque chose à la fin qui correspond à la plus petite chaîne que vous souhaitez réellement faire correspondre.