Expression régulière pour nombre impair de a

J'ai un problème à résoudre l'exercice suivant et j'apprécierais toute aide.

Laisser Σ = {a,b}. J'ai besoin de donner une expression régulière pour toutes les chaînes contenant un nombre impair de un.

Je vous remercie pour votre temps

Assurez-vous. Par exemple, toutes les chaînes ayant abba répété une ou plusieurs fois est décrite par le texte suivant: Σ*(abba)+Σ*
Note ce, sur la CS de la Pile d'Échange, ce n'est pas une question de programmation.
Mon mauvais - j'en sais plus maintenant

OriginalL'auteur kskyriacou | 2015-03-06

  1. 8
    b*(ab*ab*)*ab*

    la partie principale est (ab*ab*)*, qui énumérer toutes les possibilités du même nombre de as. puis à la fin, un supplément de a doit exister pour faire bizarre.

    avis que cette expression est équivalente à:

    b*a(b*ab*a)*b*

    ces deux constructions sont dans la forme définie par le lemme de pompage:

    http://en.wikipedia.org/wiki/Pumping_lemma

    Mise à JOUR:

    @MahanteshMAmbi présenté son souci de l'expression régulière correspondant à la casse aaabaaa. En fait, il ne le fait pas. Si nous courons grep, nous allons le voir clairement ce qui est mis en correspondance.

    $ echo aaabaaa | grep -P -o 'b*(ab*ab*)*ab*'
aaabaa
a

    -o option de grep s'imprime chaque instance correspondante à chaque ligne. Dans ce cas, comme nous pouvons le voir, l'expression régulière est l'association de deux fois. L'un des matchs 5 as, l'une correspond à 1 a. L'apparente erreur dans mon commentaire ci-dessous est causée par un mauvais cas de test, plutôt que de l'erreur dans l'expression régulière.

    Si nous voulons qu'il soit rigoureux à utiliser dans la vie réelle, il est probablement mieux d'utiliser des ancres dans l'expression de la force d'une chaîne complète de match:

    ^b*(ab*ab*)*ab*$

    donc:

    $ echo aaabaaa | grep -P -q '^b*(ab*ab*)*ab*$'
$ echo $?
1
    Vous, il est très clair, merci beaucoup
    b*(abab)*ab* ne pas travailler pour aaabaa
    vous avez manqué les étoiles après bs à l'intérieur de la parenthèse, mon ami.
    echo aaabaaa | grep -P 'b*(ab*ab*)*ab*' --> aaabaaa
    J'ai mis à jour la réponse. qui devrait répondre à votre question. l'original de la réponse était correcte.

    OriginalL'auteur Jason Hu

  2. 0
    ^[^a]*a(?=[^a]*(?:a[^a]*a)*[^a]*$).*$

    Ce ne trouverez que nombre impair de a's pour toute chaîne générique.Voir la démo.

    https://regex101.com/r/eS7gD7/22

    Je vous remercie, mais la réponse que je cherchais est exactement comme celui HuStmpHrr fourni

    OriginalL'auteur vks