Entiendo que las gramáticas libres de contexto pueden usarse para representar lenguajes libres de contexto. Puede tener ambigüedades. También tenemos formas normales como Chomsky y Greibach . No pude entender la necesidad de eso.
¿Por qué son importantes en la teoría de los idiomas? Todos los libros de texto a los que me referí hablan sobre estas formas normales pero no dicen nada sobre su importancia.
formal-languages
context-free
formal-grammars
normal-forms
usuario5507
fuente
fuente
Respuestas:
Hay al menos dos usos relevantes.
Simplicidad de las pruebas
Hay muchas pruebas en torno a las gramáticas libres de contexto, incluida la capacidad de reducción y la equivalencia con los autómatas. Esos son más simples cuanto más restringido es el conjunto de gramáticas con las que tienes que lidiar. Por lo tanto, las formas normales pueden ser útiles allí.
Permite el análisis
Mientras que los PDA pueden usarse para analizar palabras con cualquier gramática, esto a menudo es inconveniente. Las formas normales pueden darnos más estructura para trabajar, lo que resulta en algoritmos de análisis más fáciles.
Como ejemplo concreto, el algoritmo CYK utiliza la forma normal de Chomsky. La forma normal de Greibach, por otro lado, permite el análisis de descenso recursivo; Aunque puede ser necesario retroceder, la complejidad del espacio es lineal.
fuente
La forma normal de Chomsky permite que un algoritmo de tiempo polinómico decida si una cadena puede ser generada por una gramática. El algoritmo es bastante hábil si conoce la programación dinámica ...
Sé que los índices parecen bastante locos. Pero básicamente aquí está lo que está sucediendo.
sub
fuente
fuente