IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Expression non régulière


Sujet :

Algorithmes et structures de données

  1. #21
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Septembre 2007
    Messages
    7 360
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2007
    Messages : 7 360
    Points : 23 600
    Points
    23 600
    Par défaut
    Bonsoir,

    Pardon de faire remonter un fil vieux de plus d'un an mais je cherchais la solution depuis lors.

    Citation Envoyé par adiGuba Voir le message
    Après des contres exemples tu peux en avoir plein. Par exemple si les nombres de la table de 5 est facilement représentable ( "\d*[05]" ), ce n'est pas le cas de la table de 6 qui n'est pas représentable avec une expression régulière...
    Si :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    (([39]|([147]|[258][0369]*[258])([147][0369]*[258]|[0369])*5|([258]|[147][0369]*[147])([258][0369]*[147]|[0369])*[17])*([06]|([147]|[258][0369]*[258])([147][0369]*[258]|[0369])*[28]|([258]|[147][0369]*[147])([258][0369]*[147]|[0369])*4))*

    Les entiers naturels multiples de n sont d'ailleurs un cas d'école classique lorsque l'on étudie les langages, et les « expressions régulières » ont pour ainsi dire existé avant les ordinateurs. Par contre, en général, on travaille avec des binaires, pour éviter de se retrouver avec ce genre d'équation.

    Par contre, inutile de dire que ce n'est pas trivial et que selon n, le problème peut être très simple ou assez compliqué. mais il y a quand même un avantage majeur à établir la régularité d'un langage donné : la possibilité d'effectuer cette reconnaissance en utilisant l'AFD associé, ce qui garantit que le problème est faisable quelque soit la longueur du mot analysé, et ce en complexité linéaire.

    Si je traite un nombre de 7000 milliards de chiffres et que je mets un an à l'émettre, je sais que je n'aurais jamais besoin de plus de mémoire que les quelques octets alloués au départ et que j'obtiendrai la réponse immédiatement après la transmission du dernier chiffre.

  2. #22
    Membre émérite
    Avatar de prgasp77
    Homme Profil pro
    Ingénieur en systèmes embarqués
    Inscrit en
    Juin 2004
    Messages
    1 306
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur en systèmes embarqués
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Juin 2004
    Messages : 1 306
    Points : 2 466
    Points
    2 466
    Par défaut
    Juste pour savoir ... cette expression tu la sort d'où ? Tu as étudié la table des 6 juste pour pouvoir avoir le dernier mot ?
    Si oui, gros − que dis-je ? GROS − « FÉLICITATION ».
    -- Yankel Scialom

  3. #23
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Septembre 2007
    Messages
    7 360
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2007
    Messages : 7 360
    Points : 23 600
    Points
    23 600
    Par défaut
    Ça se fait en écrivant l'automate qui permet de déterminer le modulo d'un nombre à chaque fois qu'on ajoute un chiffre, en rédigeant la grammaire associée pour chaque état, puis en s'efforçant de la rendre régulière avec le lemme d'Arden, et les différentes propriétés des expressions régulières telles que a*(ba*)* = (a*b)*a* = (a | b)* = (a*b*)*, etc.

    En théorie, donc, on peut faire pareil avec tous les multiples.

    Le code Bash sous UNIX produit tous les entiers naturels de zéro à dix millions, donc 10.000.001 nombres en tout, egrep e, extrait les multiples de 6 et la boucle qui suit vérifie leur modulo 6. Le tri final compte les différents modulos. On obtient donc 1666667 zéros (soit 10.000.001 ÷ 6) et rien d'autre :

    Code Shell : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    $ echo p{0..10000000}s | tr ' ' '\n' | egrep 'p(([39]|([147]|[258][0369]*[258])([147][0369]*[258]|[0369])*5|([258]|[147][0369]*[147])([258][0369]*[147]|[0369])*[17])*([06]|([147]|[258][0369]*[258])([147][0369]*[258]|[0369])*[28]|([258]|[147][0369]*[147])([258][0369]*[147]|[0369])*4))*s' | sed -e 's/[ps]*//g' | while read i ; do echo $[ i % 6 ] ; done | sort | uniq -c
     1666667 0

    Les lettres « p » et « s » qui encadrent les nombres sont des préfixes et suffixes, pour forcer egrep à traiter le nombre en entier et ne pas reconnaître un sous-nombre au milieu.

    J'ai essayé de factoriser l'expression autant que j'ai pu jusqu'à arriver au résultat, mais je me suis arrêté dès que j'ai eu éliminé tous les non-terminaux. Si quelqu'un arrive à la raccourcir, c'est avec grand plaisir !

  4. #24
    Expert éminent sénior
    Avatar de tchize_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2007
    Messages
    25 481
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Belgique

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Avril 2007
    Messages : 25 481
    Points : 48 806
    Points
    48 806
    Par défaut
    Citation Envoyé par Obsidian Voir le message
    Si quelqu'un arrive à la raccourcir, c'est avec grand plaisir !
    Le reste, c'est de la branlette intellectuelle qui fait perdre du temps

    Edit: et je sais pas d'où ca sort çà : Mais ca m'a tout l'air erroné. aaabaababaab matche la première expression mais pas la deuxième

  5. #25
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Septembre 2007
    Messages
    7 360
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2007
    Messages : 7 360
    Points : 23 600
    Points
    23 600
    Par défaut
    Citation Envoyé par tchize_ Voir le message
    Le reste, c'est de la branlette intellectuelle qui fait perdre du temps
    Si la « branlette intellectuelle » te gène, alors le forum Algo, ce n'est pas le bon endroit…

    Citation Envoyé par tchize_ Voir le message
    Edit: et je sais pas d'où ca sort çà : Mais ca m'a tout l'air erroné. aaabaababaab matche la première expression mais pas la deuxième
    C'est parce que tu as oublié une étoile :

    UPDATE : C'est moi qui l'avais oubliée. Désolé !

+ Répondre à la discussion
Cette discussion est résolue.
Page 2 sur 2 PremièrePremière 12

Discussions similaires

  1. expression non vu par IE
    Par pmoury06 dans le forum Général JavaScript
    Réponses: 1
    Dernier message: 12/03/2009, 12h17
  2. LEFT JOIN expression non supportee
    Par Tymk dans le forum Requêtes et SQL.
    Réponses: 1
    Dernier message: 04/06/2008, 11h37
  3. Réponses: 3
    Dernier message: 18/10/2007, 17h30
  4. Contourner une expression non définie
    Par TicTac75 dans le forum Access
    Réponses: 3
    Dernier message: 20/02/2007, 19h52
  5. Réponses: 4
    Dernier message: 22/06/2006, 11h30

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo