我怎样才能构建一个上下文无关文法下列语言：
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 =别的东西......但我不能得到这个工作。
。
我不知道我们怎么能记得多少C'S shud为没有增加。 的B的增加？
例如：
string : abbccd
Answer 1:
语法是：
S1 - > S1和d | S2
S2 - > S3 S4
S3 - > S3 C | 小量
S4 - > S5 S6
S5 - > S5 B C | 小量
S6 - > C ^ d S6 | 小量
第1条增加了的并且D等于号。
第3条增加了一个和b的人数相等。
第5条增加了B的和C的人数相等。
第六条增加了C'S并且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
这里的关键是如何组...（即“零件”，而不是非终端）。
文章来源: Construct Context free Grammar
