喬姆斯基正常形式

Question

爲什麼我們將語法轉換爲喬姆斯基正常形式？有優勢嗎？

Answer 1

例如，語法CNF（或者更確切地說，它的派生樹）被用來證明抽水引理上下文無關語言。

Answer 2

一件事，你可以用Chomsky範式對CYK算法語法

Answer 3

喬姆斯基規範形式使多項式時間算法可以決定一個字符串是否可以由語法生成。 如果您知道動態編程，算法非常光滑...

如果您的輸入（I）的長度是n，那麼您需要一個dim nxn的二維數組（A）。

A [i，j]表示語法G中能夠導出子串I（i，j）的所有符號。因此，如果A [1，n]包含開始符號（S），那麼它意味着字符串I可以由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. 

我知道索引看起來很瘋狂。但基本上這是發生了什麼。

-the基本情況是很清楚，我覺得

-in我們建立了長度s子的解決方案將所有具有長度小於S中的解決方案歸納步。

- 可以找到從索引1開始的長度爲5的子字符串（sub）的解決方案。然後開始一個循環（其他部分）.....它檢查是否存在規則（A-> BC ），使得B和C派生出兩個連續的，不相交的子串，如果這樣，將所有這樣的A加到N [1,6]。

- 最後如果你有在N [1，n]的開始符號，那麼你接受！