查找上下文无关文法

Question

我已经有相当多的问题，此任务：

L = {w element of {a,b}* | 
     the number of a's plus 2 times the number of b's modulo 5 in w is 0} 

我想过：

S -> ε 

S -> abbS 

S -> babS 

S -> bbaS 

S -> aaaaaS 

S -> aaabS 

等等

但不能成为最佳的解决方案，因为你也必须改变S的位置，并且会产生太多的情况。而且它只是列举案例，而不是一个“通用解决方案”，这显然不是目标。

Answer 1

我建议引入辅助非末端符号：

• M5 = the number of a's plus 2 times the number of b's modulo 5 in w is 0
• M4 = the number of a's plus 2 times the number of b's modulo 4 in w is 0
• M3 = the number of a's plus 2 times the number of b's modulo 3 in w is 0
• M2 = the number of a's plus 2 times the number of b's modulo 2 in w is 0

然后语法可以表示如下：

S -> ε 
S -> M5 S 

M5 -> a M4 
M5 -> M4 a 
M5 -> b M3 
M5 -> M3 b 

M4 -> a M3 
M4 -> M3 a 
M4 -> b M2 
M4 -> M2 b 

M3 -> a M2 
M3 -> M2 a 
M3 -> b a 
M3 -> a b 

M2 -> a a 
M2 -> b