【blog.hellorusk.net に移行しました】

旧・技術メモ(blog.hellorusk.net に移行しました)

形式言語

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

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

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

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