math - 引入更多条件的上下文无关语法

Question

我需要为语言 A = {a^ib^jc^k | 写一个 cfg i,j,k>0 j!=k}

我的第一个想法是创建一个没有 j!=k 限制的简单语法

S -> A B C
A -> aA | a
B -> bB | b
C -> cC | c

这显然不适用于限制，我如何引入 j!=k 来创建新的 CFG？

Answer 1

您需要将其分为两种情况，具体取决于 j>k 还是 k>j。

S -> A X | A Y
A -> aA | a
X -> bX | bZ  # every X -> bX gives you an extra b
Y -> Yc | Zc  # every Y -> Yc gives you an extra c
Z -> bZc | bc  # Z produces b^j c^j strings