Expression non régulière

Version imprimable

15/03/2010, 12h57
Mister Nono

Expression non régulière

Bonjour,

Java propose des méthodes pour pouvoir traiter des expressions régulières.

Mais je recherche un ou des exemples d'expressions qui ne sont pas des expressions régulières.

Avez-vous des idées ?

Merci d'avance. ;)
15/03/2010, 13h04
tchize_

Je crois que tu confond. Dans

Code:

if (a.matches(b));

l'expression régulière c'est b, pas a. Je vois donc pas dans ce contexte ce que tu appellerais un "expression non régulière", hormis un string b qui déclencherais une exception car n'étant pas correcte!

exemple de valeur incorrecte: b="((a)"; // nombre de parenthèses erroné
15/03/2010, 13h06
Deaf

Bonjour,

je ne suis pas sûr de bien comprendre ta question.
Une expression peut être régulière si elle réponds à certains critères de syntaxe, mais elle peut aussi être utilisée comme expression "normale".

Après certaines expression ne peuvent pas être des expressions régulières, comme:

Code:

"crochet[non_fermé"
15/03/2010, 15h19
Mister Nono
Citation:

Envoyé par tchize_

Je crois que tu confond. Dans

Code:

if (a.matches(b));

l'expression régulière c'est b, pas a. Je vois donc pas dans ce contexte ce que tu appellerais un "expression non régulière", hormis un string b qui déclencherais une exception car n'étant pas correcte!

exemple de valeur incorrecte: b="((a)"; // nombre de parenthèses erroné

Non, non, je ne juge pas le code mais la possibilité d'évaluer sans ambiguïté une expression.

Par exemple, peut-on évaluer PI sachant que la grandeur de sa partie décimale vers plus l'infini ?

b="((a)" peut être en soit une expression régulière, en effet je peux très bien recherche la chaine suivante :
Code:

1 2 b="((a)"
En fait dans ce cas cela dépend de l'alphabet et de la grammaire reconnue.

Le débat est lancé. :mouarf:

A+ ;)
15/03/2010, 16h31
tchize_

