Forme normale de Chomsky

Pour cela, on introduit un nouveau symbole ${\displaystyle S_{0}}$ qui devient l'axiome, et la règle

${\displaystyle S_{0}\to S}$,

où ${\displaystyle S}$ est l’ancien axiome. Ceci ne modifie pas le langage engendré, et la variable ${\displaystyle S_{0}}$ ne figure pas dans un membre droit de règle.

Si une lettre terminale ${\displaystyle a}$ figure dans un membre droit de règle de longueur au moins 2, on la remplace par une nouvelle ${\displaystyle N_{a}}$ et on ajoute la nouvelle règle

${\displaystyle N_{a}\to a}$

et on remplace la règle ci-dessus par

${\displaystyle X\to WN_{a}T}$

En fait, on fait ce remplacement simultanément pour toutes les occurrences de lettres terminales dans les membres droits de règles. Cela ne modifie pas le langage engendré, et augmente le nombre de règles d'au plus le nombre de lettres terminales. L'opération est donc linéaire en fonction de |G|.

On remplace une règle

${\displaystyle X\to Y_{1}Y_{2}\cdots Y_{n}}$,

par les règles

${\displaystyle X\to Y_{1}Z_{1},\ Z_{1}\to Y_{2}Z_{2},\ldots ,\ Z_{n-2}\to Y_{n-1}Y_{n}}$,

où les ${\displaystyle Z_{i}}$ sont des nouveaux symboles non terminaux[14]^,[15]. Cette opération au plus triple la taille de la grammaire.

Une ε-règle est une règle de la forme

${\displaystyle X\to \varepsilon }$,

où ${\displaystyle X}$ n'est pas l’axiome de la grammaire. On commence par déterminer les variables qui dérivent en ε ; ces variables, appelées annulables (« nullable » en anglais), se calculent par récurrence : X est annulable s'il existe une règle

${\displaystyle X\to Y_{1}\cdots Y_{n}}$ telle que ${\displaystyle Y_{1},\ldots ,Y_{n}}$ sont tous annulables.

Pour toute variable ${\displaystyle X}$, annulable ou non, toute règle

${\displaystyle X\to Y_{1}\cdots Y_{n}}$

est remplacée par toutes les règles obtenues en supprimant une ou plusieurs, voire toutes les variables annulables dans le membre droit de règle, puis on supprime toutes les ε-règles (à l'exception de celle de l'axiome si elle est présente)[16].

Par exemple, dans la grammaire suivante avec axiome S₀,

S₀ → AbB | C

B → AA | AC

C → b | c

A → a | ε

La variable A, et par conséquent B, sont annulables, et ni C ni S₀ ne le sont. Dans la version intermédiaire suivante, on a coloré les variables à supprimer :

S₀ → AbB | AbB | AbB | AbB | C

B → AA | AA| AA | AεA | AC | AC

C → b | c

A → a | ε

Après suppression des variables en jaune, et des règles A → ε (d'origine) et B → ε (produite), on obtient la grammaire

S₀ → AbB | Ab | bB | b | C

B → AA | A | AC | C

C → b | c

A → a

Cette grammaire engendre le même langage, sans ε-règles.

Une règle unité est une règle de la forme

${\displaystyle X\to Y}$

où ${\displaystyle X}$ et ${\displaystyle Y}$ sont des variables, et plus généralement une règle

${\displaystyle X\to WYT}$,

où toutes les variable de ${\displaystyle WT}$ sont annulables. Pour éliminer ce type de règles, on la remplace par la règle

${\displaystyle X\to \alpha }$

pour chaque règle

${\displaystyle Y\to \alpha }$

sauf si c'est une règle unité précédemment enlevée[17]. Cette technique est complétée dans le cas de cycles (comme l'existence de trois règles ${\displaystyle X\to Y,Y\to Z,Z\to X}$) par l'identification des variables d'un cycle : elles sont toutes remplacées par l'une d'entre elles. La transformation UNIT peut faire passer la taille de la grammaire de |G| à |G|².

L'ordre dans lequel les opérations sont appliquées est important pour deux raisons : d'abord, il est possible qu'une transformation puisse annuler l'effet d'une opération précédente ; par exemple, si on utilise START après UNIT, on réintroduit une règle unité. Sur la table, les ordres convenables sont indiqués.

Une autre raison pour choisir l'ordre des opérations avec soin est l'augmentation possible de la taille de la grammaire, et par là même la complexité des opérations. La taille de la grammaire résultat peut aller de |G|² to 2^2|G| pour une grammaire de taille |G|[18]. L'augmentation dépend de l'ordre entre DEL et BIN. Il peut être exponentiel si DEL est opéré en premier, puisqu'une règle dont le membre droit est de longueur n peut produire 2²ⁿ règles, et sinon est linéaire. UNIT peut provoquer une augmentation quadratique de la taille[4].

La plus petite augmentation de taille se produit pour les ordres (START,TERM,BIN,DEL,UNIT) et (START,BIN,DEL,UNIT,TERM).

Les divers manuels et cours de théorie des langages contiennent en général, en plus de l'exposé des procédures, des démonstrations de la correction des algorithmes. Une formalisation de ces opérations de réduction, à savoir la suppression de variables inutiles, l’élimination des règles unité et des epsilon-règles dans l’assistant de preuve Coq a été entreprise par Marcus V. M. Ramos et Ruy J. G. B. de Queiroz[19]. Dans ce formalisme, Coq prouve que les opérations sont correctes en ce sens qu’ils préservent le langage engendré par la grammaire.