这种语言的上下文无关语法是什么：L= {a^n b^m c^p d^q / m+n=p+q where n,m,p,q >=0 }

Question

我试图找到
的上下文无关语法 L= {a^n b^m c^p d^q / m+n=p+q where n,m,p,q >=0 } 但我卡住了。这是我到目前为止所做的：

S -> X S Y | epsilon
X -> a|b
Y -> c|d

但我发现它不遵守顺序，例如 bacd 被接受但它不应该：

X S Y -> XX S YY -> ba S cd -> bacd

Answer 1

S -> aSd 将 A 和 d 放在两边。

S -> X | Y - X 产生更多的 A，Y 产生更多的 d

X -> aXc - A 多于 d

Y -> bYd - d 多于 a

X -> Z。- Z 添加 b 和 c

Y -> Z - Z 添加 b 和 c

Z -> bZc Z 添加 b 和 c

Z -> eps Z 终于消失了。

Answer 2

我们可以使用以下“技巧”“强制”执行顺序：

  S -> aSd |  X | Y
  X -> bXd | Z
  Y -> aYc | Z
  Z -> bZc | epsilon

基本上，我们只允许 S 派生出 a 和 d（完全派生词的“外部”部分）。然后，我们允许 S 导出 X 或 Y，它们中的每一个都代表一个变化：我们开始写 b 而不是 a' s 或开始使用 c's 而不是 d's（这是完全派生词的第二个最里面的部分），最后 Z 只允许 b' s 和 c's（完全派生词的最里面部分）

这种语言的上下文无关语法是什么：L= {a^n b^m c^p d^q / m+n=p+q where n,m,p,q >=0 }

What's the Context-Free grammar of this language :L= {a^n b^m c^p d^q / m+n=p+q where n,m,p,q >=0 }

context-free-grammar

context-free-language