考虑以下对上下文无关文法的扩展，它允许规则在左侧具有一个（或多个）终结符在非终结符的右侧。也就是说，形式的规则：
A b -> ...
右手边可以是任何东西，比如在上下文无关文法中。特别是，不需要右手边的末尾有完全相同的终端符号。在这种情况下，此扩展将是上下文相关的。但终端不仅仅是一个上下文。有时，这个终端被称为“推回”。
显然，这不再是 CFG（类型 2）。它包括类型 1。但它是什么？真的已经是 type-0 了吗？
Prolog 中的定句语法dcg允许此特定扩展。（为了避免误解，我在这里不考虑 Prolog 的完整扩展。即我假设终端来自有限的字母表而不是任意术语，我也不考虑 DCG 中允许的 Prolog 的附加参数，这些参数也进入类型- 0 已经。）
编辑：这是描述扩展的更简单方法：添加到表单的 CFG 规则
A b -> <epsilon>
这是部分答案：
该文法属于类型 0。上下文相关文法
（类型 1）具有以下形式的规则，wAx -> wBx其中 w 和 x 是终结符和非终结符字符串，并且 B 不为空。请注意，由于 B 不为空，|wAx| <= |wBx|。您的语法具有以下形式的规则，Ax -> z其中 z 是一串终结符和非终结符，可以为空，并且可以删除 x。这违反了 CSG 的两个原则。
不满意的是，我没有回答两件事：
你的语法是 type-1 生成的语言吗？语法是 type-0，但这并不意味着语言不能是 type-1。例如，常规语言（类型 3）可以由 CFG（类型 2）描述。
语言是递归的吗？这很重要，因为如果是这样，语言是可确定的（不会受到停止问题的影响）。
我目前正在尝试证明第二点，但这可能超出了我的能力。
为了回答我关于 Prolog 的 DCG 形式主义的问题，这个扩展现在被称为semicontext。参见DCG 的 N253 DIN 草案 2014-04-08 - ISO/IEC WDTR 13211-3:2014-04-08
给定
a1, [b] --> ... .
a2, [b,b] --> ... .
终端序列[b]现在和终端序列一样是半上下文[b,b]。
现在是否会在规则的末尾出现相同的终端序列，我们将有一个上下文：
a3, [b,b] --> ..., [b,b].
所以“半”在这里意味着“一半”——类似于一个半群，其中一个群的一半代数性质成立。
是的，我认为它是 0 型。前 3 种类型（3、2 和 1）的原则是那些不能执行归约。这些是仅生成类型。
在这里，您可以将终端转换为 epsilon，使其类型为 0。