Simplifier une expression régulière

Question

J'ai une question très simple (avec un jeu de mots).

Quelle est la forme la plus simple de cette expression régulière ?

(((0|1)*(00)(0|1)*)((0|1)*(11)(0|1)*))|(((0|1)*(11)(0|1)*)((0|1)*(00)(0|1)*))

Je crée une expression régulière qui accepte une langue pour toutes les chaînes binaires qui contiennent les sous-chaînes 00 et 11 (dans n'importe quel ordre).

L'expression que j'ai maintenant fonctionne, mais je suis sûr qu'elle peut être simplifiée.

Answer 1

C'est presque la même regex. J'ai seulement converti le (0|1) en [01] , a ajouté un [01]* à gauche et à droite partagés pour les deux cas (11 d'abord ou 00 d'abord) et supprimé certaines parenthèses qui n'étaient pas nécessaires :

[01]*(00[01]*11|11[01]*00)[01]*

---

Étapes de la reproduction

1. Déclaration avec

   (((0|1)*(00)(0|1)*)((0|1)*(11)(0|1)*))|(((0|1)*(11)(0|1)*)((0|1)*(00)(0|1)*))
__^^^^^_____^^^^^___^^^^^_____^^^^^______^^^^^_____^^^^^___^^^^^_____^^^^^___

2. Remplacer tous les (0|1) par [01]

   (([01]*(00)[01]*)([01]*(11)[01]*))|(([01]*(11)[01]*)([01]*(00)[01]*)) _______^^^^____________^^^^_______________^^^^____________^^^^_______

3. Supprimer les parenthèses autour de (00) y (11) comme vous ne voulez pas capturer ce groupe et vous n'avez pas de * , + , ? derrière la parenthèse. Elle n'est donc pas nécessaire en raison de l'ambiguïté.

   (([01]*00[01]*)([01]*11[01]*))|(([01]*11[01]*)([01]*00[01]*))
_^____________^^____________^___^____________^^____________^_

4. Supprimer encore une parenthèse qui ne résout aucune ambigüité :

   ([01]*00[01]*[01]*11[01]*)|([01]*11[01]*[01]*00[01]*)
________^^^^^^^^^^_________________^^^^^^^^^^________

5. Effondrement [01]*[01]* en [01]* ce qui signifie exactement la même chose.

   ([01]*00[01]*11[01]*)|([01]*11[01]*00[01]*)
_^^^^^_________^^^^^___^^^^^_________^^^^^_

6. Extraire les préfixes et suffixes courants [01]*

   [01]*(00[01]*11|11[01]*00)[01]*