正規表現を微分する

初めに

正規表現を微分する、という言葉を聞いたので自分で調べてみた。

Brzozowski微分

正規表現$R$と文字列$\omega$がマッチするかどうかを判定する手法。

1. 文字列 $\omega$ の先頭文字 $c$ を 1 文字ずつ読み取る
2. 読み取った文字 $c$ に対して正規表現 $R$ を微分し、新しい正規表現 $R'$ を得る($\partial_cR = R'$)
3. これを文字列の末尾まで繰り返す
4. 最後に得られた正規表現が空文字列 $\epsilon$ を受理できれば、$\omega$ は $R$ にマッチする

基本的な微分規則

以下は、代表的な正規表現に対する微分の定義である。

空集合と空文字

$\partial_c \emptyset = \emptyset$

$\partial_c \epsilon = \emptyset$

文字

$\partial_c a = \epsilon$（ただし $a = c$ のとき）

$\partial_c a = \emptyset$（ただし $a \neq c$ のとき）

選択（OR）

$\partial_c (R_1 | R_2) = \partial_c R_1 | \partial_c R_2$

連接

$\partial_c (R_1 R_2) =\partial_c R_1 R_2 | \partial_c R_2 $($R_1$ が $\epsilon$ を受理する場合)
$\partial_c (R_1 R_2) = (\partial_c R_1) R_2$(それ以外)

繰り返し（Kleene star）

$\partial_c(R^*)=\partial_c(R)R^*$

nullableについて

$nullable(R)$（または $v(R)$）とは、正規表現 $R$ が空文字列 $\epsilon$ を受理できるかどうかを判定する関数。

例:
$v(\emptyset)=false$
$v(\epsilon)=true$
$v(a)=false$
$v(R_1 | R_2)=R_1 \lor R_2$
$v(R_1 R_2)=R_1 \land R_2$
$v(R^*) = true$

具体例

$R=aab$,$\omega=a$
$R_1=\partial_a(R)=ab$
$v(R_1)=false$
よって$R$は$\omega$にマッチしない

---

$R=aab$,$\omega=aab$
$R_1=\partial_a(R)=ab$
$R_2=\partial_a(R_1)=b$
$R_3=\partial_b(R_2)=\epsilon$
$v(R_3)=true$
よって$R$は$\omega$にマッチする

---

選択

$R=hoge|piyo,\omega=piyo$
$R_1=\partial_p(R1|R2)=\emptyset|iyo=iyo$
$R_2=\partial_i(R_1)=yo$
$R_3=\partial_y(R_2)=o$
$R_4=\partial_o(R_3)=\epsilon$
$v(R_4)=true$
よって$R$は$\omega$にマッチする

---

連接

$R1=hoge,R2=piyo,\omega=hogepiyo$
$R_1=\partial_h(R1 R2)=\partial_h(hoge)R2=oge ; piyo$
$...$
$R_4=\partial_h(R_3 R2)=\partial_e(e)R2=piyo$
$R_5=\partial_p(R2)=iyo$
$...$
$R_8=\partial_o(R_7)=\epsilon$
$v(R_8)=true$
よって$R$は$\omega$にマッチする

---

繰り返し

$R=a^*,\omega=aaaa$
$R_1=\partial_a(R)=\partial_a(R)a^*=\epsilon R=a^*$
$R_2=\partial_a(R_1^*)=\partial_a(R_1)a^*=\epsilon R_1=a^*$
$R_3=\partial_a(R_2^*)=\partial_a(R_2)a^*=\epsilon R_2=a^*$
$R_4=\partial_a(R_3^*)=\partial_a(R_3)a^*=\epsilon R_3=a^*$
$v(R_4*)=true$
よって$R$は$\omega$にマッチする

参考文献

• Derivatives of Regular Expressions
  https://dl.acm.org/doi/pdf/10.1145/321239.321249
• ゾゾウスキー微分-Wikipedia
  https://ja.wikipedia.org/wiki/%E3%82%BE%E3%82%BE%E3%82%A6%E3%82%B9%E3%82%AD%E3%83%BC%E5%BE%AE%E5%88%86
• 正規表現の微分を Haskell で実装してみる-@tnagao7
  https://qiita.com/tnagao7/items/6b64cad31de7d4dccb64