as 数量多于 bs 的语言的上下文无关文法
Context free grammar for languages with more number of as than bs
问题是为包含 A 数多于 B 数的所有字符串的语言开发上下文无关语法。
我想不出合理的解决方案。有什么方法可以解决此类问题，什么可以帮助我更好地解决此类问题？有人可以建议一种逻辑方法来分析此类语法问题吗？
以下语法生成超过 {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*（即具有零个或多个[=12的字符串=]'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.
另一个可能更简单的解决方案：
S->A|AAB|BAA|e
A->AA | a
B->AB | BA | b
S → TaT
T → ATb | bTA | TT | ε
A → aA |一个
T 生成#a >= #b 的任何字符串（包括空字符串）。 S确保在任何位置至少比b多'a'。
问题是为包含 A 数多于 B 数的所有字符串的语言开发上下文无关语法。
我想不出合理的解决方案。有什么方法可以解决此类问题，什么可以帮助我更好地解决此类问题？有人可以建议一种逻辑方法来分析此类语法问题吗？
以下语法生成超过 {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*（即具有零个或多个[=12的字符串=]'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.
另一个可能更简单的解决方案：
S->A|AAB|BAA|e
A->AA | a
B->AB | BA | b
S → TaT
T → ATb | bTA | TT | ε
A → aA |一个
T 生成#a >= #b 的任何字符串（包括空字符串）。 S确保在任何位置至少比b多'a'。