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

Question

问题：为 L= { a^n b^m c^m d^2n } 设计上下文无关语法，其中 n 和 m >= 0

这就是我的制作方法：

s -> ABC ( This is the start symbol generating the entire string. )
A -> aA | null ( Generates the a^n part )
b -> bBc | null ( Generates the b^m c^m part )
c -> ddC| null( Generates the d^2n part )

我已经解决了这个问题，谁能告诉我上述问题的 CFG 是否正确？

Answer 1

给定的语言实际上是上下文无关的语言。因此，我们可以为其提供一种上下文无关语法（CFG）。然而，上述语法对于给定语言来说不是正确的。变量 A 和 C 独立工作。因此，该文法不能保证 d 的数量是 a 数量的两倍。以下语法是可以的：

S -> aSdd | T
T -> bTc | epsilon

首先，为每个终端a生成两个d。当变量 S 完成生成字符串的开头和结尾时，变量 T 开始生成中间部分。