人気ブログランキング | 話題のタグを見る

決定性有限オートマトン

Wikipedia の「決定性有限オートマトン」の例が Haskell と相性がよさそうだったのでプログラムでモデル化してみた。プログラム dfa.hs は次の様になる。

import Control.Monad.State

data Q = Q0 | Q1 deriving (Eq, Show)

delta Q0 0 = Q1
delta Q0 1 = Q0
delta Q1 0 = Q0
delta Q1 1 = Q1

next :: Int -> State Q Q
next x = do
 st <- get
 nxt <- return (delta st x)
 put nxt
 return nxt

簡単に説明すると、状態集合を代数的データ型 Q として定義する。個々の状態は Q0 と Q1 だ。文字集合としては [0,1] をとるがプログラムには明示していない。遷移関数は delta として状態と文字の組に対して次の状態が決まる。状態を補完するのには State モナドを利用した。next 関数はState モナドの関数で、 0 が 1 とその時の状態から次の状態を値として返す。開始状態は Q0 で状態の初期値だが、runState 関数の第2引数として渡す。また、オートマトンに0と1からなる文字列を入力したときに最終の状態がQ0のとき文字列を受理と判断する。

これを ghci の :l コマンドでロードすると、決定性有限オートマトンの実験ができる。

Prelude> :l dfa.hs
[1 of 1] Compiling Main ( dfa.hs, interpreted )
Ok, one module loaded.

動作の実験は runState 関数を用いて行う。入力文字列は [1,0,1,..] のような 0 と 1 のリストにする。このリストに next 関数を mapM でマッピングすると、runState の値として、状態の履歴と最終的な状態のペアが得られる。

*Main> runState (mapM next [0,1,1,0,1,0,0]) Q0
([Q1,Q1,Q1,Q0,Q0,Q1,Q0],Q0)

状態の最終値が Q0 なので文字列 0110100 は受理される。この例のオートマトンでは 0 が偶数個の文字列は受理され、奇数個の場合は受理されない。

*Main> runState (mapM next [0,1,1,0,1,0]) Q0
([Q1,Q1,Q1,Q0,Q0,Q1],Q1)

オートマトンの動作を頭の中だけでシミュレートするだけでなく、実際に動作させて確認することができるので面白い。手を使って機械の動作を確かめている感じがして、機械の仕組みがわかりやすく感じられる。


by tnomura9 | 2023-02-07 16:32 | Haskell | Comments(0)
<< オートマトンの動作実験 自前のモナドを作ってみた >>