喬姆斯基範式

喬姆斯基範式是由喬姆斯基提出的數學關係式。

基本介紹

• 中文名：喬姆斯基範式
• 表達式：A→BC
• 提出者：喬姆斯基
• 提出時間：1959年
• 套用學科：計算機科學
• 適用領域範圍：IT行業
• 適用領域範圍：Chomsky 範式

套用舉例

在計算機科學中，一個形式文法是Chomsky 範式的，若且唯若所有產生規則都有如下形式：

• A→BC或
• A→ α 或
• S→ ε

這裡的A,B和C是非終結符，α 是終結符（表示常量值的符號），S是開始符號，而 ε 是空串。還有，B和C都不可以是開始符號。

所有的 Chomsky 範式的文法都是上下文無關，反過來，所有上下文無關文法都可以有效的變換成等價的 Chomsky 範式的文法。

除了（在文法可能生成空串的時候包括的）可選規則S→ ε 是例外，Chomsky 範式的文法的所有規則都是擴張的，就是說在字元串的整個導出過程中，每個終結符和非終結符的字元串比起前面導出的字元串要么同樣長度要么多出一個元素。長度 n 的字元串的導出總是精確的 2n-1 步長。

證明：

1）長度為n個字元串需要n次A→ α 的派生，因此需要n個語法變元；

2）n個變元需要n-1次A→BC的派生（從S開始，每次派生增加1個變元，增加n-1次）；

3）由1），2），長度為n且滿足喬姆斯基範式語法的字元串恰好需要2n-1次派生。

進一步的，因為導出非終結符的所有規則都把一個非終結符變換成兩個非終結符，基於 Chomsky 範式的文法上的一個分析樹是二叉樹，而這個樹的高度被限制於最高為這個字元串的長度。

由於這些性質，在語言和可計算性領域中很多證明採用了 Chomsky 範式。這些性質還產生了基於 Chomsky 範式的文法的各種有效算法；例如，判定給定字元串是否可以被使用 Chomsky 範式的給定文法生成的CYK算法。

Chomsky 範式得名於諾姆·喬姆斯基，他是發明喬姆斯基層級的美國語言學家。

定義

某些來源以稍微不同的方式來定義 Chomsky 範式：

一個形式文法是Chomsky 範式的，若且唯若所有產生規則都有如下形式：

• A→BC或
• A→ α

這裡的A,B和C是非終結符，而 α 是終結符。當使用這個定義的時候，B和C不能是開始符號。

這個定義不同於前面定義的是它排除了文法生成空串 ε 的可能性。接受一個語言L的任何上下文無關文法都可以有效的變換成接受L - {ε}的 Chomsky 範式的文法。後者定義的首要好處是證明通常更簡單，由於在導出過程中每個步驟都永不減少結果字元串的長度。當然它的缺點是在最初文法生成 ε 就需要特殊考慮。

證明

1. 長度為n個字元串需要n次A→ α 的派生，因此需要n個語法變元；
2. n個變元需要n-1次A→BC的派生（從S開始，每次派生增加1個變元，增加n-1次）；
3. 由1.、2.得知，長度為n且滿足喬姆斯基範式語法的字元串恰好需要2n-1次派生。

進一步的，因為導出非終結符的所有規則都把一個非終結符變換成兩個非終結符，基於 Chomsky 範式的文法上的一個分析樹是二叉樹，而這個樹的高度被限制於最高為這個字元串的長度。

由於這些性質，在語言和可計算性領域中很多證明採用了 Chomsky 範式。這些性質還產生了基於 Chomsky 範式的文法的各種有效算法；例如，判定給定字元串是否可以被使用 Chomsky 範式的給定文法生成的CYK算法。