ele*_*ena 5 haskell automata nfa
我正在 Haskell 中实现一个非确定性有限自动机,我正在尝试实现计算 epsilon 闭包的函数。为此,NFA 实现为:
data Transaction = Transaction {
start_state :: Int,
symbol :: Maybe Char,
end_state :: Int
} deriving Show
data Automaton = Automaton {
initial_state :: Int,
states :: Set.Set Int,
transactions :: [Transaction],
final_states :: Set.Set Int,
language :: Set.Set Char
} deriving Show
Run Code Online (Sandbox Code Playgroud)
而关闭:
--Perform the computations necessary to eclosure
getClosure :: [Transaction] -> [Int]
getClosure [] = []
getClosure [tr] = [end_state tr]
getClosure (tr:trs) = end_state tr : getClosure trs
--Get the ?-closure of a given state
eclosure :: Automaton -> Int -> [Int]
eclosure a s
= s : List.concat
[ eclosure a st
| st <- getClosure . List.filter (equal_transaction Nothing s)
$ transactions a ]
Run Code Online (Sandbox Code Playgroud)
问题是,如果闭包中存在循环,则代码将永远运行。我了解这种行为背后的原因,但我不知道如何解决。请你帮助我好吗?
| 归档时间: |
|
| 查看次数: |
431 次 |
| 最近记录: |