La Forma Normal de Chomsky (CNF) simplifica las gramáticas libres de contexto (CFG) para que todas las reglas de producción sigan patrones específicos. En la CNF, cada regla produce dos símbolos no terminales, un solo símbolo terminal o, en algunos casos, la cadena vacía. Convertir una CFG a CNF es un paso importante en muchos algoritmos de análisis sintáctico, como el algoritmo CYK, y ayuda a comprender la estructura de los lenguajes. Una gramática libre de contexto (CFG) está en forma normal de Chomsky (CNF) si todas las reglas de producción satisfacen las siguientes condiciones:

Un no terminal que genera un terminal (por ejemplo; X→ x)
Un no terminal que genera dos no terminales (por ejemplo; X→YZ)
Símbolo de inicio generando ε. (p. ej.; S→ ε)

1. Forma Normal de Chomsky (Chomsky Normal Form – CNF):
Una gramática está en CNF si todas las producciones tienen una de las siguientes formas:
A → BC (donde A, B y C son variables, y B y C no son el símbolo inicial)
A → a (donde a es un terminal)
(Opcionalmente) S → ε si ε pertenece al lenguaje
Se usa principalmente en algoritmos como CYK (Cocke–Younger–Kasami).

2. Forma Normal de Greibach (Greibach Normal Form – GNF):
Una gramática está en GNF si todas las reglas son del tipo:
A → aα
donde a es un símbolo terminal y α es una (posiblemente vacía) cadena de variables.
Esta forma es útil para construir autómatas de pila deterministas.

Propiedades clave de CNF:
Un único CFG se puede convertir en diferentes formas CNF equivalentes.
CNF produce el mismo lenguaje que el CFG original.
CNF se utiliza ampliamente en algoritmos de análisis como:
Algoritmo Cocke-Younger-Kasami (CYK) para verificación de membresía.
Analizadores de abajo hacia arriba en compiladores.
Para una cadena de longitud n, una derivación CNF requiere como máximo 2n-1 pasos de derivación.
Cualquier CFG que no genere ε tiene un CNF equivalente.