Calculation of NFA ε-closure in haskell

I am implementing a non-deterministic state machine in Haskell and I am trying to implement a function that evaluates epsilon closure. To this end, NFA is implemented as:

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 

while short circuit:

--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 ]

The problem is that if there is a loop in the closure, the code runs forever. I understand the reasons for this behavior, but I do not know how to fix it. Could you help me?

+4
source share

Source: https://habr.com/ru/post/1693786/


All Articles