Siguiente: Supresión de símbolos inútiles Un nivel arriba: Lenguajes libres de contexto Anterior: Arboles y gramáticas

Transformaciones equivalentes de gramáticas

Recordamos que una gramática formal G=(V,T,P,S), donde V es el conjunto de símbolos variables, T es el conjunto de símbolos terminales, P es el conjunto de producciones y S es el símbolo inicial, se dice ser libre de contexto si sus producciones son de la forma $X\rightarrow \sigma$, con $X\in V$ y $\sigma\in (V+T)^*$. Veremos en esta sección que toda gramática libre de contexto puede ser convertida, algorítmicamente, a gramáticas equivalentes que no poseen variables que no se utilicen o que no contengan produccciones con consecuente vacío o cuyas producciones sean una mera sustitución de variables. A lo largo de esta sección, G=(V,T,P,S) denotará siempre una gramática libre de contexto.