Safe HaskellSafe

GNFA

Description

Definition, construction and reduction of GNFAs

Synopsis

Documentation

type Transition a = Map (a, a) Regexp #

data GNFA a #

A generalised nondeterministic finite automaton in the special form:

  • 1 single start state, with regexp arrows going to every other state, but no incoming arrows;
  • 1 single accept state, with regexp arrows coming in from every other state but with no outgoing arrows;
  • regexp arrows from any state except the start state to any state except the accept state - the empty set arrows can be filled with fillTransition.

Constructors

GNFA 

Fields

  • states :: Set a

    A finite set of states, NOT including the start and accept states

  • transition :: Transition a

    Transition function, mapping Q{q_accept} x Q{q_start} to a regexp

  • startState :: a

    The start state, no incoming arrows

  • acceptState :: a

    The accept state, no exiting arrows

convert :: Ord a => GNFA a -> Regexp #

Convert a GNFA to a regexp by ripping out states until only the start and accept states remain.

  • If the start and accept states are the only states left, then the regexp on the start -> accept arrow is what we want.
  • Otherwise find a state q_rip that is not the start or accept state, and for q_i ->(R1) q_rip, q_rip ->(R2) q_rip, q_rip ->(R3) q_j, q_i ->(R4) q_j, we can remove the state q_rip and replace the regexp on the q_i -> q_j arrow with R1 R2* R3 ∪ R4 to get an equivalent GNFA with 1 less state.

fillTransition #

Arguments

:: Ord a 
=> Set a

The set of states, excluding the start and accept states

-> a

The start state

-> a

The accept state

-> Transition a

The transition map to be filled

-> Transition a

The transition map filled with ∅ arrows where missing, using the fact that ∅ acts as the identity with respect to taking unions.

Fill in the map of transition arrows with ∅ arrows.