forme normale chomsky

Question

Pourquoi convertissons-nous la grammaire en forme normale de Chomsky? Y a-t-il un avantage?

Answer 1

Par exemple, la grammaire dans le CNF (ou plutôt son arbre de dérivation) est utilisée pour prouver le pompage du lemme pour les langues sans contexte.

Answer 2

D'une part, vous pouvez utiliser l'algorithme cyk sur les grammaires de forme normale de Chomsky

Answer 3

La forme normale de Chomsky permet à un algorithme de temps polynomial de décider si une chaîne peut être générée par une grammaire. L'algorithme est assez lisse si vous connaissez la programmation dynamique ...

Si la longueur de votre entrée (i) est n, vous prenez un tableau 2D (a) de DIM NXN.

A [i, j] désigne tous les symboles de la grammaire G qui peuvent dériver le sous-chaîne I (i, j).

Ainsi, si un [1, n] contient le (s) symbole (s), cela signifie que la chaîne que je peux être dérivée par S, ce que nous voulions vérifier.

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.

Je sais que les index semblent assez fous. Mais en gros, voici ce qui se passe.

-Le boîtier de base est assez clair je pense

-Dans l'étape inductive, nous construisons la solution pour une sous-chaîne de longueur de toutes les solutions avec une longueur inférieure à S.

-Say vous trouvez la solution pour la longueur 5 sous-chaîne (sub) à partir de l'index 1. Ensuite, vous démarrez une boucle (autre chose d'autre) ..... qui vérifie s'il y a une règle (a-> bc) telle que B et C dérivent deux sous-chaînes contiguës et disjointes de Sub et si oui Ajoutez tous ces A à n [1,6].

-La finalement si vous avez le symbole de démarrage en n [1, n] alors vous acceptez!