LTK.FSA

The purpose of this module is to define an interface to a generic, reusable impementation of finite-state automata (FSAs). The primary motivation for this is to allow for efficient analysis of stringsets in a linguistic context, although the nature of the project should allow more general use.

Documentation

data FSA n e

A finite-state automaton (FSA) is represented by a directed graph, the edges of which are labelled by formal symbols.

Constructors

FSA

Fields

• sigma :: Set e

  Since: 0.3

• transitions :: Set (Transition n e)
• initials :: Set (State n)
• finals :: Set (State n)
• isDeterministic :: Bool

Instances

HasAlphabet (FSA n)

Defined in LTK.FSA

Methods

alphabet :: FSA n e -> Set e

(Ord e, Ord n) => Eq (FSA n e)

Defined in LTK.FSA

Methods

(==) :: FSA n e -> FSA n e -> Bool

(/=) :: FSA n e -> FSA n e -> Bool

(Ord e, Ord n) => Ord (FSA n e)

Defined in LTK.FSA

Methods

compare :: FSA n e -> FSA n e -> Ordering

(<) :: FSA n e -> FSA n e -> Bool

(<=) :: FSA n e -> FSA n e -> Bool

(>) :: FSA n e -> FSA n e -> Bool

(>=) :: FSA n e -> FSA n e -> Bool

max :: FSA n e -> FSA n e -> FSA n e

min :: FSA n e -> FSA n e -> FSA n e

(Read e, Read n, Ord e, Ord n) => Read (FSA n e)

Defined in LTK.FSA

Methods

readsPrec :: Int -> ReadS (FSA n e)

readList :: ReadS [FSA n e]

readPrec :: ReadPrec (FSA n e)

readListPrec :: ReadPrec [FSA n e]

(Show e, Show n) => Show (FSA n e)

Defined in LTK.FSA

Methods

showsPrec :: Int -> FSA n e -> ShowS

show :: FSA n e -> String

showList :: [FSA n e] -> ShowS

(Enum n, Ord n, Ord e) => Semigroup (FSA n e)

Defined in LTK.FSA

Methods

(<>) :: FSA n e -> FSA n e -> FSA n e

sconcat :: NonEmpty (FSA n e) -> FSA n e

stimes :: Integral b => b -> FSA n e -> FSA n e

(Enum n, Ord n, Ord e) => Monoid (FSA n e)

Defined in LTK.FSA

Methods

mempty :: FSA n e

mappend :: FSA n e -> FSA n e -> FSA n e

mconcat :: [FSA n e] -> FSA n e

(NFData n, NFData e) => NFData (FSA n e)

Defined in LTK.FSA

Methods

rnf :: FSA n e -> ()

(Enum n, Ord n, Ord e) => Container (FSA n e) [e]

Defined in LTK.FSA

Methods

isIn :: FSA n e -> [e] -> Bool

isNotIn :: FSA n e -> [e] -> Bool

contains :: [e] -> FSA n e -> Bool

doesNotContain :: [e] -> FSA n e -> Bool

isEmpty :: FSA n e -> Bool

union :: FSA n e -> FSA n e -> FSA n e

intersection :: FSA n e -> FSA n e -> FSA n e

difference :: FSA n e -> FSA n e -> FSA n e

symmetricDifference :: FSA n e -> FSA n e -> FSA n e

empty :: FSA n e

insert :: [e] -> FSA n e -> FSA n e

singleton :: [e] -> FSA n e

isSubsetOf :: FSA n e -> FSA n e -> Bool

isSupersetOf :: FSA n e -> FSA n e -> Bool

isProperSubsetOf :: FSA n e -> FSA n e -> Bool

isProperSupersetOf :: FSA n e -> FSA n e -> Bool

states :: (Ord e, Ord n) => FSA n e -> Set (State n)

The collection of all states in an FSA.

isNull :: (Ord e, Ord n) => FSA n e -> Bool

True iff the input accepts no strings.

follow :: (Ord n, Ord e) => FSA n e -> [Symbol e] -> State n -> Set (State n)

