automata-0.1.0.0: automata

Safe HaskellNone
LanguageHaskell2010

Automata.Nfsa

Contents

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 details

Defined in Automata.Internal

Methods

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

Defined in Automata.Internal

Methods

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

rejection :: Bounded t => Nfsa t Source #

empty :: Bounded t => Nfsa t Source #

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