构建上下文无关文法

我怎样才能构建一个上下文无关文法下列语言：构建上下文无关文法

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的shud增加为没有。 b的增加了吗？
例如：

string : abbccd

来源

2012-10-17 Sameer Jain

为什么不是上下文？ –

（正如我回答的语法所示），我对这个问题的解决方法是1.试着写语法（我失败了）2.尝试证明它不是上下文无关的（我失败了）3.试着写语法再次（我成功了）....我写了评论，但坚持2. :) –

语法是：

S1 - > a S1 d | S2
S2 - >S3S4
S3 - >一个S3 C |小量
S4 - >S5S6
S5 - >乙S5Ç| epsilon
S6 - > c S6 d | epsilon

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

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

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

第六条增加了C'S的数目相等并且D

的规则也保证了字母的顺序是按照给定的语言保持。

来源

2014-05-05 17:33:27

怎么样这个问题：

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

这里的关键是如何组...（即 “零件”，而不是非终端）

来源

2012-10-17 12:29:22

构建上下文无关文法

回答

相关问题