Expression non régulière

**Mister Nono** · 15/03/2010, 12h57

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.

**tchize_** · 15/03/2010, 13h04

Je crois que tu confond. Dans

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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é

**Deaf** · 15/03/2010, 13h06

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

"crochet[non_fermé"

**Mister Nono** · 15/03/2010, 15h19

Envoyé par tchize_

Je crois que tu confond. Dans

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

A+

**tchize_** · 15/03/2010, 16h31

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 çà

. De plus il n'y a pas d'ambiguité sur la grammaire. Tu veux savoir quoi au juste????

**Mister Nono** · 15/03/2010, 16h58

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.

A+

**dingoth** · 15/03/2010, 17h02

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

\(\(a\)

**Mister Nono** · 15/03/2010, 17h09

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.

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.

A bientôt.

**adiGuba** · 15/03/2010, 17h32

Salut,

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

a++

**Mister Nono** · 15/03/2010, 17h45

Envoyé par adiGuba

Salut,

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

a++

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

A+

**Deaf** · 15/03/2010, 17h49

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

**Mister Nono** · 15/03/2010, 18h17

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 ?

C'est justement un contre exemple que je cherche.

A+

**adiGuba** · 15/03/2010, 19h06

Envoyé par Mister Nono

C'est justement un contre exemple que je cherche.

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

**tchize_** · 15/03/2010, 19h18

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

**Mister Nono** · 16/03/2010, 08h27

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.

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**adiGuba** · 16/03/2010, 09h31

Envoyé par Mister Nono

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

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

a++

**dingoth** · 16/03/2010, 09h32

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.

**tchize_** · 16/03/2010, 10h16

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

**Obsidian** · 17/03/2010, 03h36

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