在 codewars 做 Kata 時遇到 Regular Expression - Check if divisible by 0b111 (7) 這題。因為在正規和計算理論都有碰到 DFA ，想說當作複習，找出對所有 n 最一般的 DFA ，然後試著直接得到對應的正則表達式。

分析

假設到某個時段吃進來的字串為 k 的二進位表示，若接下來的符號是 1， k 就會變成 2k + 1；如果是 0， k 則會變成 2k。

也就是說只需要紀錄 0 ≤ k ≤ n − 1 接上 1 與 0 會走到哪裡，就能夠將 DFA 建出來。

範例

以下是 n = 4 的例子。藉由上述的作法我們能得到所有的轉換為

$$ \begin{aligned} 0 \xrightarrow{0} 0 \quad 0 \xrightarrow{1} 1 \quad 1 \xrightarrow{0} 2 \quad 1 \xrightarrow{1} 3 \\ 2 \xrightarrow{0} 0 \quad 2 \xrightarrow{1} 1 \quad 3 \xrightarrow{0} 2 \quad 3 \xrightarrow{1} 3 \end{aligned} $$

畫成圖就能得到下面的 DFA。

DFA to regex

假設要拿掉節點 k ，就必須補上 I × O 的邊，這邊的 I 為連到 k 的節點； O 為 k 連到的節點。

因為不太了解拿掉的順序對結果的影響，就先從大到小一個個拿掉。

• 去掉 3
  • I = {1, 3}
  • O = {2, 3}
  • 增加/更新的邊：{(1,2)}

• 去掉 2
  • I = {1}
  • O = {1, 0}
  • 增加/更新的邊：{(1,1), (1,0)}
• 去掉 1
  • I = {0, 1}
  • O = {0, 1}
  • 增加/更新的邊：{(0,0)}

最後得到辨認 5 的倍數的二進位表示的正則表達式為

(0|1((0|11^*0)1)^*(0|11^*0)0)^*

其他想法

觀察上面的範例可以發現只要將有 self-loop 的節點拿掉，那個迴圈就會被分到新產生或更新的邊上，造成表達式出現重複的式子，所以先拿掉 self-loop 的節點應該能減少表達式的長度（？）。