読者です 読者をやめる 読者になる 読者になる

きくらげ観察日記

好きなことを、適当に。

正規表現エンジン制作入門(2): いろいろなDFA

オートマトンの単位を落としてしまいましたが、正規表現エンジンは作っていきたいと思います。

前回定義したDFAを思い出してみましょう。

inkar-us-i.hatenablog.com

DFAは状態を持ち、入力された文字によってその状態を変えていく機械でした。

f:id:cloudear8:20170224082156p:plain

この図はsが初期状態であり、文字'0'を受け取れば状態aに、'1'を受け取れば状態bに、'2'を受け取れば状態cに遷移し、bが受理状態であるオートマトンを表しています。

このオートマトンを使って、簡単な正規表現を表してみましょう。

[abc]+を受理するオートマトン

f:id:cloudear8:20170224082931p:plain
上図のオートマトン正規表現[abc]+を受理します。初期状態はs0であり、そこからa, b, cのいずれかの文字を受け取ると受理状態s1に遷移します。
矢印が省略されている場合は失敗を意味します。すなわち、このオートマトンは実際は以下のオートマトンの省略になっています。
f:id:cloudear8:20170224083321p:plain
ちなみに、この暗黙的に用意される非受理状態fは前回実装したDFAではNothingで表されます。

このオートマトンを前回実装したDFA型の値として表してみましょう。

-- Examples.hs
-- [abc]+
abcPlus :: DFA Int Char
abcPlus = DFA {
    dfaTransTable = [
        (s0, 'a') --> s1
      , (s0, 'b') --> s1
      , (s0, 'c') --> s1
      , (s1, 'a') --> s1
      , (s1, 'b') --> s1
      , (s1, 'c') --> s1
      ]
  , dfaStart = s0
  , dfaAccepts = [s1]
  } where s0:s1:_ = [0..]

前回も説明しましたが、状態s0, s1の実体は区別できれば何でもいいので、

s0:s1:_ = [0..]

として適当な数値を割り当てています。

試しに実行してみましょう。

>>> abcPlus `accepts` "a"
True
>>> abcPlus `accepts` "b"
True
>>> abcPlus `accepts` "c"
True
>>> abcPlus `accepts` "accabbccbcbc"
True
>>> abcPlus `accepts` "accabbccbcbcd"
False
>>> abcPlus `accepts` "accabbdccbcbc"
False

abcPlusが正規表現[abc]+を表していることがわかると思います。

a(b|cd)*eを受理するオートマトン

このようなオートマトンは以下のように作ることができます。
f:id:cloudear8:20170224091002p:plain
また、このようなオートマトンを表すDFA型の値は以下のように定義することができます。

-- Example.hs
-- a(b|cd)*e
abcde :: DFA Int Char
abcde = DFA {
    dfaTransTable = [
        (s1, 'a') --> s2
      , (s2, 'b') --> s2
      , (s2, 'c') --> s3
      , (s3, 'd') --> s2
      , (s2, 'e') --> s4
      ]
  , dfaStart = s1
  , dfaAccepts = [s4]
  } where s1:s2:s3:s4:_ = [0..]

実行結果:

>>> abcde `accepts` "abcde"
True
>>> abcde `accepts` "ae"
True
>>> abcde `accepts` "abbbbe"
True
>>> abcde `accepts` "acdcdbcde"
True
>>> abcde `accepts` "acbde"
False
>>> abcde `accepts` "abcdcd"
False
>>> abcde `accepts` "abbeb"
False

このようにして実例を見ていくと、正規表現オートマトンで表せそうなことが何となくわかるのではないでしょうか。
それでは次回に続きます。