问题是为包含所有字符串的语言开发上下文无关文法，这些字符串的 As 数量多于 Bs。
我想不出合乎逻辑的解决方案。有没有办法解决此类问题，什么可以帮助我更好地解决此类问题？有人可以建议一种逻辑方法来分析此类语法问题吗？
最佳答案
以下语法生成所有超过 {a,b} 的字符串有更多 a比b的。我用 eps 表示空字符串。
S -> Aa | RS | SRA
A -> Aa | eps
R -> RR | aRb | bRa | eps
很明显它总是产生更多
a比b的。它在 {a,b} 上生成所有可能的字符串不太明显。有更多 a比b的生产
R -> RR | aRb | bRa | eps生成所有平衡的字符串(这很容易看到)，并且产生 A -> Aa生成语言 a* (即具有零个或多个 a 的字符串)。这是语法背后的逻辑。请注意，如果
w=c1,c2,c3,...,cn是一个超过 {a,b} 的字符串更多 a比b 's 那么我们总是可以将其分解为平衡字符串的串联(即相等数量的 a 和 b ，其中包括空字符串)和形式为 a+ 的字符串.例如，
ababaaaba = abab (可以由 R 生成)、aaa (可以由 A 生成)、ba (可以由 R 生成)。现在注意生产
S -> Aa | RS | SRA精确地生成这种形式的字符串。足以验证
S涵盖以下情况(因为可以通过分解此类子情况来涵盖所有其他情况，您应该验证):[a][balanced] :使用 S => SRA => AaR . [balanced][a] :使用 S => RS => RA => RAa . [balanced][a]balanced] :使用 S => SRA => RSRA => RAaR . 关于context-free-grammar - as 数量多于 bs 的语言的上下文无关文法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36360541/