Forma normal de Chomsky

En informàtica, una gramàtica lliure de context G es diu que està en la forma normal de Chomsky si totes les seves regles són de la forma:[1][2]

on és qualsevol símbol terminal (un símbol que representa un valor constant) i A, B i C són símbols no terminals, B i C no poden ser el símbol inicial. També es permet la regla:

on S és la variable inicial i la paraula buida (també pot estar representada per λ), aquesta última regla només pot aparèixer si és a L(G), és a dir, el llenguatge produït per la gramàtica lliure del context G.

Tota gramàtica en forma normal de Chomsky és lliure del context, i per contra, tota gramàtica lliure del context es pot transformar en una equivalent en forma normal de Chomsky i té una mida menor al quadrat de la mida de la gramàtica original.

Altres idiomes