context-free-grammar - 非回文的上下文无关语法

Question

我需要一个 CFG 来生成回文以外的字符串。已提供解决方案，如下所示。(计算理论介绍-Sipser)

R -> XRX | S
S -> aTb | bTa
T -> XTX | X | <epsilon>
X -> a | b

我大致了解了这个语法是如何工作的。它要求通过产生式 S -> aTb | bTa 插入一个子串，该子串的任一半都有相应的不等字母表。 ，从而确保永远不会生成回文。

我将按照我的理解写下前两个作品的语义，

S生成不能是回文的字符串，因为它们的第一个和最后一个字母不相等

R由至少一个 S 组成作为子字符串，确保它永远不会是回文。

我不完全理解第三个产品的语义，即 .

   T -> XTX | X | <epsilon>
   X -> a | b

在我看来，T 可以生成 a 和 b 的任意组合，即 {a, b}*。为什么不能像

T -> XT | <epsilon>
X -> a | b

两者不是等价的吗？由于后者更直观，为什么不使用它？

Answer 1

我相信这本书的结构显示出一些对称性，以便更好地阅读。

这意味着它首先构造任何东西，T。然后有一个包装器 S，这样它就不再是一个回文 S，然后在它上面构建所有东西。

后者似乎很直观。但是，如果您考虑回文的定义或构造，您可能会理解为什么以这种方式写作是有意义的。

如果你有一个回文，你会构造这样的东西

T -> aTa | bTb | a | b | epsilon

如果我们想违反构造，我们只需要确保有一层看起来像这样(我使用 T 代表一层，S 代表 T 之后的某一层)

S -> aTb

而其他层我们一般不关心

S -> aTa | aTb | bTa | bTb

这样就形成了内层(T)和外层(R)以及违反回文结构(S)的层。即使认为T似乎是多余的，但它形成了与R相似的构造，从而表达了构造的意图。