non, ((a) n'est pas un expression régulière. L'api javadoc est très claire sur ce qu'est une expression régulière. Et Pi n'a rien à voir avec çà 8O. De plus il n'y a pas d'ambiguité sur la grammaire. Tu veux savoir quoi au juste????
15/03/2010, 16h58
Mister Nono

Citation:

Envoyé par tchize_

non, ((a) n'est pas un expression régulière?

Ah bon ! Je ne peux pas faire une recherche de la sous-chaine ((a) appartenant à une chaine ?

Cela m'étonnerait beaucoup. :aie:

A+ ;)
15/03/2010, 17h02
dingoth

Tu peux le faire, mais l'expression régulière associée est alors:

$\(a$
15/03/2010, 17h09
Mister Nono

Citation:

Envoyé par dingoth

Tu peux le faire, mais l'expression régulière associée est alors:

$\(a$

Je n'ai jamais dis le contraire. :ccool:

Ma question est de trouver un contre exemple d'une expression régulière : cela ne semble pas évident du tout puisque je n'ai pas de réponse pour cela. :mouarf:

A bientôt. ;)
15/03/2010, 17h32
adiGuba

Salut,

Ce serait quoi une "expression non régulière" pour toi ?
Pour moi cela n'a pas trop se sens :koi:

a++
15/03/2010, 17h45
Mister Nono

Citation:

Envoyé par adiGuba

Salut,

Ce serait quoi une "expression non régulière" pour toi ?
Pour moi cela n'a pas trop se sens :koi:

a++

Réponse simpliste mais pourquoi faire compliqué quand on peut faire simple : http://fr.wikipedia.org/wiki/Langage_rationnel

A+ ;)
15/03/2010, 17h49
Deaf

Tu ne nous apprend rien avec ce lien.
Ce qu'adiGuba voulais savoir (comme les auters ayant répondu ici), c'est :
Qu'est-ce que tu veux réellement savoir?

Si tu soutiens que ((a) est une expression régulière, alors tout est expression régulière...
15/03/2010, 18h17
Mister Nono

Citation:

Envoyé par Deaf

Tu ne nous apprend rien avec ce lien.
Ce qu'adiGuba voulais savoir (comme les auters ayant répondu ici), c'est :
Qu'est-ce que tu veux réellement savoir?

Si tu soutiens que ((a) est une expression régulière, alors tout est expression régulière...

Absolument faux : tout ne peux pas être interprété par un Automate Fini Déterministe (AFD), de même à quoi cela servirait-il de démontrer mathématiquement qu'une expression est régulière s'il n'existait pas de contre exemple ? :aie:

C'est justement un contre exemple que je cherche. :mouarf:

A+ ;)
15/03/2010, 19h06
adiGuba

Citation:

Envoyé par Mister Nono

C'est justement un contre exemple que je cherche. :mouarf:

Tu recherches des exemples d'ensembles qui ne peuvent pas être représentés par une expression régulière ? Pourquoi ne pas l'avoir dit plus tôt au lieu de parler d'expression non régulière...

Si tu veux des réponses claires il faut que la question le soit tout autant...

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...

a++
15/03/2010, 19h18
tchize_

adiguba: si c'est ça ce qu'il cherche, c'est ce que j'ai dit au début, il confond l'expression régulière et l'ensemble testé. Une expression régulière en java, c'est çà, point

http://java.sun.com/j2se/1.4.2/docs/...x/Pattern.html

Citation:

Envoyé par tchize_

adiguba: si c'est ça ce qu'il cherche, c'est ce que j'ai dit au début, il confond l'expression régulière et l'ensemble testé. Une expression régulière en java, c'est çà, point

http://java.sun.com/j2se/1.4.2/docs/...x/Pattern.html

NON, NON et NON, tu n'as vraiment pas compris la question initiale. :aie:

J'ai trouvé une réponse tout à fait satisfaisant sur le site du CNAM qui indique ceci dans un de ses cours :
Code:

1 2 3 4 Parmi les langages qui ne peuvent pas être d´écrits par automates finis, voici quelques exemples classiques : – les chaînes qui ont le même nombre de a que de b. – les chaînes bien parenthésées (avec une parenthèse fermante pour chaque ouvrante et une bonne imbrication des parenthèses).
L'URL du cours est http://deptinfo.cnam.fr/~barthe/NFP108/poly-automates.pdf

Bon cours et à bientôt. ;)

16/03/2010, 09h31
adiGuba

Citation:

Envoyé par Mister Nono

NON, NON et NON, tu n'as vraiment pas compris la question initiale. :aie:

En même temps la question initiale est tout sauf clair...

a++
16/03/2010, 09h32
dingoth

Effectivement, ce ne sont des pas des automates finis, mais cela n'en fait pas des expressions non-rationnelles.

Si tu veux en savoir davantage, je t'invite à lire la page Wikipédia à ce sujet: http://fr.wikipedia.org/wiki/Langage_formel et son équivalent anglais, bien plus complet.
16/03/2010, 10h16
tchize_

apparement la question n'a rien a voir avec les expression régulière en java. Si tu cherche des exemples d'ensembles qui ne peuvent pas être défini par des regexp, je donnerais celle-ci, assez courrament mal compris dans ces forum:

une adresse email respectant le RFC 5322

Je ne connais aucune regexp à ce jour capable de valider correctement une addresse email suivant ce RFC :mouarf:
17/03/2010, 03h36
Obsidian

Il y a un cas typique de langage non régulier : les langages récursifs (auto-contenus).

Par exemple, il est impossible d'écrire une expression régulière qui serve de validateur HTML, la page entière étant considérée valide si l'expression arrive à retrouver la page entière. Il faut un automate à pile pour le faire, ce qui fait passer les langages récursifs dans la catégorie 2 de la classification de Chomsky.

Ceci s'explique assez facilement par le fait que l'on veuille retrouver exactement le même nombre de balises fermantes que de balises ouvrantes et que donc, pour cela, il faut les compter. Comme leur nombre est potentiellement infini, ce n'est pas possible avec un automate fini ordinaire.

On note toutefois que si on fixe un nombre maximum de balises imbriquées, alors il est possible d'énumérer tous les cas possibles, et donc de dresser un automate fini, ce qui rend le langage à nouveau régulier. Par contre, l'expression qui le décrit risque de faire plusieurs méga-octets et ça ne vaudra vraiment pas la peine. :-)
17/03/2010, 06h42
Mister Nono

Citation:

Envoyé par Obsidian

Il y a un cas typique de langage non régulier : les langages récursifs (auto-contenus)...

Merci Obsidian pour cette explication.

A+ ;)
05/05/2011, 21h38
Obsidian

Bonsoir,

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

Citation:

Envoyé par adiGuba

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:

(([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.
05/05/2011, 23h49
prgasp77

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 ».

Ç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:

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 !

06/05/2011, 00h41
tchize_

Citation:

Envoyé par Obsidian

Si quelqu'un arrive à la raccourcir, c'est avec grand plaisir !

Code:

return (i%6==0);

Le reste, c'est de la branlette intellectuelle qui fait perdre du temps :?

Edit: et je sais pas d'où ca sort çà :

Code:

a*(ba*)* = (a*b)a*

Mais ca m'a tout l'air erroné. aaabaababaab matche la première expression mais pas la deuxième :mrgreen:
06/05/2011, 00h49
Obsidian

Citation:

Envoyé par tchize_

Code:

return (i%6==0);

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_

Edit: et je sais pas d'où ca sort çà :

Code:

a*(ba*)* = (a*b)a*

Mais ca m'a tout l'air erroné. aaabaababaab matche la première expression mais pas la deuxième :mrgreen:

C'est parce que tu as oublié une étoile :

Code:

a*(ba*)* = (a*b)*a*

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