Grammaires formelles : mesure d'expressivité du langage

[invite3443c7ee]

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 apparait la règle de G2. Ces règles produisent tous les mots à quatres 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 connait-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
-----

[Médiat]

Bonjour,

Je ne connais pas ce domaine, donc je vais très vraisemblablement écrire des âneries ou des évidences, mais la lecture de la phrase « il y a deux fois moins de nombres pairs que de nombres entiers » me choque un peu et je me dis que la théorie de la mesure serait sans doute plus appropriée, en considérant le graphe de chacune des grammaires comme un sous graphe de la grammaire qui génère tous les mots avec comme vocabulaire la réunion des vocabulaires (le monoïde libre à n générateurs, n étant le cardinal du vocabulaire total).

[invite3443c7ee]

merci de ta réponse
Je comprends que la phrase il y a deux fois moins de pairs que d'entiers te choque, puisqu'on peut mettre les premiers en bijection avec les seconds.
Par contre je n'ai pas très bien compris ce que tu proposais... (monoïde ?)

[Médiat]

Le monoïde libre à n générateurs est constitué de l'ensemble des mots possibles avec n générateurs, c'est à dire que toutes les grammaires formelles sur ces générateurs ne peuvent fabriquer que des sous-ensembles de ce monoïde (ou un sous-graphe si on préfère cette vision).

Je me demandais si jeter un coup d'oeil à la catégorie des graphes ne permettrait d'avoir un éclairage intéressant, il me semble que la notion d'inclusion dont tu parles est très proche des morphismes de graphe (mais pas identique, au bénéfice des catégories, à mon humble avis), en éliminant les problèmes liès à des disparités de vocabulaire, par exemple la grammaire libre sur {a} est la même que la grammaire libre sur {b}, et pourtant aucun des mots générés par l'une n'appartient à l'autre.

[A voir en vidéo sur Futura]