The generalized \(\delta\) function, follow each symbol in a string in order.

Since: 0.2

Constructing simple automata

totalWithAlphabet :: (Ord e, Enum n, Ord n) => Set e -> FSA n e

An automaton accepting every string over a given alphabet.

emptyWithAlphabet :: (Ord e, Enum n, Ord n) => Set e -> FSA n e

An automaton accepting no strings over a given alphabet.

emptyLanguage :: (Ord e, Ord n, Enum n) => FSA n e

A specialization of emptyWithAlphabet where the alphabet is itself empty.

singletonWithAlphabet :: (Ord e, Enum n, Ord n) => Set e -> [e] -> FSA n e

An automaton that accepts only the given string, over a given alphabet.

singletonLanguage :: (Ord e, Enum n, Ord n) => [e] -> FSA n e

An automaton that accepts only the given string, over the minimal alphabet required to represent this string.

Derived automata

brzozowskiDerivative :: (Ord e, Ord n) => [e] -> FSA n e -> FSA n e

Return an FSA representing possible continuations from a given sequence of symbols. If the input automaton is not complete then the output may have no states when given incompatible input.

Since: 1.0

quotLeft :: (Ord e, Ord n1, Ord n2) => FSA n1 e -> FSA n2 e -> FSA (Maybe (Either n1 ()), Maybe n2) e

Return an FSA representing possible continuations in the second language from strings in the first language. In other words, quotLeft a b returns \(\{w : x\in a, xw\in b\}\).

Since: 1.0

quotMid :: (Ord e, Ord n1, Ord n2, Ord n3) => FSA n1 e -> FSA n2 e -> FSA n3 e -> FSA Integer e

quotMid a b c is \(\{wz : wx\in a, yx\in b, yz\in c\}\). This lifts strings to a group, placing b-inverse between a and c. The time complexity of this function is abysmal, performing a left and a right quotient for each state in b.

Since: 1.0

quotRight :: (Ord e, Ord n1, Ord n2) => FSA n1 e -> FSA n2 e -> FSA Integer e

Return an FSA representing possible strings in the first language which end with a string in the second language. In other words, quotRight a b is \(\{w : wx\in a, x\in b\}\).

Since: 1.0

kleeneClosure :: (Ord n, Ord e) => FSA n e -> FSA (Either n Bool) e

The Kleene Closure of an automaton is the free monoid under concatenation generated by all strings in the automaton's represented stringset. The resulting automaton is nondeterministic.

powersetGraph :: (Ord e, Ord n) => FSA n e -> FSA (Set n) e

Given an automaton \(M\) with stateset \(Q\), the powerset graph of \(M\) is an automaton with stateset in the powerset of \(Q\). From a node \(\{q_1,q_2,\ldots,q_n\}\), there is an edge labelled \(\sigma\) that leads to \(\{\delta(q_1,\sigma), \delta(q_2,\sigma), \ldots, \delta(q_n, \sigma)\}\), where \(\delta\) is the transition function of the input. The initial state is \(Q\), and the result is complete.

syntacticMonoid :: (Ord e, Ord n) => FSA n e -> FSA ([Maybe n], [Symbol e]) e

Given an automaton \(M\) with stateset \(Q\), the syntactic monoid of \(M\) is an automaton with stateset in \((Q\rightarrow Q)\). Here these functions are represented by lists, where \(q_i\) maps to the \(i^\text{th}\) element of the list. From a node \(\langle q_1,q_2,\ldots,q_n\rangle\), there is an edge labelled \(\sigma\) that leads to \(\langle\delta(q_1,\sigma), \delta(q_2,\sigma), \ldots, \delta(q_n, \sigma)\rangle\), where \(\delta\) is the transition function of the input. The initial state is the identity function, and the result is complete.

residue :: (Ord n, Ord e, Enum n) => FSA n e -> FSA n e -> FSA n e

(residue a b) is equivalent to (difference a b). In the context of an approximation and its source, represents the strings accepted by the approximation that should not be.

coresidue :: (Ord n, Ord e, Enum n) => FSA n e -> FSA n e -> FSA n e

