やったこと

2DFAの勉強をした

双方向決定的有限状態オートマトン(2DFA)がどうしてDFAに変換できるのかよく分からなかったので勉強した。

末尾が文字aである文字列waがあるときに、aの位置に状態qで入ってきて、wの文字列を戻ったりしたあとaの次の位置へpで出て行くような状況をT[wa](q) = pと書くことにする。（下図参照）

| ... w ... | a |
 /-<-------<-[ ]<-q-
 \->------->-[ ]-p->

状態の数は有限だから、T[wa](q) = pの組み合わせの数は状態の数をnとしてたかだかn^nの有限個になる。これは明かに文字列の数よりも小さいので、異なる文字列xとyでT[x] = T[y]となるようなx, yの組が存在する（鳩の巣原理）。このようなx, yに同じ末尾文字列zをつけた文字列xz, yzはxzが受理されるときに限りyzも受理されるだろう。逆もまた然り。よってT[x] = T[y]であることをx ~ yとすると~は同値関係であり、Myhill-Nerodeの定理より2DFAは正規であると言える。そして、T[x]を状態としてDFAを構築することができる、というわけ。

しかしこれを実装するのはとてもしんどい。あと、Verdiという人が考えた別のDFA構築の方法もあって、そっちも面白い。が、やはり実装が面倒。

実装した

なぜかHaskell。

https://github.com/MakeNowJust-Labo/two-way-dfa

DFAへの変換を実装していないのでダメと言えばダメ。