我需要一个 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
两者不是等价的吗？既然后者更直观，为什么不使用它呢？
确保您拥有仅生成非回文的语法的最佳方法如下：
定义：
- Pal - 回文语言
- {a, b}* - 包含字母表中所有字符串的语言 {a,
b}
- 非 Pal - 所有非回文字符串的语言（即
不在帕尔）
观察非 Pal = {a, b}* - Pal
Pal 的语法已知如下：
{a, b}* 的语法可以写成如下：
现在要构建非 Pal 的语法，请遵守以下规定：
- If x is an element of non-Pal then:
- axa 是非 Pal 的一个元素
- bxb是非Pal的元素
- If y is an element of {a, b}* then:
- ayb 是非 Pal 的元素
- bya 是非 Pal 的一个元素
结合所有这些信息，非 Pal 的语法将是：
- S-> aSa |锑化物 |抗体 |巴阿
- A -> 拉姆达 |啊|抗体
我希望这能澄清事情
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
