NooJ: A Linguistic Development Environment



Notes sur le livre


La formalisation des langues

1/ Se procurer le livre

2/ Errata et notes

3/ Exercices


Se procurer le livre

Une note de lecture a été publiée dans la revue TAL, numéro "Varia", volume 56:1.

Pour télécharger la table des matières du livre, son premier chapitre, acheter le livre ou une version e-book, cliquez ici.  


Errata et notes

pp. 178-179 et note 10.

Les langages que l’on peut décrire avec des grammaires non restreintes sont les ensembles récursivement énumérables. L’ensemble des ensembles récursivement énumérables est strictement inclus dans l’ensemble de tous les langages ; autrement dit, il existe des langages qui ne sont pas récursivement énumérables, qu'on ne peut pas décrire avec des grammaires génératives et qu'on ne peut pas traiter avec des machines de Turing.

Un exemple d'un tel langage non-récursivement énumérable est obtenu par diagonalisation :

Soit E l’ensemble des langages récursivement énumérables ; cet ensemble est infini mais dénombrable ; on peut donc numéroter chaque langage L1, L2,... Li de E.

Par ailleurs, chaque langage Li est lui-même dénombrable, et son complément est aussi dénombrable. On peut donc numéroter tous les mots de Li, mais aussi tous les mots qui n'appartiennent pas à Li. Soit mi le i-ème mot qui n'appartient pas à Li.

On construit alors le langage L qui contient tous les mots mi de tous les langages Li de E.

Cet ensemble n’est pas récursivement énumérable ; en effet s’il l’était, alors il appartiendrait à E (puisque E contient tous les langages récursivement énumérables), et on pourrait lui trouver son indice j dans E, soit Lj. Mais alors, on a une contradiction : L contient mj par construction de L, mais en même temps, mj n'appartient pas à Lj par définition de mj.

Bien entendu, aucun langue naturelle n’est définie par rapport à un ensemble infini (!) d'autres langues naturelles ou de langages ; je ne connais pas d'exemple de phénomène linguistique qui justifierait l'intérêt de décrire des ensembles non récursivement énumérables.

pp. 188, 189.

La disjonction est une opération associative, ex. :

rouge | (vert | bleu) =  (rouge | vert) | bleu =  rouge | vert | bleu

La concaténation est une opération associative, ex. :

la (belle table) = (la belle) table = la belle table

La concaténation est distributive par rapport à la disjonction :

le (crayon | stylo) = le crayon | le stylo

(le | un) crayon = le crayon | un crayon

pp. 217, 218.

La grammaire donnée en figure 9.6 n’est pas une grammaire strictement récursive à droite car le noeud auxiliaire Phrase apparaît aussi dans le groupe nominal sujet GN qui se situe à gauche du noeud <V> dans le graphe Phrase. Pour la rendre strictement récursive à droite (et donc pour pouvoir la dérécursiver), il faut distinguer les deux noeuds GN, par ex.  un GN0 pour le groupe nominal sujet qui ne peux pas contenir de Phrase de façon récursive (ce qui est naturel linguistiquement) et un GN1 pour le groupe nominal complément d'objet direct qui lui peut contenir le noeud Phrase :

Grammaire locale de la PhraseGrammaire locale du groupe nominal


Solution aux exercices du livre

Si vous êtes enseignant(e), merci de contacter : max point silberztein arobase univ tiret fcomte point fr pour obtenir les solutions aux exercices données en fin de chapitre.