在目錄中說明 2 型和 3 型文法？

喬姆斯基層級結構如下所示：

2 型——上下文無關文法 (CFG)

• 2 型文法由上下文無關語言生成。
• 由文法生成的語言由下推自動機識別。
• 2 型必須在 1 型中。
• 產生式的左端只能有一個變數。

• |alpha| =1

  對 beta 沒有限制。

  產生式規則形式如下：

  A->alpha

  其中，A 是任何單個非終結符，是終結符和非終結符的任意組合。

示例

S->AB

A->a

B->b

3 型——正則文法

• 3 型文法由正則語言生成。
• 這些語言正是所有能夠被有限狀態自動機接受的語言。
• 3 型是最受限制的文法。

• 形式為

  V->VT*/T* 或 V->T*V/T*

示例

S->ab

Bhanu Priya

更新於：16-Jun-2021

6K+ 瀏覽量

開啟您的 職業生涯

透過完成課程獲得認證

開始