扩展到CFG,它是什么？

Question

考虑以下对无上下文语法的扩展,该语法允许规则在左侧,非终端右侧的一个(或多个)终端.也就是说,形式的规则:

A b -> ...

右侧可以是任何东西,例如在无上下文的语法中.特别是,不要求右侧的末端具有完全相同的终端符号.在这种情况下,此扩展将是上下文相关的.但终端不仅仅是一个背景.有时,这个终端被称为"后推".

显然,这不再是CFG(类型-2).它包括类型1.但它是什么？真的输0了吗？

Prolog 中的Definite Clause Grammars dcg允许这种特殊的扩展.(为了避免误解,我在这里不考虑Prolog的完整扩展.即我假设终端来自有限的字母而不是任意的术语,我也不认为Prolog在DCG中允许的其他参数,这些参数也属于类型 - 已经0了.)

---

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

A b -> <epsilon>

Answer 1

这是一个部分答案:

语法在类型0内.上下文敏感语法 (类型-1)具有形式的规则,wAx -> wBx其中w和x是终端和非终端的串,并且B不是空的.请注意,由于B不为空,|wAx| <= |wBx|.你的语法有这样的形式规则,Ax -> z其中z是一串终端和非终端,可以是空的,可以删除x.这违反了CSG的两个原则.

不满意的是,我没有回答两件事:

• 是语言通过你的语法1型产生的？语法是type-0,但这并不意味着语言不能是type-1.例如,常规语言(类型-3)可以由CFG(类型-2)描述.

• 语言是递归的吗？这很重要,因为如果是这样,语言是可判定的(不会遇到暂停问题).

  我现在正试图证明第二点,但这可能超出了我的能力范围.

Answer 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].

因此，“半”在这里的意思是“一半” - 类似于半群，其中群的代数属性的一半成立。