module FST.Reversal ( reversal
) where
import FST.Automaton
import Data.Array
reversal :: Eq a => Automaton a -> Automaton a
reversal automaton = reverseTrans (rename (transitionTable automaton)
(alphabet automaton)
(finals automaton)
(initials automaton)
(firstState automaton))
reverseTrans :: Eq a => Automaton a -> Automaton a
reverseTrans automaton = let bs = (firstState automaton, lastState automaton)
table = assocs $ accumArray (\tl1 tl2 -> tl1 ++ tl2) []
bs [(s1,[(a,s)]) | (s,tl) <- transitionTable automaton,
(a,s1) <- tl]
in construct bs table (alphabet automaton) (initials automaton) (finals automaton)