Forma normale di Chomsky

Question

Perché convertiamo la grammatica in forma normale di Chomsky? C'è un vantaggio?

Answer 1

Ad esempio, la grammatica nel CNF (o meglio il suo albero di derivazione) viene utilizzata per dimostrare il pompaggio del lemma per le lingue senza contesto.

Answer 2

Per prima cosa, puoi usare l'algoritmo cyk su grammatiche normali di chomsky

Answer 3

La forma normale Chomsky consente a un algoritmo del tempo polinomiale di decidere se una stringa può essere generata da una grammatica. L'algoritmo è piuttosto liscio se conosci la programmazione dinamica ...

Se la lunghezza del tuo input (i) è n, prendi un array 2D (a) di dim nxn.

A [i, J] indica tutti i simboli nella grammatica G che può derivare la sotto-corda I (i, j).

Quindi, infine, se un [1, n] contiene i simboli di avvio, significa che la stringa che posso derivare da s che è ciò che volevamo controllare.

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.

So che gli indici sembrano piuttosto pazzi. Ma fondamentalmente ecco cosa sta succedendo.

-La caso di base è abbastanza chiaro, credo

-Na fase induttiva costruiamo la soluzione per una sottostringa di lunghezza da tutte le soluzioni con lunghezza inferiore a s.

-Say stai trovando la soluzione per il substricatura di lunghezza 5 (sub) A partire dall'indice 1. Quindi si avvia un ciclo (qualcos'altro parte) ..... che controlla se esiste una regola (a-> bc) in modo tale che B e C derivano due sottostringhe contigue e disgiunte di sub e in tal caso Aggiungi tutti questi di questi a n [1,6].

-Finalmente se hai il simbolo di avvio in n [1, n], allora accetti!