formal-languages - 上下文相关语法

Question

我正在寻找描述以下语言的上下文相关语法：

L = { ww | w ∈ {a,b}*, |w| ≥ 1} <br>

我遇到了一个问题，即不允许使用诸如 X -> ε 之类的规则，因此我不能放置任何非终结符来指示单词的“中间”。这个问题有什么诀窍吗？
如果你碰巧知道答案，请帮忙。

Answer 1

当然，这实际上很容易。在上下文相关的语法中，您可以在 LHS 上有字符串；这就是上下文。所以假设你最终得到一个这样的字符串：

abababWababab

好吧，所以你不想要这样的规则

W := -empty-

出色的。这些规则怎么样？

aWa := aa
aWb := ab
bWa := ba
bWb := bb

当然，这意味着您应该避免引入W，除非您确定将有一个非空字符串。