我需要一个 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
两者不是等价的吗?由于后者更直观,为什么不使用它?