Diseño y elaboración de software de aplicación a la normalización de gramáticas libres del contexto

Abstract

A lo largo del presente trabajo se describe la teoría pertinente relativa a lenguajes y gramáticas formales enfatizando en las gramáticas independientes del contexto, y las formas normales de gramáticas. Las gramáticas independientes del contexto son un tipo de gramáticas formales en donde cada regla de producción está compuesta siempre por un único símbolo no terminal en el lado izquierdo y por una cantidad finita de símbolos, terminales o no terminales, en el lado derecho. La forma normal de Chomsky para gramáticas independientes del contexto tiene la particularidad de que el lado derecho de toda producción contiene o bien solo dos símbolos no terminales o bien un único símbolo terminal; la ventaja de tener una determinada gramática independiente de contexto en la forma normal de Chomsky es facilitar el estudio de sus propiedades, ya que es posible transformarla a un árbol binario. Un árbol binario se caracteriza por que cada nodo tiene solamente dos hijos, uno izquierdo y otro derecho. Este tipo de estructura permite que la búsqueda de datos almacenados sea mucho más rápida y eficiente. Toda gramática independiente de contexto es reducible a esta forma normal, mediante algunas simplificaciones, específicamente son cinco algoritmos para esta transformación. El análisis de los algoritmos de reducción ha sido ampliamente desarrollado por Noam Chomsky y está discutido extensamente en los principales textos que abarcan el tema de Teoría de Lenguajes Formales. El objetivo del presente trabajo es automatizar estos pasos mediante el diseño y elaboración de software de aplicación de estos algoritmos en un entorno de programación especifico, lo cual permitirá al usuario poder trabajar con la gramática en su forma reducida. El presente trabajo se limita al diseño y elaboración de software de aplicación a la normalización de gramáticas independientes del contexto. El ámbito del presente trabajo es académico y es útil para los cursos de pregrado y postgrado en Ciencias de la Computación relacionados con Teoría de Autómatas Finitos y Lenguajes Formales.