module FST.EpsilonFreeT (
epsilonfree
) where
import FST.Transducer
import Data.List (partition)
epsilonfree :: Eq a => Transducer a -> Transducer a
epsilonfree transducer
= epsFree transducer ([],initials transducer) [] []
epsFree :: Eq a => Transducer a -> ([StateTy],[StateTy]) -> FinalStates ->
[(StateTy,[(Relation a,StateTy)])] -> Transducer a
epsFree transducer (_,[]) fs table
= construct (firstState transducer, lastState transducer)
table (alphabet transducer) (initials transducer) fs
epsFree transducer (done,(s:undone)) fs table
= let (newtl, fsB) = stateEpsRemove [] (transitionList transducer s)
([], False)
newSts = filter (`notElem` s:done) (map snd newtl)
in epsFree transducer (s:done, newSts ++ undone)
(if fsB || isFinal transducer s then s:fs else fs)
((s,newtl):table)
where
epsTransitions :: Eq a => ((Symbol a, Symbol a), t) -> Bool
epsTransitions (eps, _) = eps == (Eps, Eps)
stateEpsRemove _ [] (tl, fsB) = (tl,fsB)
stateEpsRemove history tlist (tl, fsB)
= case partition epsTransitions tlist of
([], ntl) -> (tl ++ ntl, fsB)
(epstl, ntl) -> let newSts = filter (`notElem` history) (map snd epstl)
fsBnew = any (isFinal transducer) newSts
in stateEpsRemove (newSts ++ history)
(concatMap (transitionList transducer) newSts)
(ntl ++ tl, fsB || fsBnew)