语言的上下文无关语法的数量多于bs

Question

问题是为语言开发一个上下文无关文法，该语言包含的所有字符串的数量都多于B。

我想不出合乎逻辑的解决方案。有没有办法解决这些问题，有什么可以帮助我更好地处理这些问题？有人可以提出一个合理的方法来分析这样的语法问题吗？

Answer 1

以下语法生成的{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's）。

这里是语法背后的逻辑。请注意，如果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。

Answer 2

另一种可能是简单的解决办法：

S->A|AAB|BAA|e A->AA | a B->AB | BA | b