Usuario:Escaldon/Simplificación de gramáticas

En informática y concretamente en teoría de lenguajes, la simplificación de gramáticas es un método mediante el cual, partiendo de una gramática G se puede encontrar otra equivalente G' que consideremos mejor para nuestro propósito final. En una gramática independiente del contexto (GIC) no existen limitaciones a lo que se encuentra en la parte derecha de las producciones. Esta libertad puede ser considerada improductiva en el caso de que existan producciones que dificulten la comprensión de la gramática. Por ello, se emplean restricciones, simplificaciones y métodos para transformar una gramática cualquiera en otra equivalente que cumpla unas características deseables. Por todo lo previamente explicado existen los algoritmos de simplificación de gramáticas y a las formas normales de las GIC, siendo las más utilizadas la forma normal de Chomsky y la forma normal de Greibach.

Para la simplificación de gramáticas se utilizan los siguientes tres algoritmos: eliminación de símbolos y producciones vacías, eliminación de producciones unitarias y eliminación de símbolos inútiles. Debido a que el algoritmo de eliminación de producciones unitarias puede introducir en la gramática símbolos inútiles, para simplificar completamente una gramática, seguiríamos los siguientes pasos:

1. Eliminar símbolos y producciones vacías
2. Eliminar producciones unitarias
3. Eliminar símbolos inútiles

Una aplicación preliminar del último algoritmo puede mejorar la eficiencia del proceso, con lo cual aplicaríamos:

1. Eliminar símbolos inútiles
2. Eliminar símbolos y producciones vacías
3. Eliminar producciones unitarias
4. Eliminar símbolos inútiles

Algoritmos

Usuario:TooloTF/Eliminación de símbolos inútiles
Usuario:Escaldon/Eliminación de producciones unitarias
Usuario:Escaldon/Eliminación de producciones vacías

Referencias

• Kelley, Dean (1995). Teoría de Autómatas y Lenguajes Formales. Prentice Hall. ISBN 0-13-518705-2.