(coresidue a b) is equivalent to (complement (residue a b)). In the context of an approximation and its source, represents unmet constraints of the source.

Primitive ideals

primitiveIdeal2 :: (Ord n, Ord e) => FSA (n, [Symbol e]) e -> State (n, [Symbol e]) -> Set (State (n, [Symbol e]))

The primitive two-sided ideal.

Since: 0.2

primitiveIdealL :: (Ord n, Ord e) => FSA (n, [Symbol e]) e -> State (n, [Symbol e]) -> Set (State (n, [Symbol e]))

The primitive left ideal.

Since: 0.2

primitiveIdealR :: (Ord n, Ord e) => FSA n e -> State n -> Set (State n)

The primitive right ideal.

Since: 0.2

Transformations

flatIntersection :: (Enum n, Ord n, NFData n, Ord e, NFData e) => [FSA n e] -> FSA n e

Intersect all given automata, in parallel if possible. An empty intersection is undefined. In theory it should be the total language over the total alphabet, but the latter cannot be defined. Intermediate results are evaluated to normal form.

flatUnion :: (Enum n, Ord n, NFData n, Ord e, NFData e) => [FSA n e] -> FSA n e

Union all given automata, in parallel if possible. An empty union is defined as the empty language over an empty alphabet. Intermediate results are evaluated to normal form.

reverse :: (Ord e, Ord n) => FSA n e -> FSA n e

The reversal of an automaton accepts the reversals of all strings accepted by the original.

complement :: (Ord e, Ord n) => FSA n e -> FSA (Set n) e

Returns an FSA accepting all and only those strings not accepted by the input.

complementDeterministic :: (Ord e, Ord n) => FSA n e -> FSA n e

Returns the complement of a deterministic FSA. The precondition that the input is deterministic is not checked.

determinize :: (Ord e, Ord n) => FSA n e -> FSA (Set n) e

Returns a deterministic automaton representing the same stringset as the potentially nondeterministic input.

Minimization

minimize :: (Ord e, Ord n) => FSA n e -> FSA (Set (Set n)) e

Returns a deterministic FSA recognizing the same stringset as the input, with a minimal number of states.

minimizeDeterministic :: (Ord e, Ord n) => FSA n e -> FSA (Set n) e

Returns a deterministic FSA recognizing the same stringset as the input, with a minimal number of states. The precondition that the input is deterministic is not checked.

normalize :: (Ord e, Ord n) => FSA n e -> FSA Integer e

Returns a normal form of the input. An FSA is in normal form if it is minimal and deterministic, and contains neither unreachable states nor nonaccepting sinks. Node labels are irrelevant, so Int is used as a small representation.

trimUnreachables :: (Ord e, Ord n) => FSA n e -> FSA n e

The input automaton with unreachable states removed.

Since: 1.0

Equivalence Classes

minimizeOver :: (Ord e, Ord n) => (FSA n e -> Set (Set (State n))) -> FSA n e -> FSA (Set n) e

Returns a non-necessarily deterministic FSA minimized over a given relation. Some, but not all, relations do guarantee deterministic output. The precondition that the input is deterministic is not checked.

nerode :: (Ord e, Ord n) => FSA n e -> Set (Set (State n))

Two strings \(u\) and \(v\) are equivalent iff for all strings \(w\), \(uw\) and \(vw\) lead to states in the same equivalence class.

hEquivalence :: (Ord n, Ord e) => FSA (n, [Symbol e]) e -> Set (Set (State (n, [Symbol e])))

Given an automaton whose syntactic monoid is \(M\), two strings \(u\) and \(v\) are equivalent if \(Mu=Mv\) and \(uM=vM\).

Since: 0.2

jEquivalence :: (Ord e, Ord n) => FSA ([Maybe n], [Symbol e]) e -> Set (Set (State ([Maybe n], [Symbol e])))

Given an automaton whose syntactic monoid is \(M\), two strings \(u\) and \(v\) are equivalent iff \(MuM=MvM\)

trivialUnder :: (FSA n e -> Set (Set (State n))) -> FSA n e -> Bool

