Regex qui définit un langage régulier avec {a, b} sans une sous-chaîne avec exactement 3 b (bbb)

Question

À peu près ce que dit la question. Je suis venu avec

(ba)?(a + bb + bbbbb + aba)*(ab)?

Y at-il quelque chose de plus lisible? Ou est-ce incorrect? Je sais que vous ne devriez pas vraiment faire ce genre de chose avec Regex quand vous pouvez simplement y aller! ~/Bbb/dans votre code, mais c'est un exercice de théorie.

Merci.

Modifier pour clarifier: Je n'utilise pas | pour représenter le bit OR dans la Regex et en utilisant + à la place. Désolé pour la confusion.

Éditer 2: {a,b} est pour un langage avec juste 'a' et 'b' caractères. Pas {mininum, maximum}. Encore pardon.

Édition 3: Parce que cela fait partie d'une classe de théorie, nous traitons juste les bases de Regex. Les seules choses que vous pouvez utiliser sont +,?,() Et *. Vous ne pouvez pas utiliser {minimum, maximum).

Answer 1

Je pense que j'ai une regex de travail. Soit b° - une notation que j'ai inventée tout à l'heure - soit l'expression rationnelle qui correspond à zéro ou plus b, sauf qu'elle ne correspondra pas à trois d'entre eux. Cela peut être remplacé par (ε | b | bb | bbbb+), donc ne vous inquiétez pas que j'utilise la magie ou quoi que ce soit. Maintenant, je pense que les chaînes correspondantes peuvent être vues comme des sous-modèles répétitifs de 0 ou plus suivis de b°, ce qui pourrait être (a*b°)*, mais il faut qu'il y ait au moins un "a" entre les séquences de b. Donc, votre regex final est a*b°(a+b°)*.

Depuis b° peut correspondre à la chaîne vide, le a* initial est superflu que la a+ peut prendre le départ un est très bien, donc le regex peut être optimisée jusqu'à b°(a+b°)* (merci, wrikken).

Answer 2

Hmm, quelque chose comme ça?

^(a|(?<!b)b{1,2}(?!b)|b{4,})*$ 

modifier:

Edit 3: Parce que cela fait partie d'une classe de théorie, nous sommes juste affaire avec les bases de Regex. Les seules choses que vous pouvez utiliser sont +,?,() Et *. Vous ne pouvez pas utiliser {minimum, maximum).

Pfff, en parlant de lacer vos mains derrière votre dos ... Une solution simple: vous ne pouvez pas le faire (^ & $ sont exigences pour jamais au travail), et nous avons besoin du |. Alors, imaginez de meilleures conditions. Laissant tomber le lookbehind & pourrait préanalyse être fait, mais ne va pas être assez (du moins, pas sans violer DRY):

^(b|bb|bbbb+)?(a+(b|bb|bbbb+)?)*$ 

Answer 3

Vous êtes correspondant à une chaîne sans précisément 3 b dans une rangée. Cela signifie que vous regardez des sous-chaînes comme "aa", "aba", "abba", et "abbbbb * a", où l'un des a extérieur peut être le début ou la fin de la chaîne, peut se chevaucher, et peut être multiple. Cela suggère quelque chose comme:

(a + ab + abb + abbbbb*)* 

avec des ajouts appropriés pour tenir compte de l'absence de a au début de la chaîne. Il y a beaucoup de répétitions, mais c'est comme ça que les expressions régulières fonctionnent sous forme de base.