Forma Normal de Greibach (FNG)

Vista previa del material en texto

Forma Normal de Greibach 
(FNG) 
 Una GLC está en FNG si 
 La variable inicial no es recursiva 
 G no tiene variables inútiles. 
 G no tiene producciones ɛ (excepto posiblemente 
S →ɛ ). 
 Todas las producciones son de la forma: A →a ó 
A →aB1B2…Bk donde Bi son variables. 
 
Lema 4.11.3 
 En una GLC cualquiera, una producción A → 
uBv se puede reemplazar por 
 A →uw1v | u w2v |… | uwnv. 
 
 Siendo B →w1 | w2 | … | wn todas las 
producciones de B. 
 
Ejemplo 
 Encontrar una gramática en FNG equivalente a la siguiente 
gramática (en FNC): 
Ejercicio 
 Encontrar una gramática en FNG equivalente a la siguiente 
gramática (en FNC): 
 
 
Ejercicio 
 Encontrar una gramática en FNG equivalente a la siguiente 
gramática (en FNC): 
 
 
Ejercicios 
 Encontrar la GLC en FNG equivalente: