вычисление ε-замыкания NFA в Haskell

Я реализую недетерминированный конечный автомат в Haskell, и я пытаюсь реализовать функцию, которая вычисляет замыкание эпсилон. С этой целью 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 

при закрытии:

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

Проблема в том, что если в замыкании есть цикл, код работает вечно. Я понимаю причины такого поведения, но не знаю, как это исправить. Не могли бы вы мне помочь?


person elena    schedule 18.02.2018    source источник
comment
Похоже, вы примерно понимаете, что происходит, поэтому вот набросок: используйте наборы вместо списков, таким образом вы избегаете дубликатов (и знаете, не добавили ли вы ничего нового). Теперь выполните стандартный обход в ширину по графу после всех эпсилон-переходов. Т.е. начинайте с known = {s} и edge = {s} и на каждом шаге вы заменяете edge на getClosure edge - known (в разумной интерпретации) и одновременно заменяете known на union known (getClosure edge). Затем продолжайте, пока edge не станет пустым. known тогда ваше эпсилон-замыкание.   -  person Dan Robertson    schedule 18.02.2018
comment
@DanRobertson Я думаю, вы должны написать это как ответ.   -  person Paul Johnson    schedule 18.02.2018
comment
Вот подробное исследование. stackoverflow.com/questions/28549336/   -  person Gurkenglas    schedule 19.02.2018