Haskellで簡単な正規表現を実装した【KMCアドベントカレンダー8日目】 - -KMCアドベントカレンダー8日目の記事です。 講義で正規表現とかオートマトンをちゃんと学んだので、Haskellの修行も兼ねて簡単な正規表現を実装しました。理論とか実装とかダルいと思うので、おまけだけ読むと楽しいかも知れません。 理論 決定性有限オートマトン(DFA) 有限オートマトンとは、 状態集合(s_0, s_1, .., s_N) 入力記号(a, b, c, など) 受理状態集合 初期状態(s_0) 状態遷移関数 によって定義される数学的モデルです。ある入力記号列が与えられると、それを左から読みながら状態を移動していきます（最初は初期状態にいる）。状態の移動は状態遷移関数に依存します。状態遷移関数は、現在の状態と入力記号を受け取って、遷移先の状態を返すような関数です。例えば「s_0にいる状態で'a'を読んだら、s_1に移動する」というような遷移を定義します。全ての記号を読み終わった
