在我的一个 cs 课程中,他们提到上下文无关语法和上下文相关语法之间的区别在于,在 CSG 中,生产规则的左侧必须小于或等于右侧。
所以,他们给出的一个例子是上下文相关的语法不能有一个空字符串,因为那样第一条规则就不会被满足。
但是,我了解到,常规语法包含在上下文无关中,上下文无关包含在上下文相关中,上下文相关包含在递归可枚举语法中。
因此,例如,如果一个文法是递归可枚举的,那么它也属于上下文相关、上下文无关和常规类型。
问题是,如果发生这种情况,那么如果我有一个包含空字符串的上下文无关语法,那么它将不满足被视为上下文相关的规则,但随后会发生矛盾,因为每个上下文相关是上下文无关的。