Forme normale de Chomsky

Cet article est orphelin. Il a peu ou aucun article lié à lui. (septembre 2011) Aidez à ajouter des liens dans les articles relatifs au sujet.

En informatique théorique, et notamment en théorie des langages, une grammaire algébrique est en forme normale de Chomsky si et seulement si toutes ses règles de production sont de la forme :

1. $X\to YZ$ ou
2. $X\to a$ ou
3. $S\to\varepsilon$

où $X, Y, Z$ sont des symboles non terminaux, $a$ est un symbole terminal, $S$ est l'axiome de la grammaire, et $\varepsilon$ est le mot vide.

Si la dernière règle est présente, il est demandé que l'axiome n'apparaisse jamais dans le membre droit d'une règle.

Toute grammaire écrite en forme normale de Chomsky est une grammaire algébrique. Inversement, toute grammaire algébrique peut être transformée en une grammaire équivalente (c'est-à-dire engendrant le même langage) en forme normale de Chomsky.

À l'exception de la règle (3), toutes les règles d'une grammaire sous forme normale de Chomsky sont croissantes; par conséquent, tout au long d'une dérivation, les longueurs des mots croissent. Ils croissent de 1 avec une règle de type (1), et restent de même longueur avec une règle de type (2). La dérivation d'un mot de longueur $n>0$ se fait donc toujours en $2n-1$ étapes: il y a $n-1$ étapes de type (1) et $n$ étapes d type (2). De plus, dans la mesure où toutes les règles de dérivation de non terminaux transforment un non terminal en deux non terminaux, un arbre de dérivation basé sur une grammaire en forme normale de Chomsky est un arbre binaire avec $2n-1$ nœuds internes et $n$ feuilles, et sa hauteur est au maximum la longueur de la chaîne de caractères.

Grâce à ces propriétés, de nombreuses preuves dans le domaine des langages formels deviennent plus simples en utilisant la forme normale de Chomsky (par exemple le fait que l'appartenance d'un mot au langage engendré est décidable). Plusieurs algorithmes généraux d'analyse syntaxique, comme l'algorithme CYK, emploient cette forme normale.

La forme normale de Chomsky tient son nom du linguiste américain Noam Chomsky, qui a conçu également la hiérarchie qui porte son nom, et qui a décrit cette forme normale à cette occasion.

Voir aussi

• Grammaire algébrique
• Grammaire contextuelle
• Forme normale
• Compilation