T031438
T032069
Forma normal de Chomsky
Una gramática de libre contexto está en su forma normal de Chomsky si cada regla es de la forma
A → BC
A → α
Donde α es cualquier terminal y A, B y C son variables (donde B y C no pueden ser la variable inicial).
Además, solo se permite la regla S → ε cuando S es la variable inicial.
A → BC
A → α
Donde α es cualquier terminal y A, B y C son variables (donde B y C no pueden ser la variable inicial).
Además, solo se permite la regla S → ε cuando S es la variable inicial.
Paso 1
Variable inicial.
Se agrega una nueva variable inicial S0 y la regla S0 → S, donde S es la variable inicial original.
Pequeño quiz:
¿S0 debe producir la variable inicial original?
Paso 2
Remover cadenas vacías.
Se remueve una regla de cadena vacía, donde A → ε donde A no es la variable inicial. Después para ocurrencia de la variable A del lado derecho de una regla, se agrega una nueva regla con la ocurrencia borrada.
Si R → uAw, agregamos R → uw.
Si R → uAw, agregamos R → uw.
Pequeño quiz:
Una vez removida la ocurrencia de la variable que produce la cadena vacía, ¿qué hay que hacer?
Paso 3
Remover reglas unitarias.
Se remueve una regla A → B cuando aparezca una regla B → u y se arregla A → u.
Pequeño quiz:
Elige un ejemplo de regla unitaria:
Paso 4
Transformar reglas con tres o más elementos
Reemplazar cada regla del tipo A → U1 U2 U3…Uk, k >= 3 con las reglas A1 → U1 A2, A2 → U2 A3, A(k-2) → U(k-1)Ak.
Pequeño quiz:
Si A → BCD, y se sustituye por la regla A → BE, ¿Qué debe producir E?
Paso 5
Remover terminales juntas con variables.
Cambiar cada terminal α por A y agregamos la regla A → α.