为以下语言生成上下文无关文法

Question

**{a^i b^j c^k d^m | i+j=k+m | i<m}**

语法应该允许语言按顺序 abbccd 而不是 cbbcda。首先应该是 a，然后是 b，依此类推。

我知道您必须 "count" 要添加的 a 和 b 的数量，以确保 c 和 d 的数量相等。我似乎无法弄清楚如何确保语言中的 c 多于 a。我感谢任何人可以提供的帮助。我已经为此工作了好几个小时了。

编辑：

语法应该是上下文无关的

我目前只有这两个，因为其他的都错了：

S -> C A D | B

B -> C B D |

C -> 一个 | b

D -> c | d

和

S -> a S d | A

A -> b A c |

（接近但不满足 i < k 部分）

Answer 1

编辑：这是针对 i < k 的情况，而不是 i < m 的情况。 OP改变了问题，但我认为这个答案可能仍然有用。

这不是上下文无关文法，这可以用泵引理证明，该引理指出如果文法是上下文无关的，则存在一个整数 p > 0，使得长度 > 的语言中的所有字符串= p 可以拆分为子串 uvwxy，其中 len(vx) >= 1，len(vwx) <= p，以及 uvⁿwxⁿy 是所有 n >= 0 的语言成员。

假设p值存在。我们可以创建这样的字符串：

k = i + 1
j = m + 1
j > p
k > p

v 和 x 不能包含超过一种类型的字符，或者都在左侧或都在右侧，因为如果将它们提升为幂会立即破坏语法。它们不能是相同的字符，因为它们相乘会破坏 i + j = k + m 的规则。如果 x 是 d，则 v 不能是 a，因为那时 w 包含 bs 和 cs，这使得 len(vwx) > p。通过同样的推理，如果 x 是 cs，则 v 不能是，如果 x 是 ds，则 v 不能是 bs。唯一剩下的选项是 bs 和 cs，但是将 n 设置为 0 会使 i >= k 和 j >= m，从而破坏语法。

因此，它不是上下文无关文法。

Answer 2

必须至少有一个 d 因为 i < m，所以必须有一个 b 来抵消它。 T 和 V 在移动到 S 接受状态之前保证这个标准。

T ::= bd | bTd
U ::= bc | bUc
V ::= bUd | bVd
S ::= T | V | aSd

为以下语言生成上下文无关文法

Generate context free grammar for the following language

grammar