Forme Normale de Chomsky
Un article de Wikipédia, l'encyclopédie libre.
En informatique, une grammaire formelle est en forme normale de Chomsky si et seulement si toutes ses règles de production sont de la forme :
- A → BC ou
- A → α ou
- S → ε
où A, B et C sont des symboles non-terminaux, α est un symbole terminal (représentant une valeur constante), S est l'axiome de la grammaire, et ε est le mot vide, tels que l'axiome n'apparaît jamais dans le membre droit d'une règle (autrement dit, ni B ni C ne peuvent être S).
Toute grammaire écrite en forme normale de Chomsky est une grammaire hors-contexte. Inversement, toute grammaire hors-contexte peut être transformée en une grammaire équivalente en forme normale de Chomsky.
A l'exception de la règle optionnelle S → ε (incluse si la grammaire peut générer le mot vide), toutes les règles d'une grammaire sous forme normale de Chomsky sont extensibles; par conséquent, tout au long de la suite de dérivations, chaque chaîne de terminaux et non-terminaux est toujours de la même longueur ou plus longue d'un élément seulement que la chaîne de l'étape précédente. La dérivation d'une chaîne de longueur n se fait donc toujours au plus en 2n-1 étapes. 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 Chosmky est un arbre binaire, 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 utilisent la forme normale de Chomsky. Plusieurs algorithmes efficaces tirent également profit de ces propriétés, comme par exemple l'algorithme CYK, permettant de décider si une chaîne de caractères peut être générée par une grammaire mise en forme normale de Chomsky.
La forme normale de Chomsky tient son nom du linguiste américain Noam Chomsky, également inventeur de la Hiérarchie de Chomsky.
