automation - 如何解决这种上下文无关语法

Question

给出一个上下文无关的语法

{ w | w是 {a, b, c, d}* 的元素，使得 # of a+ # of b = # of c + # of D}

我该如何处理这个问题......？

Answer 1

这个怎么样：

S -> A C S     
S -> A S C                   
S -> S A C                 

S -> C A S     
S -> C S A                   
S -> S C A

S -> 
A -> a|b
C -> c|d

（可能有更优雅的解决方案......）

至于如何处理这些，在我看来，关键的见解通常是在分组中（这里是 A 和 C），但我认为最好的学习方法是查看大量示例并尝试大量问题——例如这个。