HaLeX-1.1: HaLeX enables modelling, manipulation and animation of regular languagesSource codeContentsIndex
Language.HaLex.Minimize
Portabilityportable
Stabilityprovisional
Maintainerjas@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
minimizeDfaSource
:: (Eq sy, Ord st)
=> Dfa st syOriginal Dfa
-> Dfa [[st]] syEquivalent Minimized Dfa
Minimize the number of states of a given Dfa. This function uses Brzozowski's algorithm
stdMinimizeDfaSource
:: (Ord st, Ord sy)
=> Dfa st syOriginal Dfa
-> Dfa [st] syEquivalent 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

minimizeExpSource
:: Ord st
=> Dfa st syOriginal Dfa
-> Dfa [st] syEquivalent Minimized Dfa

Minimize the number of states of a given Dfa.

(a third algorithm)

minimizeNdfaSource
:: (Eq sy, Ord st)
=> Ndfa st syOriginal Ndfa
-> Dfa [[st]] syEquivalent Minimized Dfa
Minimize the number of states of a given Ndfa. This function uses Brzozowski's algorithm
Reversing Automata
reverseDfaSource
:: Eq st
=> Dfa st syOriginal Dfa
-> Ndfa st syResulting Ndfa
Reverse a Dfa
reverseDfaAsDfaSource
:: (Ord st, Eq sy)
=> Dfa st syOrginal Dfa
-> Dfa [st] syResulting Dfa
Reverse a Dfa into a Dfa. It uses a Ndfa as an intermediate representation.
reverseNdfaSource
:: Eq st
=> Ndfa st syOriginal Ndfa
-> Ndfa st syResulting Ndfa
Reverse a Ndfa
Produced by Haddock version 2.3.0