Forme normale de Chomsky

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

  1.  ;
  2. ou  ;
  3. ou

sont des symboles non terminaux, est un symbole terminal, est l'axiome de la grammaire, et 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.

Historique

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 dans un article publié en 1959 [1].

Dans d'autres langues