An automaton is considered trivial under some equivalence relation if each of its equivalence classes is singleton.

Since: 0.2

Alphabetic Transformations

extendAlphabetTo :: (Ord a, Ord b) => Set b -> FSA a b -> FSA (Maybe Integer, Maybe a) b

Add missing symbols to the alphabet of an automaton. The result is an automaton with at least the provided alphabet that licenses exactly the same set of strings as the input.

semanticallyExtendAlphabetTo :: (Ord a, Ord b) => Set b -> FSA a (Maybe b) -> FSA a (Maybe b)

Add missing symbols to the alphabet of an automaton. As the symbol Nothing is taken to represent any symbol not currently in the alphabet, new edges are added in parallel to existing edges labelled by Nothing.

tierify :: (Ord a, Ord b) => Set b -> FSA a (Maybe b) -> FSA a (Maybe b)

Convert a semantic automaton that represents a Local constraint into a new one that represents the same constraint in the associated Tier-Local class.

contractAlphabetTo :: (Ord a, Ord b) => Set b -> FSA a b -> FSA a b

Remove symbols from the alphabet of an automaton.

forceAlphabetTo :: (Ord a, Ord b) => Set b -> FSA a b -> FSA (Maybe Integer, Maybe a) b

Ignore the alphabet of an automaton and use a given alphabet instead.

desemantify :: (Ord a, Ord b) => FSA a (Maybe b) -> FSA a b

Remove the semantic Nothing edges from an automaton and reflect this change in the type.

renameSymbolsBy :: (Ord e, Ord e1, Ord n) => (e -> e1) -> FSA n e -> FSA n e1

Transform the edge labels of an automaton using a given function. If this function is not injective, the resulting FSA may not be deterministic even if the original was.

Transformations of State labels

renameStatesBy :: (Ord e, Ord n, Ord n1) => (n -> n1) -> FSA n e -> FSA n1 e

Transform the node labels of an automaton using a given function. If this function is not injective, the resulting FSA may not be deterministic even if the original was.

renameStates :: (Ord e, Ord n, Ord n1, Enum n1) => FSA n e -> FSA n1 e

Equivalent to renameStatesBy \(f\), where \(f\) is an arbitrary injective function.

Miscellaneous

data State n

A vertex of the graph representation of an FSA is a State, which can be labelled with any arbitrary value, so long as every vertex of a single automaton is labelled with a distinct value of the same type.

Constructors

State

Fields

• nodeLabel :: n

Instances

Monad State

Defined in LTK.FSA

Methods

(>>=) :: State a -> (a -> State b) -> State b

(>>) :: State a -> State b -> State b

return :: a -> State a

Functor State

Defined in LTK.FSA

Methods

fmap :: (a -> b) -> State a -> State b

(<$) :: a -> State b -> State a

Applicative State

Defined in LTK.FSA

Methods

pure :: a -> State a

(<*>) :: State (a -> b) -> State a -> State b

liftA2 :: (a -> b -> c) -> State a -> State b -> State c

(*>) :: State a -> State b -> State b

(<*) :: State a -> State b -> State a

Eq n => Eq (State n)

Defined in LTK.FSA

Methods

(==) :: State n -> State n -> Bool

(/=) :: State n -> State n -> Bool

Ord n => Ord (State n)

Defined in LTK.FSA

Methods

compare :: State n -> State n -> Ordering

(<) :: State n -> State n -> Bool

(<=) :: State n -> State n -> Bool

(>) :: State n -> State n -> Bool

(>=) :: State n -> State n -> Bool

max :: State n -> State n -> State n

min :: State n -> State n -> State n

Read n => Read (State n)

Defined in LTK.FSA

Methods

readsPrec :: Int -> ReadS (State n)

readList :: ReadS [State n]

readPrec :: ReadPrec (State n)

readListPrec :: ReadPrec [State n]

Show n => Show (State n)

Defined in LTK.FSA

Methods

showsPrec :: Int -> State n -> ShowS

show :: State n -> String

showList :: [State n] -> ShowS

Semigroup n => Semigroup (State n)

