非回文的上下文无关语法

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

确保您的语法仅生成非回文的最佳方法如下： 定义：

• Pal - 回文的语言
• {a, b}* - 包含字母 {a, b} 上所有字符串的语言
• Non-Pal - 所有非回文字符串的语言（即不在 Pal 中）

观察者非 Pal = {a, b}* - Pal

Pal 的语法如下：

• S -> 拉姆达 | | 乙 | 萨 | 锑

{a, b}* 的语法可以写成如下：

• S -> 拉姆达 | 萨 | 锑

现在要构建非 Pal 的语法，请注意以下几点：

• 如果 x 是非 Pal 的元素，则：
  • axa是非Pal的一个元素
  • bxb 是非 Pal 的元素
• 如果 y 是 {a, b}* 的元素，则：
  • ayb是非Pal的一个元素
  • bya是非Pal的一个元素

结合所有这些信息，非 Pal 的语法将是：

• S -> aSa | bSb | 抗体| 氨基酸
• A -> 拉姆达 | 啊| 抗体

我希望这能澄清事情

Answer 2

该T语法中的定义确实似乎是不必要的并发症.T可以生成任何as和bs的字符串,因此更简单的定义也同样好.

由于写书的香肠工厂特性,我只能猜测这些作品是按原样给出的.

原始的错误答案:

他们是不等价的,因为X它本身不能<epsilon>,而T不是任意组合a和b.T只能扩展到回文结构(包括空回文,单个字符或具有不成对中心字符的回文).

如果X可能是空的,那么T可以扩展到任何东西,但它不能.

注意

这个答案是基于这样的假设:作者的制作意图T -> XTX是替换中的两个相同的非终端必须代表相同的字符串.由于我没有要查看的文本,我不知道这个假设是否有充分根据,除非它是由问题本身激发的.如果在其他地方不是这种情况,那么这个假设可能是作者的错误.我认为,一般来说,这种要求不适用于无上下文的语法.

正确的作品将是:

R -> aRa | bRb | S
S -> aTb | bTa
T -> aTa | bTb | a | b | <epsilon>

Answer 3

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

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

后者可能看起来很直观。但是，如果您考虑回文的定义或构造，您可能会明白为什么以这种方式编写是有意义的。

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

T -> aTa | 结核病 | 一个 | 乙| 厄普西隆

如果我们想违反构造，我们只需要确保有一层看起来像这样（我使用T作为一层，S作为T之后的一步）

S -> aTb

而其他层我们一般不关心

S-> aTa | aTb | βTa | 结核杆菌

这样就形成了内层（T）和外层（R）以及违反回文结构的层（S）。即使认为T看似多余，但它却形成了与R类似的结构，从而表达了结构的意图。