8

我需要一个 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

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

4

5 回答 5

7

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

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

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

Pal 的语法如下所示：

  • S -> 拉姆达 | 一个 | 乙 | 阿萨| 锑

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

  • S -> 拉姆达 | 萨 | 锑

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

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

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

  • S -> aSa | 锑| 抗体 | 氨基酸
  • A -> λ | 啊 | 抗体

我希望这能澄清事情

于 2013-12-08T00:23:40.087 回答
5

该语法中的定义T确实似乎是不必要的复杂化。T可以生成任何as 和bs 的字符串，所以更简单的定义也一样好。

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

原始错误答案：

它们不等价，因为它们X本身不能是<epsilon>，也不是 和的T任何组合。只能扩展为回文（包括空回文、单个字符或具有不成对中心字符的回文）。abT

如果X可以为空，则T可以扩展为任何内容，但不能。

笔记

这个答案是基于作者的生产意图T -> XTX是替换中的两个相同的非终结符必须代表相同的字符串的假设。由于我没有要查看的文本，我不知道这个假设是否有根据，除非它是由问题本身引起的。如果其他地方不是这种情况，这个假设可能是作者的错误。我认为，一般来说，这个要求对于上下文无关语法来说是不正确的。

正确的产生是：

R -> aRa | bRb | S
S -> aTb | bTa
T -> aTa | bTb | a | b | <epsilon>
于 2011-06-27T15:32:42.850 回答
3

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

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

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

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

T -> aTa | 结核病 | 一个 | 乙 | ε

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

S -> aTb

而其他层我们一般不关心

S -> aTa | 结核病菌 | 钽 | 结核菌素

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

于 2015-02-14T21:44:06.170 回答
2

我发现这个非回文的定义非常直观。我假设作者从回文的定义开始

R -> aRa | bRb | a | b | <epsilon>

现在问，这个定义如何被“破坏”。

也就是说，他将定义展开了三遍，交换了一个aRa | bRb，aRb | bRa并将剩余的产生式概括为(a|b)R(a|b)。

于 2011-06-28T19:10:20.030 回答
0

任何非回文都可以沿 middle 拆分，使得 x(k) != x(k+ n)

n= 半长 x(i) = 第 i 个位置的字符

牢记这一点，一个简单的解决方案是

R  -> aRa | bRb | T
T  -> aSb | bSa
S  -> aRa | bRb | a | b | T | episoln

它可以生成所有非回文

于 2017-02-28T23:14:36.377 回答