prolog - CFG 的扩展，是什么？

Question

考虑以下上下文无关文法的扩展，它允许规则在左侧有一个(或多个)终结符在非终结符的右侧。即形式规则:

A b -> ...

右手边可以是任何东西，就像在上下文无关文法中一样。特别是 不是 要求，右侧将在末尾具有完全相同的终结符。在这种情况下，此扩展名将是上下文敏感的。但终端不仅仅是一个上下文。有时，这个终端被称为“回推”。

显然，这不再是 CFG(类型 2)。它包括类型 1。但它是什么？真的已经是 0 型了吗？

定语从句语法中允许此特定扩展 dcg在序言中。 (为了避免误解，我在这里不考虑 Prolog 的完整扩展。即我假设终端来自有限字母表而不是任意术语，我也不考虑 DCG 中允许的 Prolog 附加参数，这些参数也进入类型- 0 已经。)

编辑:这是描述扩展的一种更简单的方法:添加到表单的 CFG 规则

A b -> <epsilon>

Answer 1

这是部分答案:
语法在类型 0 内。A context-sensitive grammar
(type-1) 具有形式 wAx -> wBx 的规则其中 w 和 x 是终结符和非终结符的字符串，B 不为空。请注意，由于 B 不为空，|wAx| <= |wBx| .你的语法规则的形式是 Ax -> z其中 z 是一串终结符和非终结符，可以为空，x 可以删除。这违反了 CSG 的两个原则。
令人不满意的是，我没有回答两件事:

你的语法生成的语言是 type-1 吗？语法是类型 0，但这并不意味着语言不能是类型 1。例如，常规语言(类型 3)可以用 CFG(类型 2)来描述。

是语言recursive ?这很重要，因为如果是这样，语言是可判定的(不受停机问题的影响)。
我目前正在尝试证明第二点，但这可能超出了我的能力。