解释 TOC 中的 Type-0 语法

Chomsky Hierarchy 代表不同机器接受的语言类别。

乔姆斯基等级制度

根据乔姆斯基的语法层次结构在下面根据语法类型进行解释 -

类型 0. 不受限制的语法

   图灵机 (TM)

类型 1. 上下文相关的语法

   线性有界自动机 (LBA)

类型 2. 上下文无关文法

   下推自动机 (PDA)

类型 3. 正则文法

   有限自动机 (FA)

Type-0 无限制语法

• 类型 0 文法生成递归可枚举。

• 在类型 0 中，生产没有限制。

• 可能存在包括所有形式语法的任何阶段结构语法

• 它们生成被图灵机识别的语言。

• 产生式可以是 a->b 的形式，其中 a 是一串终结符，并且至少有一个非终结符，并且 a 不能为空。b 是终结符和非终结符的字符串。

示例

S->ACaB

Bc->acB

CB->DB

aD->Db