La importancia de las formas normales como la forma normal de Chomsky para los CFG

12

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.

usuario5507
fuente
2
Las formas normales son útiles cuando se dan pruebas constructivas.
Karolis Juodelė

Respuestas:

12

Hay al menos dos usos relevantes.

  1. 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í.

    εε

  2. 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.

Rafael
fuente
5

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 ...

InAnn

A[i,j]GI(i,j)

A[1,n]SS

def decide (string s,grammar G):
    //base case
    for i=1 to n:
        N[i,i]=I[i]    //as the substring of length one can be generated by only a
                       terminal.
    //end base case

    //induction
    for s=1 to n:       //length of substring
        for i=1 to n-s-1: //start index of substring
            for j=i to i+s-1:   //something else
                 if there exists a rule A->BC such that B belongs to N[i,j] and C
                 belongs to N[j+1,i+s-1] then add A to N[i,i+s-1]
    //endInduction

    if S belongs to N[1,n] then accept else reject.

Sé que los índices parecen bastante locos. Pero básicamente aquí está lo que está sucediendo.

  • El caso base es bastante claro, creo.

  • ss

  • 5sub1A>BCBCAN[1,6]

  • N[1,n]

  • ishan3243
    fuente
    3
    Este es el algoritmo CYK que a) debe nombrar como tal yb) ha sido mencionado en mi respuesta. Tenga en cuenta que el tiempo de ejecución polinomial solo es impresionante porque el algoritmo es uniforme en todos los CFG, es decir, es general.
    Raphael
    @Raphael ok ... no sabía el nombre :)
    ishan3243
    4

    ϵ

    Dominik D. Freydenberger
    fuente