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 : ou ; ou où 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. 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. Une variante de la définition consiste à ne pas permettre le mot vide : seules des règles de la forme ou , sont permises où , et sont des symboles non terminaux et est un symbole terminal. C'est la définition adoptée par exemple par Carton ou Hopcroft et. al. . Bien entendu, ces grammaires n'engendrent pas le mot vide. Une autre variante demande que les membres droits de règles soient de longueur au plus 2, mais n'impose pas que les membres droits de longueur 2 soient formés exclusivement de symboles non terminaux. Un telle grammaire est appelé 2-forme normale ou « 2NF ». Toute grammaire écrite en forme normale de Chomsky est une grammaire non contextuelle. Inversement, toute grammaire hors contexte 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 se fait donc toujours en étapes : il y a étapes de type (1) et étapes de type (2).