Chomsky Hierarchy 代表不同机器接受的语言类别。
根据乔姆斯基的语法层次结构在下面根据语法类型进行解释 -
类型 0. 不受限制的语法
图灵机 (TM)
类型 1. 上下文相关的语法
线性有界自动机 (LBA)
类型 2. 上下文无关文法
下推自动机 (PDA)
类型 3. 正则文法
有限自动机 (FA)
类型 1 语法也称为上下文敏感语法
上下文敏感语法用于表示上下文敏感语言
上下文相关语法在其产生式规则的左侧可能有多个符号。
左侧的符号数不得超过右侧的符号数。
除非 A 是起始符号,否则不允许采用 A->epsilon 形式的规则。它不会出现在任何规则的右侧。
类型 1 语法必须是类型 0。
在类型 1 中,生产应采用 V->T 的形式。
V 中的计数符号小于或等于 T。
S->AB
AB->ABC
乙_>乙