Chomsky Forma normal

Question

¿Por qué convertimos la gramática en forma normal de Chomsky? ¿Hay alguna ventaja?

Answer 1

Por ejemplo, la gramática en CNF (o más bien su árbol de derivación) se usa para probar el lema de bombeo para idiomas sin contexto.

Answer 2

Por un lado, puedes usar el algoritmo CYK en las gramáticas normales de Chomsky

Answer 3

La forma normal de Chomsky permite un algoritmo de tiempo polinomial decidir si una cadena puede ser generada por una gramática. El algoritmo es bastante elegante si conoces la programación dinámica ...

Si la longitud de su entrada (i) es n, entonces toma una matriz 2D (a) de Dim nxn.

A [i, j] denota todos los símbolos en la gramática que pueden derivar la sub-string i (i, j).

Entonces, finalmente, si a [1, n] contiene los símbolos de inicio (s), entonces significa que la cadena puedo ser derivada por s, que es lo que queríamos verificar.

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

-El caso base es bastante claro, creo

-En el paso inductivo construimos la solución para una subcadena de longitud de todas las soluciones con una longitud inferior a s.

-Say está encontrando la solución para la longitud 5 de la subcadena (sub) Comenzando en el índice 1. luego comienza un bucle (algo más) ..... que verifica si hay una regla (a-> bc) tal que B y C derivan dos sustras contiguas y disjuntas de sub y, de ser así, Agregue todos los de este tipo a n [1,6].

-Finalmente, si tienes el símbolo de inicio en n [1, n] ¡entonces acepta!