在目錄中解釋 0 型文法

喬姆斯基層級表示可被不同機器接受的語言的類別。

喬姆斯基層級

喬姆斯基將文法層級按文法型別解釋如下 −

0 型。不受限文法

   圖靈機 (TM)

1 型。上下文相關文法

   線性有界自動機 (LBA)

2 型。上下文無關文法

   下推自動機 (PDA)

3 型。正則文法

   有限自動機 (FA)

0 型不受限文法

• 0 型文法生成遞迴可列舉資訊。
• 在 0 型中，生成沒有限制。
• 可能存在包括所有形式文法的任意短語結構文法
• 它們生成能被圖靈機識別的語言。
• 生成可以透過形如 a->b 的形式出現，其中 a 是一個終結符串，並且至少有一個非終結符，且 a 不能為 null。b 是終結符和非終結符串。

示例

S->ACaB

Bc->acB

CB->DB

aD->Db

Bhanu Priya

更新於: 16-6 月-2021

10 千次以上瀏覽

開啟你的 職業生涯

完成課程並獲得認證

入門