Noam Chomsky est une célébrité dans de nombreux domaines. Certains traducteurs sont surpris quand je leur apprends qu’il est également bien connu du monde des sciences informatiques. Naom Chomsky a en effet a inventé (découvert ?) une classification des langages et des grammaires formels selon leur pouvoir d’expression (ou leur traitement) : la hiérarchie de Chomsky.
Ce schéma a ordonné les grammaires et donc les langages en quatre catégories :
– les langages récursivement énumérables
– les langages contextuels
– les langages hors contexte (ou langages algébriques)
– les langages rationnels (ou réguliers)
Ces différentes classes étant hiérarchiquement imbriquées les unes aux autres.
Pour chacune d’entre elle, il existe un automate qui peut reconnaître les phrases du langage :
– Automate fini (connu également sous le nom de machine à états finis)
– Automate à pile non déterministe
– Automate linéairement borné
– Machine de Turing
Les langues naturelles appartiennent aux catégories de grammaires les plus puissantes et la machine correspondante est la machine de Turing.
Je voudrais maintenant présenter un exemple de langage dit rationnel, soit le plus simple, pour illustrer la correspondance frappante entre les grammaires et les machines. Considérons cette grammaire :
PHRASE -> « la » parenté « est » adjectif
PARENTÉ -> relation « de » personne
RELATION –> « mère » | « père » | « sœur » | « frère » | « fils » | « fille »
PERSONNE -> « Anne » | « David »
ADJECTIF -> « brillant » | « grand »
À partir de là nous pouvons créer des phrases aussi inspirées que « la maman de Anne est brillante » ou « la fille de David est grande ».
L’automate fini reconnaît ces deux phrases, plus 22 autres phrases qui peuvent être construites à partir de ces mots (les écrire est la tâche divertissante du lecteur). Il s’agit d’un nombre d’états unis par des tag fléchées qui représentent les transitions d’un état à un autre. Il y a un état de départ spécifique et un état final également spécifique :
Il est facile de se tromper sur ce point et de croire que « fini » dans un automate fini se réfère au fait de que seul un nombre fini de phrases peuvent être construites ou reconnues par l’automate fini. Mais ce n’est pas le cas. « Fini » se réfère au fait qu’il y a un nombre fini d’états (les cercles, 7 ici). En modifiant légèrement notre grammaire, nous pourrions créer des phrases de longueur arbitraire, y compris sans altérer le nombre d’états.
PHRASE -> « la » PARENTÉ « est » ADJECTIF
PARENTÉ -> RELATION « de » personne
RELATION -> « mère » | « père » | « sœur » | « frère » | « fils » | « fille »
PERSONNE -> « Anne » | « David » | « la » PARENTÉ
ADJECTIF -> « brillant » | « grand »
Nous avons ajouté « la » PARENTÉ comme alternative supplémentaire pour PERSONNE. Dans l’automate fini cela apparaît simplement sous la forme d’une nouvelle flèche qui revient au second état.
Nous pouvons maintenant créer des phrases telles que « le fils de la sœur de la mère de la fille de David est grand ». Je jouais souvent à ce jeu avec mes ex-amis (ils se convertissaient systématiquement en ex-amis dès que je commençais à jouer à ce jeu). Quand je parlais de mon frère par exemple, je me référais à lui comme au fils de la tante de la sœur de mon cousin.
La hiérarchie de Chomsky a été longuement étudiée depuis ces deux domaines. En ce qui concerne les sciences informatiques, elle apporte les bases de la syntaxe pour les langages de programmation, entre autres choses. De nombreux efforts ont été faits en vue de comprendre les structures des langues réelles avec leurs grammaires et leur machines correspondantes, ce à des fins diverses dont la traduction. Les systèmes de traduction basés sur cette approche sont connus comme les systèmes « basés sur des règles ».
Étiquettes : sciences informatiques, grammaires
Version en anglais : https://www.trustedtranslations.com/grammars-where-linguistics-meets-computer-science-2012-04-25.html
Version en espagnol : https://www.trustedtranslations.com/gramaticas-donde-la-linguistica-se-encuentra-con-la-informatica-2012-04-30.html
