Language.HaLex.Minimize

Minimization of the States of a Deterministica Finite Automata

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

Minimization

minimizeDfa

Arguments

:: (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

Arguments

:: (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

Arguments

:: 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

Arguments

:: (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

Arguments

:: Eq st

=> Dfa st sy

Original Dfa

-> Ndfa st sy

Resulting Ndfa

Reverse a Dfa

reverseDfaAsDfa

Arguments

:: (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

Arguments

:: Eq st

=> Ndfa st sy

Original Ndfa

-> Ndfa st sy

Resulting Ndfa

Reverse a Ndfa