complexity-theory - 对语言和 CFG 的一些限制

Question

我看到一个关于自动机理论的注释：

考虑以下语言：

L={xy : x,y in {a,b}*}

并考虑以下约束：

1) x=y

2) x != y

3) x=(y) 反向

4) x 的数量不等于 y 的数量

我读了一种带有约束 2,3,4 的语言是上下文无关的。高度赞赏 1 到 3 的任何提示或教程。

Answer 1

正如你所说，它不是一种上下文无关的语言。L1: {xy | x,y ∈ {a,b}* ∧ x=y}

但是，非常相似的是上下文无关的，如下所示：L3: {xy | x,y ∈ {a,b}* ∧ x=y-1}

S → Ø
S → a S a
S → b S b

从技术上讲，您问题中的另外两种语言是微不足道的：

L2: {xy | x,y ∈ {a,b}* ∧ x≠y}
L4: {xy | x,y ∈ {a,b}* ∧ |x|≠|y|}

因为唯一不满足约束的字符串是空字符串。任何非空字符串S都可以简单地分解为两个不相等的字符串Ø和S; 很明显，这两个字符串的串联是S，除非S为空，否则这两个字符串是不相等的并且具有不同的长度。由所有非空字符串组成的语言不仅是上下文无关的，而且是常规的：.(a|b)+

既然这很容易，我怀疑这不是你真正要问的，但我猜不出你的真正意思。我建议您将问题编辑得更准确。