やったこと

一蘭に行った

ひさしぶりに行った気がする。まあそれなりに美味しい。たまに食べたくなる感じ。

Hopcroft-Karpのアルゴリズムを実装した

Hopcroft-Karpのアルゴリズムを使って二つのDFAが同値であることの確認するプログラムを書いた。

Union-Findとか最近書いてなかったけど案外書けるもんだ。

https://gist.github.com/MakeNowJust/f1e414013b074ec9ddb4daf596eb6709

Hopcroft-Karpのアルゴリズムと言えば二部マッチングのためのアルゴリズムなのだけど、こういう使い方もできるのだなぁと思うのだった。

ちなみにこのコードは次の論文を参考にした。

Testing the Equivalence of Regular Languages
Almeida M., Moreira N., Reis R. (2009)
https://arxiv.org/abs/0907.5058

まあDFAで同値をチェックするのだと正規表現から式の情報が失われてしまうので、あまり今後の目的には似わないし、多分使うことは無いと思う。式変形で同値をチェックするアルゴリズムを学ばねば‥‥。