Language.HaLex.Minimize
 Portability portable Stability provisional Maintainer jas@di.uminho.pt
 Contents Minimization Reversing Automata
Description

Minimization of the States of a Deterministica Finite Automata

Code Included in the Lecture Notes on Language Processing (with a functional flavour).

Synopsis
 minimizeDfa :: (Eq sy, Ord st) => Dfa st sy -> Dfa [[st]] sy stdMinimizeDfa :: (Ord st, Ord sy) => Dfa st sy -> Dfa [st] sy minimizeExp :: Ord st => Dfa st sy -> Dfa [st] sy minimizeNdfa :: (Eq sy, Ord st) => Ndfa st sy -> Dfa [[st]] sy reverseDfa :: Eq st => Dfa st sy -> Ndfa st sy reverseDfaAsDfa :: (Ord st, Eq sy) => Dfa st sy -> Dfa [st] sy reverseNdfa :: Eq st => Ndfa st sy -> Ndfa st sy
Minimization
 minimizeDfa Source
 :: (Eq sy, Ord st) => Dfa st sy Original Dfa -> Dfa [[st]] sy Equivalent Minimized Dfa Minimize the number of states of a given Dfa. This function uses Brzozowski's algorithm
 stdMinimizeDfa Source
 :: (Ord st, Ord sy) => Dfa st sy Original Dfa -> Dfa [st] sy Equivalent Minimized Dfa Minimize the number of states of a given Dfa. This minimization algorithm is described in "An Introduction to Formal Languages and Automata", Peter Linz, 3rd Ed. Jones and Bartlett Publishers
 minimizeExp Source
 :: Ord st => Dfa st sy Original Dfa -> Dfa [st] sy Equivalent Minimized Dfa Minimize the number of states of a given Dfa. (a third algorithm)
 minimizeNdfa Source
 :: (Eq sy, Ord st) => Ndfa st sy Original Ndfa -> Dfa [[st]] sy Equivalent Minimized Dfa Minimize the number of states of a given Ndfa. This function uses Brzozowski's algorithm
Reversing Automata
 reverseDfa Source
 :: Eq st => Dfa st sy Original Dfa -> Ndfa st sy Resulting Ndfa Reverse a Dfa
 reverseDfaAsDfa Source
 :: (Ord st, Eq sy) => Dfa st sy Orginal Dfa -> Dfa [st] sy Resulting Dfa Reverse a Dfa into a Dfa. It uses a Ndfa as an intermediate representation.
 reverseNdfa Source
 :: Eq st => Ndfa st sy Original Ndfa -> Ndfa st sy Resulting Ndfa Reverse a Ndfa