Defined in LTK.FSA

Methods

(<>) :: State n -> State n -> State n

sconcat :: NonEmpty (State n) -> State n

stimes :: Integral b => b -> State n -> State n

Monoid n => Monoid (State n)

Defined in LTK.FSA

Methods

mempty :: State n

mappend :: State n -> State n -> State n

mconcat :: [State n] -> State n

NFData n => NFData (State n)

Defined in LTK.FSA

Methods

rnf :: State n -> ()

data Symbol e

The label of a Transition.

Constructors

Epsilon

The edge may be taken without consuming input.

Symbol e

The edge requires consuming this symbol.

Instances

Functor Symbol

Defined in LTK.FSA

Methods

fmap :: (a -> b) -> Symbol a -> Symbol b

(<$) :: a -> Symbol b -> Symbol a

Eq e => Eq (Symbol e)

Defined in LTK.FSA

Methods

(==) :: Symbol e -> Symbol e -> Bool

(/=) :: Symbol e -> Symbol e -> Bool

Ord e => Ord (Symbol e)

Defined in LTK.FSA

Methods

compare :: Symbol e -> Symbol e -> Ordering

(<) :: Symbol e -> Symbol e -> Bool

(<=) :: Symbol e -> Symbol e -> Bool

(>) :: Symbol e -> Symbol e -> Bool

(>=) :: Symbol e -> Symbol e -> Bool

max :: Symbol e -> Symbol e -> Symbol e

min :: Symbol e -> Symbol e -> Symbol e

Read e => Read (Symbol e)

Defined in LTK.FSA

Methods

readsPrec :: Int -> ReadS (Symbol e)

readList :: ReadS [Symbol e]

readPrec :: ReadPrec (Symbol e)

readListPrec :: ReadPrec [Symbol e]

Show e => Show (Symbol e)

Defined in LTK.FSA

Methods

showsPrec :: Int -> Symbol e -> ShowS

show :: Symbol e -> String

showList :: [Symbol e] -> ShowS

NFData e => NFData (Symbol e)

Defined in LTK.FSA

Methods

rnf :: Symbol e -> ()

unsymbols :: (Collapsible s, Container c e, Monoid c) => s (Symbol e) -> c

Remove Epsilon from a Collapsible of Symbol and present the unwrapped results as a new Container.

data Transition n e

The edges of an FSA.

Constructors

Transition

Fields

• edgeLabel :: Symbol e
• source :: State n
• destination :: State n

Instances

Functor (Transition n)

Defined in LTK.FSA

Methods

fmap :: (a -> b) -> Transition n a -> Transition n b

(<$) :: a -> Transition n b -> Transition n a

(Eq e, Eq n) => Eq (Transition n e)

Defined in LTK.FSA

Methods

(==) :: Transition n e -> Transition n e -> Bool

(/=) :: Transition n e -> Transition n e -> Bool

(Ord e, Ord n) => Ord (Transition n e)

Defined in LTK.FSA

Methods

compare :: Transition n e -> Transition n e -> Ordering

(<) :: Transition n e -> Transition n e -> Bool

(<=) :: Transition n e -> Transition n e -> Bool

(>) :: Transition n e -> Transition n e -> Bool

(>=) :: Transition n e -> Transition n e -> Bool

max :: Transition n e -> Transition n e -> Transition n e

min :: Transition n e -> Transition n e -> Transition n e

(Read e, Read n) => Read (Transition n e)

Defined in LTK.FSA

Methods

readsPrec :: Int -> ReadS (Transition n e)

readList :: ReadS [Transition n e]

readPrec :: ReadPrec (Transition n e)

readListPrec :: ReadPrec [Transition n e]

(Show e, Show n) => Show (Transition n e)

Defined in LTK.FSA

Methods

showsPrec :: Int -> Transition n e -> ShowS

show :: Transition n e -> String

showList :: [Transition n e] -> ShowS

(NFData n, NFData e) => NFData (Transition n e)

Defined in LTK.FSA

Methods

rnf :: Transition n e -> ()

module LTK.Containers