Automata.Internal

Types

data Dfsa t

Deterministic Finite State Automaton.

The start state is always zero.

Constructors

Dfsa

Fields

• dfaTransition :: !(Array (Map t Int))

  Given a state and transition, this field tells you what state to go to next. The length of this array must match the total number of states.

• dfaFinal :: !(Set Int)

  A string that ends in any of these set of states is considered to have been accepted by the grammar.

Instances

Eq t => Eq (Dfsa t)

Defined in Automata.Internal

Methods

(==) :: Dfsa t -> Dfsa t -> Bool

(/=) :: Dfsa t -> Dfsa t -> Bool

(Bounded t, Enum t, Show t) => Show (Dfsa t)

Defined in Automata.Internal

Methods

showsPrec :: Int -> Dfsa t -> ShowS

show :: Dfsa t -> String

showList :: [Dfsa t] -> ShowS

(Ord t, Enum t, Bounded t) => Semiring (Dfsa t)

This uses union for plus and intersection for times.

Defined in Automata.Internal

Methods

plus :: Dfsa t -> Dfsa t -> Dfsa t

zero :: Dfsa t

times :: Dfsa t -> Dfsa t -> Dfsa t

one :: Dfsa t

data Nfsa t

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.

Constructors

Nfsa

Fields

• nfaTransition :: !(Array (TransitionNfsa t))

  Given a state and transition, this field tells you what state to go to next. The length of this array must match the total number of states. The data structure inside is a diet map. This is capable of collapsing adjacent key-value pairs into ranges.

• nfaFinal :: !(Set Int)

  A string that ends in any of these set of states is considered to have been accepted by the grammar.

Instances

(Bounded t, Enum t, Show t) => Show (Nfsa t)

Defined in Automata.Internal

Methods

showsPrec :: Int -> Nfsa t -> ShowS

show :: Nfsa t -> String

showList :: [Nfsa t] -> ShowS

Bounded t => Semiring (Nfsa t)

This uses union for plus and append for times.

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

data TransitionNfsa t

Constructors

TransitionNfsa

Fields

• transitionNfsaEpsilon :: !(Set Int)
• transitionNfsaConsume :: !(Map t (Set Int))

Instances

Eq t => Eq (TransitionNfsa t)

Defined in Automata.Internal

Methods

(==) :: TransitionNfsa t -> TransitionNfsa t -> Bool

(/=) :: TransitionNfsa t -> TransitionNfsa t -> Bool

(Bounded t, Enum t, Show t) => Show (TransitionNfsa t)

Defined in Automata.Internal

Methods

showsPrec :: Int -> TransitionNfsa t -> ShowS

show :: TransitionNfsa t -> String

showList :: [TransitionNfsa t] -> ShowS

Builder Types

newtype State s

Constructors

State Int

data Epsilon

Constructors

Epsilon !Int !Int

NFA Functions

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

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.

toDfsaMapping :: forall t. (Ord t, Bounded t, Enum t) => Nfsa t -> (Map (Set Int) Int, Dfsa t)

append :: Nfsa t -> Nfsa t -> Nfsa t

empty :: Bounded t => Nfsa t

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

rejectionNfsa :: Bounded t => Nfsa t

Docs for this are at Automata.Nfsa.rejection.

unionNfsa :: Bounded t => Nfsa t -> Nfsa t -> Nfsa t

Docs for this are at Automata.Nfsa.union.

epsilonClosure :: Array (TransitionNfsa t) -> Set Int -> Set Int

DFA Functions

union :: (Ord t, Bounded t, Enum t) => Dfsa t -> Dfsa t -> Dfsa t

Accepts input that is accepted by either of the two argument DFAs. This is also known as synchronous composition in the literature.

intersection :: (Ord t, Bounded t, Enum t) => Dfsa t -> Dfsa t -> Dfsa t

Accepts input that is accepted by both of the two argument DFAs. This is also known as completely synchronous composition in the literature.

acceptance :: Bounded t => Dfsa t

Automaton that accepts all input. This is the identity for intersection.

rejection :: Bounded t => Dfsa t

Automaton that rejects all input. This is the identity for union.

minimize :: (Ord t, Bounded t, Enum t) => Array (Map t Int) -> Set Int -> Dfsa t

This uses Hopcroft's Algorithm. It is like a smart constructor for Dfsa.

minimizeMapping :: forall t. (Ord t, Bounded t, Enum t) => Array (Map t Int) -> Set Int -> (Map Int Int, Dfsa t)

This uses Hopcroft's Algorithm. It also provides the mapping from old state number to new state number. We need this mapping for a special NFST to DFST minimizer.

composeMapping :: (Ord t, Bounded t, Enum t) => (Bool -> Bool -> Bool) -> Dfsa t -> Dfsa t -> (Map (Int, Int) Int, Dfsa t)