context-free-grammar - 从给定语言构建上下文无关语法

Question

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

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

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

Answer 1

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

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

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

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

对于不是回文的单词w，我们希望确保存在这样一个位置i，即i开头的第 th 个符号不等于i结尾的第 th 个符号。所以，我们只有在产生的开头和结尾放置了不同的字母后才终止单词产生：

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状态«we have not put different letters yet»T的含义，以及«we have put different letters»的含义。注意我已经删除S -> ""了这个 CFG 中的规则，所以我们将只完成 from T，所以我们肯定会在生成单词时放置不同的字母。