具有更多a而不是b的语言的无上下文文法

Question

这个问题是为包含更多A字符的字符串而不是B字符的所有字符串开发无上下文语法。

我想不出一个逻辑解决方案。有没有一种方法来解决这样的问题，可以帮助我更好地解决这样的问题？有人能建议一种合乎逻辑的分析语法问题的方法吗？

- nino

---

你能更准确地描述一下你想要生成的语言吗？例如，aabbaba 是一个有效的字符串吗？ - blazs

@blazs 是的，aabbaba是一个有效的字符串，对于a或b的顺序没有限制。我可以编写适用于A之后跟着B的情况的语法，但是给定问题的一般性正在证明它很困难。 - nino

Answer 1

以下文法生成所有在{a,b}上的字符串，这些字符串中 a 的数量要多于 b 的数量。我用 eps 来表示空字符串。

S -> Aa | RS | SRA
A -> Aa | eps
R -> RR | aRb | bRa | eps

很明显，它总是生成比'b'更多的'a'。不太明显的是，它生成所有可能的字符串，其中有比'b'更多的'a'，并且平衡的字符串使用产生式R -> RR | aRb | bRa | eps可以很容易地生成，而语言a* （即具有零个或多个'a'的字符串）可以通过产生式A -> Aa生成。

这里是该文法的逻辑。请注意，如果w = c1，c2，c3，...，cn是一个由{a，b}组成的字符串，其中有比'b'更多的'a'，则我们总是可以将其分解为平衡字符串（即等量的'a'和'b'，包括空字符串） 和形如'a+'的字符串的连接。

现在请注意，产生式S -> Aa | RS | SRA精确地生成这种形式的字符串。

只需验证S涵盖以下情况即可（因为您应该验证每种其他情况都可以通过分解为这种子情况来涵盖）。 - [a][balanced]: 使用S -> SRA -> AaR。 - [balanced][a]: 使用S -> RS -> RA -> RAa。 - [balanced][a]balanced: 使用S -> SRA -> RSRA -> RAaR。

- blazs

---

有一个严格的不等式，A的数量和B的数量不能相等。 - nino

是的，谢谢，我刚刚注意到并纠正了答案。 - blazs

你能解释一下解决方案背后的逻辑和思考过程吗？那会帮很多忙。先谢谢了。 - nino

非常感谢，这真的澄清了很多问题。我只有一个愚蠢的疑问，是否需要 R -> RR？ - nino

是的：你需要它来生成例如aaabbbaabb的字符串。 - blazs

啊，是的，如果没有它，我们需要在第0个和第n-1个位置、第1个和第（n-2）个位置等匹配a和b，现在我明白了。 - nino

Answer 2

S → TAT

T → ATb | bTA | TT | ɛ

A → aA | a

T可以生成任何满足#a >= #b（包括空字符串）的字符串。S确保在任何位置上至少有一个'a'比'b'多。

- Silvio Bandeira

---

字符串aabababbbbbaabbbaabbababbaa中有12个a和15个b（a的数量少于b），但是（根据JFLAP的说法）该字符串似乎属于由此文法生成的语言。 - user3134725

你的测试出了问题。我没有使用jflap，但是https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/工具显示不同。此外，生成你提到的字符串是不可能的，因为每次生成一个'b'，你都必须至少生成一个'a'...再加上开头的额外的'a'确保有更多的a比b。 - Silvio Bandeira

Answer 3

我能想到的另一种简单解决方案是：

S -> XAX|a

A -> aS|Sa

X -> aXb|bXa|e

其中 e 表示空集。

- Silent

Answer 4

另一种可能更简单的解决方案：

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

- Dhruv Ghulati