L{a^n b^m d^n 的上下文无关语法，其中 n>=0，m=2n

Question

L｛a^n b^m d^n的上下文无关语法，其中n>=0，m=2n

S->ABD-

A->aB|a

B->bB|bD->dd|dd

这个正确与否

Answer 1

这是不正确的。我用这种语法能产生的最短单词是abdd，它不符合你的语言。应该可以为n＝0构造一个空字，为n＝1构造一个字abbd。

但是：所提出的语言不是上下文无关的，不能用上下文无关的语法来描述。看看这个答案来证明。

Answer 2

正确的GRAMMAR

Context free grammar for L{a^n b^m d^n where n>=0,m=2n

S->AbbBD|bb

A ->aB|a
B ->bB|b 
D->dd|dD