Estudio estadístico del número de reglas resultantes al transformar una gramática libre de contexto a la forma normal de Chomsky

Statistical study of the number of resulting rules when transforming a context-free grammar to Chomsky normal form

Es un hecho conocido que toda gramática libre de contexto puede ser transformada a la forma normal de Chomsky de talforma que los lenguajes generados por las dos gramáticas son equivalentes. Una gramática en forma normal de Chomsky(FNC) tiene algunas ventajas, por ejemplo sus árboles de derivación son binarios, la forma de sus reglas más simplesetc. Por eso es siempre deseable poder trabajar con una gramática en FNC en las aplicaciones que lo requieran. Existeun algoritmo que permite transformar una gramática libre de contexto a una en FNC; sin embargo, la cantidad de reglasgeneradas al hacer la transformación depende del número de reglas en la gramática inicial así como de otras características.En este trabajo se analiza desde el punto de vista experimental y estadístico, la relación existente entre el número de reglasiniciales y el número de reglas que resultan luego de transformar una gramática libre de contexto a la FNC. Esto permiteplanificar la cantidad de recursos computacionales necesarios en caso de tratar con gramáticas de alguna complejidad.

INTRODUCCIÓN

Una gramática libre de contexto (GLC) es un mecanismo para generar eficientemente lenguajes formales [6], los cuales son sistemas matemáticos usados como modelos teóricos de computación que sirven de apoyo a algunos sistemas de reconocimiento de patrones tales como: reconocimiento de la voz, traducción automática [6] y otros. Las gramáticas también han sido de gran utilidad en el diseño de compiladores, lenguajes de programación para computadoras y como modelo sintáctico de lenguajes naturales [6, 7].

Definición 1. Una gramática formal es una 4 - tupla G = (N, Σ, P, S) donde:

• Σ es un alfabeto (denominado conjunto de símbolos terminales).
• ​$x\to a$ es un conjunto finito denominado conjunto de símbolos no terminales, $\Sigma \cap N=\text{Ø}$
  
• P es un conjunto finito de reglas, llamado conjunto de reglas de producción.​​
• S es el símbolo inicial de la gramática, $S\in N$
  

Forma de las reglas. El conjunto finito de producciones o reglas de producción, que representan la definición recursiva de un lenguaje, está formado por expresiones que se escriben en la forma $alpha oeta$ y se leen: "α deriva en β", donde: el lado izquierdo de una producción (antes del símbolo $o$) se denomina cabeza de la producción o antecedente, en este trabajo se usará antecedente y es un elemento de $(varSigma ∪ N )^+$.​