A package containing various binary and unary operations on automaton
objects.
Documentation
This package offers a lot of standard transformations on automata objects:
- concatenation:
- concatenate two automaton so that
L(A.B) = L(A).L(B),
- union:
- union of two automaton ,
L(A+B) = L(A) U L(B),
- star closure:
- the standard kleene-closure operator,
L(A*) = epsilon U L(A).L(A*)
- minimization:
- compute the minimal - canonical - DFA from a given DFA
- determinization:
- make an automaton deterministic: Each state has at most one transition labelled with
a given letter,
- epsilon transition removals:
- Removes transition labelled with
null while keeping the same language
- complementation:
- complement the language over the alphabet of the automaton, for an alphabet
X,
L(-A-)=X*\L(A)
- synchronization product:
- Compute the synchronization product of two automaton, also named mixed product
- parametric intersection:
- compute the intersection of two automaton with a synchronization object,
- normalization:
- normalize an automaton: One start state, one end state, no incoming transitions
on start state
- prefix closure:
- an automaton with all states made terminal
- pruning:
- remove all states that are neither accessible from a start state nor can
reach a terminal state
- projection over an alphabet:
- remove all transitions from an automaton that are not in an alphabet
- reversal:
- reverse the language of an automaton so that it recognizes mirrored words
from the original automaton.
- shuffle product:
- compute all possible interleavings of words from two automaton
These transformations are usually not very efficient so that applying any one of them
on large automaton may yield poor performances. Possible exceptions are the epsilon
transition removal, synchronization products and intersections which compute the
results using reachable states set only so that the cartesian product of the
involved automata is not computed.
Work is underway to improve ultimately performance of this library.