Я реализую недетерминированный конечный автомат в 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 ]
Проблема в том, что если в замыкании есть цикл, код работает вечно. Я понимаю причины такого поведения, но не знаю, как это исправить. Не могли бы вы мне помочь?
known = {s}
иedge = {s}
и на каждом шаге вы заменяетеedge
наgetClosure edge - known
(в разумной интерпретации) и одновременно заменяетеknown
наunion known (getClosure edge)
. Затем продолжайте, покаedge
не станет пустым.known
тогда ваше эпсилон-замыкание. - person Dan Robertson   schedule 18.02.2018