使用 BNF 表示二進位3的倍數

設計文法產生二進位數字，其值為3的倍數

hint:

(1) 在 3 的世界中只會有三種數字 3n, 3n+1, 3n+2
(2) 切割子問題時，只要考慮 1位數 與 多位數

令所求 <3n> 表示三的倍數，則有下面幾個可能

0 ( 單純只有一個數字，又要是三的倍數，所以只能選0 )
<A>0 ( 真正值為 2*A+0 為三的倍數，所以取 A 的值為 <3n> )
<B>1 ( 真正值為 2*B+1 為三的倍數，所以取 B 的值為 <3n+1> )

所以整理一下可以得到：
<3n> → 0 | <3n>0 | <3n+1>1

在這邊要討論 <3n+1> 的部份(三的倍數+1)，仿照上面的論述法：
1 ( 如果單純只有一位數，又要是三的倍數+1，那麼只能選1 )
<C>0 ( 如果 2*C+0 要為三的倍數+1，那麼 C 的值要取 <3n+2> )
<D>1 ( 如果 2*D+1 要為三的倍數+1，那麼 D 的值要取 <3n> )

所以這個階段整理一下：
<3n+1> → 1 | <3n+2>0 | <3n>1

剩最後是 <3n+2> 的部份(即三的倍數+2)，依照上面論述法：
從缺 ( 如果只有一位數字，但又要是三的倍數+2，基本上不可能 )
<P>0 ( 如果 2*P+0 要為三的倍數+2，那麼 P 的值要取 <3n+1> )
<Q>1 ( 如果 2*Q+1 要為三的倍數+2，這種 Q 要選<3n+2> )

整理一下可得：
<3n+2> → <3n+1>0 | <3n+2>1

**

總結上面論述
<3n> → 0 | <3n>0 | <3n+1>1
<3n+1> → 1 | <3n+2>0 | <3n>1
<3n+2> → <3n+1>0 | <3n+2>1