Forma normal de Chomsky

En la informàtica, una gramàtica lliure de context és aquella que està en la forma normal de Chomsky si totes les seves regles són de la forma:

on és qualsevol símbol terminal i A, B i C són variables, B i C no poden ser la variable inicial. També es permet la regla:

on S és la variable inicial i la paraula buida (també pot estar representada per λ).

Vegeu també

Altres idiomes