Нахождение контекстно-свободной грамматики

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