查找上下文無關文法

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