trifle

技術メモ(最近は hellorusk.net/blog の方が使うことが多いです)

形式言語

NFAをDFAに変換して状態数最小化する

大学の試験で「与えられた言語を認識するような状態数最小の有限オートマトンを答える」問題が頻出されているため, 検算用のプログラムを書いてみます. NFA の入力形式 input.txt として以下のように与えます. 2 0 0,0 1,0, 1,2,2, 2,3,3, 3,,,1 一行目は[入…

Haskellでも非決定性有限オートマトンがしたい!

理学部オートマトン学科に在籍しているので, オートマトンについて勉強させられています. これは決定性有限オートマトンという良いオートマトンです. 各状態と各文字に対して, 状態遷移がちょうど1つだけ定められています. 形もかっこいいですね. これは非決…