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