context-free-grammar - 构建上下文无关语法

Question

如何为以下语言构建上下文无关语法：

L = {a^l b^m c^n d^p   | l+n==m+p; l,m,n,p >=1}

我开始尝试：

S -> abcd | aAbBcd | abcCdD | aAbcdD | AabBcCd

然后A=别的东西......但我无法让它工作。

.

我想知道我们如何才能记住为 no 增加了多少 c 的 shud。b的增加？
例如：

string : abbccd

Answer 1

语法是：

1. S1 -> 一个S1 d | S2

2. S2 -> S3 S4

3. S3 -> a S3 b | ε

4. S4 -> S5 S6

5. S5 -> b S5 c | ε

6. S6 -> c S6 d | ε

规则 1 添加相等数量的 a 和 d。

规则 3 添加相等数量的 a 和 b。

规则 5 添加相等数量的 b 和 c。

规则 6 添加相等数量的 c 和 d

这些规则还确保根据给定的语言维护字母表的顺序。

Answer 2

这个怎么样：

S1 -> a S2 d                   # at least one a and d
S2 -> a S2 d
S2 -> S3 S4                    # no more d, split into ab and bc parts
S2 -> S4 S5                    # no more a, split into bc and cd parts

S3 -> a S3 b
S3 ->                          # already ensured at least one a and b
S4 -> b S4 c                  
S4 -> b c                      # at least one b and c
S5 -> c S5 d   
S5 ->                          # already ensured at least one c and d

关键是你如何分组......（即“部分”而不是非终端。）