考虑以下上下文无关语法的扩展，它允许规则在左侧有一个（或多个）终端在非终端的右侧。即，形式规则：
A b -> ...
右侧可以是任何东西，就像在上下文无关语法中一样。特别是，它是not要求右侧末尾具有完全相同的终端符号。在这种情况下，此扩展将是上下文相关的。但终端不仅仅是一个上下文。有时，这个终端被称为“推回”。
显然，这不再是 CFG（类型 2）。它包括类型1。但它是什么？真的已经是 type-0 了吗？
定子句语法允许这种特殊的扩展dcg在序言中。 （为了避免误解，我在这里不考虑 Prolog 的完整扩展。即，我假设终端来自有限字母表，而不是任意术语，我也不考虑 DCG 中允许的 Prolog 附加参数，这些参数也进入类型 -已经 0 了。）
编辑：这是描述扩展的更简单方法：添加到表单的 CFG 规则
A b -> <epsilon>
这是部分答案：
语法属于类型 0。 A上下文相关语法(type-1) 具有以下形式的规则wAx -> wBx其中 w 和 x 是终结符和非终结符的字符串，并且 B 不为空。请注意，由于 B 不为空，|wAx| <= |wBx|。你的语法有以下形式的规则Ax -> z其中 z 是终结符和非终结符的字符串，可以为空，x 可以被删除。这违反了CSG的两条原则。
令人不满意的是，我没有回答两件事：
-
Is the language由你的语法 type-1 生成？语法是类型 0，但这并不意味着语言不能是类型 1。例如，常规语言（类型 3）可以通过 CFG（类型 2）来描述。
-
是语言递归的？这很重要，因为如果是这样，语言是可判定的（不会遇到停止问题）。
我目前正在尝试证明第二点，但这可能超出了我的能力。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
