在目录中解释 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 千次以上浏览

开启你的 职业生涯

完成课程并获得认证

入门