Grammaires formelles ...
Titre initial : Grammaires formelles : mesure d'expressivité du langage
Bonjour,
Je voudrais savoir s'il existe un moyen de comparer les langages générés par deux grammaires formelles, l'un s'incluant dans l'autre, pour mesurer par exemple l'expressivité de l'un par rapport à l'autre (en essayant de calculer la proportion des formules de l'un par rapport à l'autre).
Je donne un exemple de mon idée :
J'ai une grammaire G1 qui définit un langage L1 par le vocabulaire et les règles suivantes :
V1 = {a, b}
Pour tout mot X et Y du langage L1 XY est dans L1.
Ma seconde grammaire G2 définit le langage L2 par :
V2 = {a, b}
Pour tout mot X et Y du langage L2 aXXY est dans L2.
On voit que L2 est strictement inclus dans L1, mais à quel point ?
Je redéfinis ma grammaire G1 pour pouvoir la comparer à G2. Pour cela je partitionne la règle de G1 en un ensemble de règles "disjointes" telles qu'elles soient les plus petites qui existent et parmi lesquelles apparaît la règle de G2. Ces règles produisent tous les mots à quatre lettres possibles, donc on rajoute en extension les mots de L1 à moins de trois lettres (ils sont en nombre finis).
On obtient G1' :
V1 = {a, b}
On a les mots a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb,
Pour tout mot X et Y du langage L2 aXXY est dans L2.
Pour tout mot X et Y du langage L2 bXXY est dans L2.
Pour tout mot X et Y du langage L2 aXYY est dans L2.
Pour tout mot X et Y du langage L2 bXYY est dans L2.
Pour tout mot X et Y du langage L2 aXYX est dans L2.
Pour tout mot X et Y du langage L2 bXYX est dans L2.
Si on compare G1' et G2 : si on ne tient pas compte des mots à moins de trois lettres (qui sont en nombre fini), à chaque itération on peut dire que G2 produit un mot parmi les 6 mots qu'on peut obtenir par G1. D'une certaine manière G2 produit 1/6 des mots de G1.
On pourrait désigner le nombre 1/6 par "mesure d'expressivité" de G2 par rapport à G1.
Ensuite on peut aller plus loin : mesurer l'expressivité d'un langage L2 par rapport à un langage L1 (qui le contient)... Puis celle de L3 par rapport à L1 (qui le contient), et ainsi comparer L1 et L3.
En faisant une analogie avec les nombres entiers, on peut définir la grammaire G1 qui génère tous les nombres entiers et G2 qui ne génère que les nombres divisibles par 7. Le langage généré par G2 contient 1/7 des mots du langage généré par G1 (puisqu'en partant de zero, tous les 7 entiers successifs 1 seul est divisible par 7). On pourrait aussi dire qu'il y a deux fois moins de nombres pairs que de nombres entiers... etc
Voila en gros l'idée...
Quelqu'un connaît-il des liens sur une théorie qui aurait été réalisée la dessus ? Ou peut-être l'approche est trop naïve ? Je cherche des outils qui pourrait m'aider à établir une telle mesure...
Merci d'avance pour vos réactions
Bonjour,
Je voudrais savoir s'il existe un moyen de comparer les langages générés par deux grammaires formelles, l'un s'incluant dans l'autre, pour mesurer par exemple l'expressivité de l'un par rapport à l'autre (en essayant de calculer la proportion des formules de l'un par rapport à l'autre).
Je donne un exemple de mon idée :
J'ai une grammaire G1 qui définit un langage L1 par le vocabulaire et les règles suivantes :
V1 = {a, b}
Pour tout mot X et Y du langage L1 XY est dans L1.
Ma seconde grammaire G2 définit le langage L2 par :
V2 = {a, b}
Pour tout mot X et Y du langage L2 aXXY est dans L2.
On voit que L2 est strictement inclus dans L1, mais à quel point ?
Je redéfinis ma grammaire G1 pour pouvoir la comparer à G2. Pour cela je partitionne la règle de G1 en un ensemble de règles "disjointes" telles qu'elles soient les plus petites qui existent et parmi lesquelles apparaît la règle de G2. Ces règles produisent tous les mots à quatre lettres possibles, donc on rajoute en extension les mots de L1 à moins de trois lettres (ils sont en nombre finis).
On obtient G1' :
V1 = {a, b}
On a les mots a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb,
Pour tout mot X et Y du langage L2 aXXY est dans L2.
Pour tout mot X et Y du langage L2 bXXY est dans L2.
Pour tout mot X et Y du langage L2 aXYY est dans L2.
Pour tout mot X et Y du langage L2 bXYY est dans L2.
Pour tout mot X et Y du langage L2 aXYX est dans L2.
Pour tout mot X et Y du langage L2 bXYX est dans L2.
Si on compare G1' et G2 : si on ne tient pas compte des mots à moins de trois lettres (qui sont en nombre fini), à chaque itération on peut dire que G2 produit un mot parmi les 6 mots qu'on peut obtenir par G1. D'une certaine manière G2 produit 1/6 des mots de G1.
On pourrait désigner le nombre 1/6 par "mesure d'expressivité" de G2 par rapport à G1.
Ensuite on peut aller plus loin : mesurer l'expressivité d'un langage L2 par rapport à un langage L1 (qui le contient)... Puis celle de L3 par rapport à L1 (qui le contient), et ainsi comparer L1 et L3.
En faisant une analogie avec les nombres entiers, on peut définir la grammaire G1 qui génère tous les nombres entiers et G2 qui ne génère que les nombres divisibles par 7. Le langage généré par G2 contient 1/7 des mots du langage généré par G1 (puisqu'en partant de zero, tous les 7 entiers successifs 1 seul est divisible par 7). On pourrait aussi dire qu'il y a deux fois moins de nombres pairs que de nombres entiers... etc
Voila en gros l'idée...
Quelqu'un connaît-il des liens sur une théorie qui aurait été réalisée la dessus ? Ou peut-être l'approche est trop naïve ? Je cherche des outils qui pourrait m'aider à établir une telle mesure...
Merci d'avance pour vos réactions
Réponses
-
Bonjour.
L'idée revient à peu près à "En prenant un mot dans le langage L1, quelle est la probabilité qu'il soit dans L2". La probabilité donne la mesure voulue.
Le problème est que définir une probabilité saine sur un ensemble infini dénombrable est assez délicat. L'équiprobabilité est impossible ("prendre un mot au hasard" ne veut rien dire). Donc deux voies (au moins) :
* Choisir une probabilité liée à la taille des mots.
* Traiter l'équiprobabilité sur un ensemble fini (par exemple les mots de moins de n lettres - mais est-ce raisonnable ?) et passer à la limite (A condition qu'il y en ait une). C'est dans ce sens qu'on peut dire qu'un entier sur 2 est pair.
Cordialement -
Merci pour cette réponse.
Avez-vous des exemples ou connaissez vous des liens sur l'utilisation de cette méthodes ? Y a-t-il eu des travaux en ce qui concerne le calcul d'une telle mesure (ou proba) en ce qui concerne les grammaires/langages formels et les langages logiques ? -
Non, je n'ai pas grand chose.
Mes références (plutôt culturelles) sont plutôt les probas sur les nombres premiers, et quelques notions historiques sur les axiomatisations des probabilités (Von Mises) vers 1900-1930.
Si je comprends bien tu (tutoyons nous si ça ne te gène pas) ne considères aucune notion sémantique dans ce que tu appelles "expressivité" (Dans le langage courant, être expressif est plutôt une notion sémantique que formelle). Serait-ce dans cette direction que la définition d'une probabilité pourrait se faire ? Par exemple, une expression trop courte ou au contraire trop longue peut perdre de la signification (Je pense à certaines démonstrations mathématiques en 600 pages, illisibles, donc jamais lues).
Cordialement -
En fait j'aurai déjà voulu une définition rigoureuse de cette mesure en ce qui concerne uniquement l'expressivité que j'appelerai "syntaxique" (en comparant la proportion de mots générés par deux grammaires l'une incluant l'autre).
Puis à partir de cette notion d'expressivité (qui reste vague désolé) aboutir à un concept plus élaboré défini pour les langages logiques : la notion d'expressivité sémantique (pourquoi pas). Elle s'obtiendrait en calculant avec le meme principe la proportion des formules obtenues à partir des axiomes et des règles de déduction logique par rapport à toutes celles du langage. Ainsi pourrait on peut-être calculer la proportion des tautologies d'un langage logique par rapport à toutes les formules de ce langage.
Ce sont juste des idées et j'aimerais parcourir de la littérature là dessus. Je suppose qu'il doit y en avoir mais avec une terminologie différente et je ne connais pas les mots clés de ce domaine... -
Moi non plus.
La seule chose proche que j'ai rencontrée est en philo, chez Popper, mais lui n'avait pas besoin de mathématiser par exemple son "contenu de vraisemblance".
Bonne chance dans ta recherche. -
Pour tout mot X et Y du langage L1 XY est dans L1.
Ma seconde grammaire G2 définit le langage L2 par :
V2 = {a, b}
Pour tout mot X et Y du langage L2 aXXY est dans L1.
On voit que L2 est strictement inclus dans L1, mais à quel point ?
Si L2 contient tous les mots, il vérifie ta condition et si L1 n'en contient aucun, idem... Donc je ne comprends pas pourquoi tu dis que L2 est inclus dans L2.
Est-ce que tu voulais définir L1 par la règle S--->SS, S étant l'axiome, et L2 par j ene sais quelle mécanisme officiellement reconnu comme définissant une "grammaire"?
Pardonne-moi, il est peut-être possible que tu définis Li comme la plus petite partie contenant Vi et tel que blabla... auquel cas, je n'ai pas vérifié l'inclusion. Je pensais que peut-être Vi était juste l'alphabet.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Bonjour,
Merci de m'avoir lu, par contre je n'ai pas très bien compris ou se situe l'ambiguité dans l'énoncé du problème ?
Je serais heureux de pouvoir l'éliminer, faut juste que je comprenne de quoi elle retourne... -
Ah oui je crois avoir compris :
On considère les mots initiaux (axiomes) des langages L1 et L2 comme étant les mots restreints à une seule lettre du vocabulaire (pour toutes les lettres)...
cela résout-il le pb ? -
Laisse tomber Nicola.
Désolé Christophe, mais ce qu'explique Nicola(s) au début est très clair et très courant. Inutile de polluer ce fil par du pinaillage. -
{\it
}Laisse tomber Nicola.
Désolé Christophe, mais ce qu'explique Nicola(s) au début est très clair et très courant. Inutile de polluer ce fil par du pinaillage.
????????????????????????????????????????
à Nicolas: je n'étais pas au courant des conventions. Mais j'ai modifié un peu mon msg. Donc je pense que tu définis L1 comme étant:
La plus petite partie de $\{a,b\}*$ qui contient $a$ et aussi $b$ et telle que pour tout mot $X$ et $Y$ de L1, le mot $XY\in L1$
(Mais non, en fait, je ne comprends pas! Le L1 ci-dessus semble contenir tous les mots)
{\bf je vois que je ne suis toujours pas au courant des conventions, vu que mon interpretation ci-dessus me parait erronée!}
à Gerard: la connerie et l'agressivité poussée à ce point, j'hallucine! Je posais une question: je n'ai pas compris les définitions!!! Bon apparemment, c'est interdit, je vous laisse disucter entre experts et je dégageAide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Re-bonjour,
c'est difficile de juger de l'agressivité de quelqu'un sur un forum... Je ne suis pas sur que Gerard était agressif... (mais d'un autre coté j'en sais rien)
De plus, je ne suis absolument pas un expert (et justement les conventions du domaine sont très floues à mon sens)...
Tu as bien compris : on peut définir le langage par
V1={a,b} (le vocab)
et tous les mots de L1 : {a, b}*
C'est ce que j'écris avec la règle Si X,Y dans L1 Alors XY dans L1 (concaténation) : en incluant dans les mots initiaux 'a' et 'b' (faut bien démarrer sur quelque chose).
Voila... Si tu as des conseils, pointeurs, références, idées etc, je n'attends que ça :-) -
Bonsoir Nicola
Effectivement ton langage $L_1$ est formé de tous les mots constitués avec les 2 lettres $a, b$. On s'en convainc par récurrence.
Par contre ton langage $L_2$ est formé de mots constitués des lettres $a,b$ en quantité $1 \pmod 3$.
Cela se montre par récurrence sur le nombre $k$ d'itération de la règle $aXXY$ :
$k=0 : L_2$ contient $a, b$ de longueur $1\pmod 3$
Supposons que après au plus $k$ itérations de la règle, les mots obtenus sont tous de longueurs $1 \pmod 3$, alors en en choisissant deux : $X, Y$ la longueur de $aXXY$ sera $1 + 1\pmod 3+1\pmod 3+1\pmod 3 = 1\pmod 3$ Donc par récurrence ...
On peut même essayer de dénombrer les mots construits avec cette règle :
A l'étape 0, on a $n_0=2$ mots ($a, b$)
A l'étape 1, c'est à dire après avoir appliqué 1 fois la règle $aXXY$, on a en plus : $aaaa, abba, aaab, abbb$ soit $u_0^2$ ($u_0$ choix pour $X$ et $u_0$ pour $Y$). Cela fait donc $2+2^2=6$ éléments construits.
En supposant $u_k$ éléments obtenus après au plus $k$ itérations,
$u_{k+1}= u_k^2 + u_k$ (après avoir vérifié que les $u_k^2$ ajoutés sont bien différents entre eux et différents de ceux déjà obtenus).
Le nombre d'éléments obtenus après $n$ applications de la règle est donnée par la suite récurrente : $u_{n+1}=u_n(u_n+1)$.
A suivre ...
Alain -
Bonjour CC et AD.
J'ai peut-être été violent avec CC, mais je ne comprends toujours pas ... pourquoi CC ne comprend pas : Le langage L2 est formé des mots construits avec les lettres a et b, d'une certaine façon. Donc c'est une partie du langage L1 qui contient tous les mots formés avec a et b. C'est une évidence dans le post initial.
Evidemment, il faut avoir rencontré le vocabulaire de la liguistique (ou de l'informatique) pour être familier de ce type de présentation (mais je l'ai seulement rencontré, et ça suffit). Donc je prends acte que CC ne connaissait rien à ce sujet. Et je considère ma réaction (motivée par les interventions habituelles de CC) comme anormale, je l'en prie de m'excuser (et vous aussi).
En tout cas, AD, tu as mathématisé l'idée, est-ce qu'elle donne quelque chose en termes de limite de fréquence ?
Cordialement -
Bonjour,
Effectivement l'idée de AD est intéressante mais je n'ai pas le temps de bien l'étudier (dans le cas général)... En ce moment je suis assez pris...
Ce que je souhaiterais faire c'est reprendre le même principe mais au lieu de la présenter sous forme de suite $u_n$ avec $n$ la $n^{\grave eme}$ itération, j'aimerais trouver une suite $u_n$ qui dénombre le nombre de mots de taille $n$.
Les mots du langage $L_1=\{a,b\}^*$ seraient dénombrés par $v_n$ ; et $u_n$ dénombrerait les mots du langage $L_2$ inclus dans $L_1$.
Ainsi je pourrais poser que la proportion $p_n$ des mots de taille $n$ de $L_2$ par rapport à $L_1$ est $p_n=u_n/v_n$...
La limite $p = \lim\limits_{n\to\infty} (p_1 + p_2 + \ldots + p_n)$ serait la mesure que je cherche (c'est à dire la proportion totale des mots de $L_2$ par rapport à ceux de $L_1$), à condition que ça converge bien entendu...
La limite d'une telle somme ne converge pas forcément si $p_n$ converge vers l'infini, non ? Cette limite est plutôt difficile à établir dans le cas général je pense non ? (par contre il est possible qu'on puisse facilement déterminer si elle existe dans le cas étudié ici)
Et au sujet de la démarche ? (plutôt correct ou naïf ?)
[La case LaTeX
AD] -
Salut Nicola.
C'est plus simple que ça.
D'abord l'idée d'additionner des proportions est à proscrire. Ajouter des pourcentages, ça n'a de sens que si c'est des pourcentages d'une même population (30 \% des français + 15\% des chiens ça fait quoi ?).
Le calcul que tu peux faire est de chercher la proportion $p_n$ des mots d'au-plus $n$ lettres de $L_2$ qui sont dans $L_1$, et de voir si $p_n$ tend vers une limite (c'est un nombre compris entre 0 et 1, mais il pourrait varier dans se rapprocher d'aucune limite).
$p_n = \dfrac{u_1 + u_2 + \ldots + u_n}{v_1 + v_2 + \ldots + v_n}$ donne la probabilité pour qu'un mot d'au plus $n$ lettres de $L_1$ soit aussi dans $L_2$. Sa limite est l'idée intuitive de la probabilité pour qu'un mot de $L_1$ soit aussi dans $L_2$. Si la limite existe.
Cordialement. -
Ah oui effectivement c'est pas bon ...
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 27
+20 Invités