问题是为包含所有字符串的 As 数多于 B 的语言开发一种上下文无关语法。
我想不出合乎逻辑的解决方案.有没有办法解决这样的问题，什么可以帮助我更好地处理这些问题？有人可以提出一种逻辑方法来分析这些语法问题吗？
以下语法生成{a,b}上所有a多于b的字符串。我通过eps空字符串来表示。
S -> Aa | RS | SRA
A -> Aa | eps
R -> RR | aRb | bRa | eps
很明显，它总是产生比b更多的a。不太明显的是，它会在{a,b}上生成所有可能的字符串，这些字符串的a比b的多
生产R -> RR | aRb | bRa | eps生成所有平衡字符串(这很容易看到(，生产A -> Aa生成语言a*(即具有零个或多个a的字符串(。
这是语法背后的逻辑。请注意，如果w=c1,c2,c3,...,cn是一个{a,b}上的字符串，a多于b，那么我们总是可以将其分解为平衡字符串(即等数的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。
S → TAT
T → ATb | bTA |电汇 |ɛ
A → aA | a
T 生成 #a>= #b 中的任何字符串(包括空字符串(。S 确保在任何位置至少有一个"a"比 b 多。
我能想到的另一个简单解决方案是：
S -> XAX|a
A -> aS|Sa
X -> aXb|bXa|e
对于 e 是 epsilon。
另一个可能更简单的解决方案：
S->A|AAB|BAA|e
A->AA | a
B->AB | BA | b