在目錄中解釋 1 型文法

喬姆斯基等級代表了不同機器接受的語言類別。

喬姆斯基等級

根據喬姆斯基的文法等級如下所示：

0 型：無限制文法

   圖靈機 (TM)

1 型：上下文有關文法

   線性界限自動機 (LBA)

2 型：上下文無關文法

   下推自動機 (PDA)

3 型：正則文法

   有限自動機 (FA)

1 型上下文有關文法 (CSG)

• 1 型文法也稱為上下文有關文法
• 上下文有關文法用於表示上下文有關語言

CSG遵循以下規則：

• 上下文有關文法在其產生式規則的左側可能有多個符號。
• 左側符號的數量不得超過右側符號的數量。
• 不允許A->ε形式的規則，除非A是起始符號。它不會出現在任何規則的右側。
• 1 型文法必須是 0 型文法。
• 在 1 型產生式中，應採用 V->T 的形式。
• V 中的符號計數小於或等於 T。

示例

S->AB

AB->abc

B->b

Bhanu Priya

更新於：2021年6月16日

4K+ 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習