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)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||