非回文的上下文无关语法
我需要一个 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
两者不相等？既然后者更直观，为什么不使用它呢？
I need a CFG which will generate strings other than palindromes. The solution has been provided and is as below.(Introduction to theory of computation - Sipser)
R -> XRX | S
S -> aTb | bTa
T -> XTX | X | <epsilon>
X -> a | b
I get the general idea of how this grammar works. It mandates the insertion of a sub-string which has corresponding non-equal alphabets on its either half, through the production S -> aTb | bTa, thus ensuring that a palindrome could never be generated.
I will write down the semantics of the first two productions as I have understood it,
Sgenerates strings which cannot be palindromes because their 1st and last alphabets are not equalRconsists of at-least oneSas a sub-string ensuring that it is never a palindrome.
I don't completely understand the semantics of the third production, i.e. .
T -> XTX | X | <epsilon>
X -> a | b
The way I see it, T can generate any combination of a and b, i.e. {a, b}*. Why could it not have been like
T -> XT | <epsilon>
X -> a | b
Aren't the two equivalent? As the later is more intuitive, why isn't it used?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
确保您拥有仅生成非回文的语法的最佳方法如下：
定义：
b}
不在 Pal 中）
观察者发现 non-Pal = {a, b}* - Pal
Pal 的语法已知如下：
{a, b}* 的语法可以写成如下：
现在要构造非 Pal 的语法，请遵守以下规定：
结合所有这些信息，非 Pal 的语法将是：
我希望这能澄清问题
The best way to ensure that you have a grammar that generates only non-palindromes is the following:
Define:
b}
not in Pal)
Observer that non-Pal = {a, b}* - Pal
The grammar for Pal is know to be the following:
The grammar for {a, b}* can be written as follows:
Now to construct the grammar of non-Pal observe the following:
Combining all this information the grammar for non-Pal would be:
I hope this clarifies things
该语法中
T的定义确实显得不必要的复杂化。T可以生成任何a和b字符串，因此更简单的定义也同样好。我只能猜测这些作品是按原样给出的，因为写书的香肠工厂性质。
原始错误答案：
它们不等价，因为
X本身不能是T是不是a和b的任意组合。T只能扩展为回文（包括空回文、单个字符或具有不成对中心字符的回文）。如果
X可以为空，那么T可以扩展到任何内容，但它不能。注意
这个答案是基于作者的制作意图
T -> 的假设。 XTX是指替换中的两个相同的非终结符必须表示相同的字符串。由于我没有文字可看，我不知道这个假设是否有充分根据，除了它是由问题本身引发的。如果其他地方情况并非如此，那么作者的这种假设可能是错误的。我认为，一般来说，这个要求对于上下文无关语法来说并不成立。正确的产生式是：
The definition of
Tin that grammer does indeed appear to be unnecessary complication.Tcan generate any string ofas andbs, so the simpler definition would have been just as good.I can only guess that the productions are given as they are because of the sausage-factory nature of writing a book.
ORIGINAL WRONG ANSWER:
They are not equivalent, because
Xitself cannot be<epsilon>, andTis not any combination ofaandb.Tcan only expand to a palindrome (including the empty palindrome, a single character, or a palindrome with an unpaired central character).If
Xcould be empty, thenTcould expand to anything, but it can't.NOTE
This answer is based on the supposition that the author’s intention for the production
T -> XTXis that the two identical non-terminals in the substitution must represent identical strings of characters. Since I don't have the text to look at, I don't know if this assumption is well-founded except that it is motivated by the question itself. This supposition could be a mistake by the author if that is not the case elsewhere. I think that, in general, this requirement is not true of context-free grammers.The correct productions would be:
我认为这本书的结构显示出一些对称性，以便更好地阅读。
这意味着它首先构造任何东西T。然后有一个包装器S，这样它就不再是回文S，然后在它上面构建所有东西。
后者可能看起来很直观。但是，如果您考虑回文的定义或构造，您可能会明白为什么以这种方式编写是有意义的。
如果你有一个回文，你会构造这样的东西
如果我们想违反构造，我们只需要确保有一层看起来像这样（我使用 T 表示一层，S 表示 T 之后的一步）
和其他层我们一般不关心
这样就形成了内层（T）和外层（R）以及违反回文结构的层（S）。即使认为T看似多余，但它却形成了与R类似的结构，从而表达了结构的意图。
The construction the book I believe is shows some symmetry for better reading.
It means it first construct anything, T. Then there is a wrapper S, so that it becomes no longer a palindrome S, and then build everything upon it.
The latter might seems to intuitive. However, if you think of the definition or construction of palindrome, you might understand why writing in such way make sense.
If you have a palindrome, you would construct something like this
And if we want to violate construction, we just need to make sure that there is one layer looks like this (I use T to be one layer and S to something one step after T)
And other layer we generally do not care
So that forms the inner layer (T) and outer layer(R) and the layer that violates the construction of palindrome(S). Even thought T seems to be redundant, but it forms the similar construction like R, thus expressing the intention of the construction.
我发现非回文的这个定义非常直观。我假设作者
从回文的定义开始
，现在问，如何“破坏”这个定义。
也就是说，他将定义展开了三次，交换了一次
aRa | bRb作者：aRb | bRa 并将剩余的产生式推广到(a|b)R(a|b)。I found this definition of a non-palindrome quite intuitive. I assume that the author
started with a definition for a palindrome
and now asked, how this definition can be "ruined".
That is, he unfolded the definition three times, exchanged one
aRa | bRbbyaRb | bRaand generalized the remaining productions to(a|b)R(a|b).任何非回文都可以沿中间分割，
使得 x(k) != x(k+ n)
n= 一半长度
x(i) = 第 i 个位置的字符
记住，一个简单的解决方案是
它可以生成所有非回文
Any Non Palindrome can be split along middle ,
such that x(k) != x(k+ n)
n= half length
x(i) = character at i th position
Keeping that in mind a simple solution would be
It can generate all non palindromes