Copyright | (c) Karl Cronburg 2018 |
---|---|
License | BSD3 |
Maintainer | karl@cs.tufts.edu |
Stability | experimental |
Portability | POSIX |
Safe Haskell | None |
Language | Haskell2010 |
Synopsis
- data Automata e s i = Automata {}
- type AutomataEdge t = (Bool, Set t)
- type Transition e i = (i, AutomataEdge e, i)
- tFrom :: Transition e i -> i
- tTo :: Transition e i -> i
- tEdge :: Transition e i -> Set e
- transitionAlphabet :: HashSet (a1, (a2, [b]), c) -> [b]
- compress :: (Eq i, Eq e, Hashable i, Hashable e) => Set (Transition e i) -> Set (Transition e i)
- xor :: Bool -> Bool -> Bool
- transitionMember :: (Eq i, Hashable e, Eq e) => (i, e, i) -> Set (Transition e i) -> Bool
- edgeMember :: (Eq a, Hashable a) => a -> (Bool, HashSet a) -> Bool
- data Result
- validStartState :: (Eq i, Hashable i) => Automata e s i -> Bool
- validFinalStates :: (Eq i, Hashable i) => Automata e s i -> Bool
- validTransitions :: forall e s i. (Hashable e, Hashable i, Eq e, Eq i) => Automata e s i -> Bool
- type Config i = Set i
- closureWith :: forall e s i. (Hashable e, Hashable i, Eq e, Eq i) => (e -> Bool) -> Automata e s i -> Config i -> Config i
- move :: forall e s i. (Hashable e, Hashable i, Eq i, Eq e) => Automata e s i -> Config i -> e -> Config i
- complementMember :: (Hashable i, Eq i, Hashable e, Eq e) => (i, i) -> Set (Transition e i) -> Bool
- moveComplement :: forall e s i. (Hashable e, Hashable i, Eq i, Eq e) => Automata e s i -> Config i -> Config i
Documentation
An automaton with edges e
, symbols s
, and state indices i
type AutomataEdge t = (Bool, Set t) Source #
Edge label of an automaton, on which we traverse if we match
on one of the tokens t
in the set. The boolean is for negation
of the set.
type Transition e i = (i, AutomataEdge e, i) Source #
A triplet with an edge alphabet of e
and node states of i
.
tFrom :: Transition e i -> i Source #
The from-node component of a Transition
tTo :: Transition e i -> i Source #
The to-node component of a Transition
tEdge :: Transition e i -> Set e Source #
The set of edge characters in e
of a Transition
transitionAlphabet :: HashSet (a1, (a2, [b]), c) -> [b] Source #
Determine the edge-label alphabet of a set of transitions.
compress :: (Eq i, Eq e, Hashable i, Hashable e) => Set (Transition e i) -> Set (Transition e i) Source #
Compress a set of transitions such that every pair of (start,end) states appears at most once in the set.
transitionMember :: (Eq i, Hashable e, Eq e) => (i, e, i) -> Set (Transition e i) -> Bool Source #
Is the given transition triplet (with a single e
character as the edge
edge label) in some set of transitions? Note that we need to handle complement
sets here, in case the given e
is in the complement of one of the
transitions in the set.
edgeMember :: (Eq a, Hashable a) => a -> (Bool, HashSet a) -> Bool Source #
Is the given character s
accepted by the given edge label?
validFinalStates :: (Eq i, Hashable i) => Automata e s i -> Bool Source #
Are all of the ending states valid?
validTransitions :: forall e s i. (Hashable e, Hashable i, Eq e, Eq i) => Automata e s i -> Bool Source #
Can all of the nodes as defined by the set of transitions be found
in the set of allowable states _S
?
type Config i = Set i Source #
An automaton configuration is the set of state (indices) your can currently be in.
closureWith :: forall e s i. (Hashable e, Hashable i, Eq e, Eq i) => (e -> Bool) -> Automata e s i -> Config i -> Config i Source #
move :: forall e s i. (Hashable e, Hashable i, Eq i, Eq e) => Automata e s i -> Config i -> e -> Config i Source #
Consume the e
character given, based on the fact that we are currently
in some 'Config i' of states, resulting in a new config consisting of the
states that we can get to by doing so.
complementMember :: (Hashable i, Eq i, Hashable e, Eq e) => (i, i) -> Set (Transition e i) -> Bool Source #
Whether or not (a, (True, _), b) is a transition in our set of transitions.