L'importance des formes normales comme la forme normale de Chomsky pour les CFG

Je comprends que les grammaires sans contexte peuvent être utilisées pour représenter des langues sans contexte, ce qui peut avoir des ambiguïtés. Nous avons également des formes normales comme la forme normale de Chomsky et Greibach . Je ne pouvais pas comprendre le besoin de cela.

Pourquoi sont-ils importants dans la théorie des langues? Tous les manuels auxquels j'ai fait référence parlent de ces formes normales mais ne disent rien de leur importance.

Il existe au moins deux utilisations pertinentes.

1. Simplicité des preuves
   Il existe de nombreuses preuves concernant les grammaires hors contexte, notamment la réductibilité et l'équivalence avec les automates. Ce sont les plus simples, le plus restreint l'ensemble de grammaires auquel vous devez faire face. Par conséquent, les formulaires normaux peuvent y être utiles.

   $\varepsilon$$\varepsilon$

2. Active l'analyse
   Bien que les PDA puissent être utilisés pour analyser des mots avec n'importe quelle grammaire, cela est souvent gênant. Les formulaires normaux peuvent nous donner plus de structure avec laquelle travailler, résultant en des algorithmes d'analyse plus faciles.

   À titre d'exemple concret, l'algorithme CYK utilise la forme normale de Chomsky. La forme normale de Greibach, en revanche, permet une analyse de descente récursive; même si le retour en arrière peut être nécessaire, la complexité de l'espace est linéaire.

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

$I$$n$$A$$n$$n$

$A[i,j]$$G$$I(i,j)$

$A[1,n]$$S$$S$

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.

$\epsilon$