automata-0.1.0.0: automata

Automata.Nfsa

Synopsis

# Types

data Nfsa t Source #

Non-Deterministic Finite State Automaton.

Some notes on the implementation and design:

• You can transition to any non-negative number of states (including 0).
• There is only one start state.
• We use the Thompson encoding. This means that there is an epsilon transition that consumes no input.
• We store the full epsilon closure for every state. This means that, when evaluating the NFA, we do not ever need to compute the closure.
• There is no Eq instance for NFA. In general, this can take exponential time. If you really need to do this, convert the NFA to a DFA.

Invariants:

• The start state is always the state at position 0.
• The length of nfaTransition is given by nfaStates.
Instances
 (Bounded t, Enum t, Show t) => Show (Nfsa t) Source # Instance detailsDefined in Automata.Internal MethodsshowsPrec :: Int -> Nfsa t -> ShowS #show :: Nfsa t -> String #showList :: [Nfsa t] -> ShowS # Bounded t => Semiring (Nfsa t) Source # This uses union for plus and append for times. Instance detailsDefined in Automata.Internal Methodsplus :: Nfsa t -> Nfsa t -> Nfsa t #zero :: Nfsa t #times :: Nfsa t -> Nfsa t -> Nfsa t #one :: Nfsa t #

# Conversion

toDfsa :: (Ord t, Bounded t, Enum t) => Nfsa t -> Dfsa t Source #

Convert an NFSA to a DFSA. For certain inputs, this causes the number of states to blow up expontentially, so do not call this on untrusted input.

# Evaluation

evaluate :: (Foldable f, Ord t) => Nfsa t -> f t -> Bool Source #

# Composition

append :: Nfsa t -> Nfsa t -> Nfsa t Source #

union :: Bounded t => Nfsa t -> Nfsa t -> Nfsa t Source #

# Special NFA

empty :: Bounded t => Nfsa t Source #

Automaton that accepts the empty string and rejects all other strings. This is the identity for append.