从给定语言构建上下文无关语法

Question

我需要帮助为给定语言构建CFG。

L = { x ∈ {a, b}* | x != x reversed }，换句话说，L是L中所有回文的补语。

我更感兴趣的是如何处理这类问题，而不是具体的解决方案。

Answer 1

好吧，我还没有弄清楚解决此类问题的常见模式，但我想我知道如何解决这个问题：

首先考虑回文语言L的CFGG(L)(让我们考虑二进制字母)：

S -> ""
S -> "0" S "0"
S -> "1" S "1"
S -> "1" // odd length case
S -> "0" // odd length case

构造G(L)的想法是确保最后一个符号等于 S 中的第一个符号，因此，对于每个位置i，从开头开始的第i个符号等于该语法产生的单词从末尾开始的第i个符号。

对于一个不是回文的单词w，我们希望确保有一个位置i，即开头的第i个符号不等于结尾的第i个符号。因此，让我们仅在生产开始和结束放置不同的字母后终止单词生产：

S -> "0" S "0"
S -> "1" S "1"
S -> "0" T "1"
S -> "1" T "0"
T -> ""
T -> "0" T "0"
T -> "1" T "1"
T -> "0" T "1" // we are allowed to put different symbols more than once
T -> "1" T "0" // we are allowed to put different symbols more than once
T -> "0"
T -> "1"

您可以S给出状态的含义"我们还没有放不同的字母"，T"我们放了不同的字母"的含义。请注意，我已经删除了此 CFG 中的S -> ""规则，因此我们只会从T完成，因此我们肯定会在生成单词时放置不同的字母。