CNF significa forma normal de Chomsky. Una CFG (gramática libre de contexto) está en CNF (forma normal de Chomsky) si todas las reglas de producción satisfacen una de las siguientes condiciones:

• Símbolo de inicio que genera ε. Por ejemplo, A → ε.
• Un no terminal que genera dos no terminales. Por ejemplo, S → AB.
• Un no terminal que genera un terminal. Por ejemplo, S → a.

Por ejemplo:

 G1 = {S → AB, S → c, A → a, B → b} G2 = {S → aA, A → a, B → c} 

Las reglas de producción de la Gramática G1 satisfacen las reglas especificadas para CNF, por lo que la gramática G1 está en CNF. Sin embargo, la regla de producción de Gramática G2 no satisface las reglas especificadas para CNF ya que S → aZ contiene terminal seguido de no terminal. Entonces la gramática G2 no está en CNF.

centrar imágenes en css

Pasos para convertir CFG en CNF

Paso 1: Eliminar el símbolo de inicio del lado derecho. Si el símbolo inicial T está en el lado derecho de cualquier producción, cree una nueva producción como:

 S1 → S 

Donde S1 es el nuevo símbolo de inicio.

Paso 2: En la gramática, eliminar las producciones nulas, unitarias e inútiles. Puede consultar la Simplificación de CFG.

Paso 3: Eliminar terminales del RHS de la producción si existen con otros no terminales o terminales. Por ejemplo, la producción S → aA se puede descomponer como:

 S → RA R → a 

Etapa 4: Eliminar RHS con más de dos no terminales. Por ejemplo, S → ASB se puede descomponer como:

número aleatorio en java

 S → RS R → AS 

Ejemplo:

Convierta el CFG dado a CNF. Considere la gramática dada G1:

 S → a | aA | B A → aBB | ε B → Aa | b 

Solución:

Paso 1: Crearemos una nueva producción S1 → S, ya que aparece el símbolo de inicio S en el lado derecho. La gramática será:

 S1 → S S → a | aA | B A → aBB | ε B → Aa | b 

Paso 2: Como la gramática G1 contiene producción nula A → ε, su eliminación de la gramática produce:

objeto de matriz en java

 S1 → S S → a | aA | B A → aBB B → Aa | b | a 

Ahora, como la gramática G1 contiene producción unitaria S → B, su eliminación produce:

 S1 → S S → a | aA | Aa | b A → aBB B → Aa | b | a 

También elimine la producción unitaria S1 → S, su eliminación de la gramática produce:

ordenar una matriz en java

 S0 → a | aA | Aa | b S → a | aA | Aa | b A → aBB B → Aa | b | a 

Paso 3: En la regla de producción S0 → aA | Aa, S → aA | Aa, A → aBB y B → Aa, el terminal a existe en el lado derecho sin terminales. Entonces reemplazaremos la terminal a con X:

 S0 → a | XA | AX | b S → a | XA | AX | b A → XBB B → AX | b | a X → a 

Etapa 4: En la regla de producción A → XBB, RHS tiene más de dos símbolos, eliminándolo del rendimiento gramatical:

 S0 → a | XA | AX | b S → a | XA | AX | b A → RB B → AX | b | a X → a R → XB 

Por tanto, para la gramática dada, este es el CNF requerido.