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

The collection of all states in an FSA.

True iff the input accepts no strings.

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

Since: 0.2

Returns whether the given FSA lands in a final state after processing the given sequence.

Since: 1.1

An automaton accepting every string over a given alphabet.

An automaton accepting no strings over a given alphabet.

A specialization of emptyWithAlphabet where the alphabet is itself empty.

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

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

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

Add self-loops on all symbols to all edges to compute an upward closure.

Since: 1.1

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

Allow a given set of symbols to be freely inserted or deleted. In other words, make those symbols neutral.

Since: 1.1

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

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

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.

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.

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.

The syntactic ordered monoid is the syntactic monoid alongside the same order as in the syntactic ordered semigroup. Return the transition monoid: this is syntactic if the automaton is minimal or shaped like the Cayley graph of its monoid.

Since: 1.2

Consider each alphabetic symbol as a function from state to state. The semigroup generated by these functions is the transformation semigroup of a deterministic automaton. Return the transition semigroup: this is syntactic if the automaton is minimal or shaped like the Cayley graph of its monoid.

Since: 1.2

The syntactic ordered semigroup is the syntactic semigroup alongside an order, where \(x\leq y\) if and only if whenever \(uyv\) maps the inital state to a final state, so too does \(uxv\). Return the transition semigroup: this is syntactic if the automaton is minimal or shaped like the Cayley graph of its monoid.

Since: 1.2

(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 a b) is equivalent to (complement (residue a b)). In the context of an approximation and its source, represents unmet constraints of the source.

Create a graph whose vertices are states of the given FSA and where a directed edge exists from \(p\) to \(q\) if and only if \(p\mathcal{R}q\) under the given relation.

Since: 1.2

The primitive two-sided ideal.

Since: 0.2

The primitive left ideal.

Since: 0.2

The primitive right ideal.

Since: 0.2

Return the set of states in the same strongly connected component as the given state.

Since: 1.2

Return a graph of the strongly connected components of the given FSA and the directed connections between them.

Since: 1.2

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.

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.

Infiltrate all given automata, in parallel if possible. An empty infiltration is defined as the singleton language over an empty alphabet containing only the empty string. Intermediate results are evaluated to normal form.

Since: 1.1

Shuffle all given automata, in parallel if possible. An empty shuffle is defined as the singleton language over an empty alphabet containing only the empty string. Intermediate results are evaluated to normal form.

Since: 1.1

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

Returns an FSA accepting all and only those strings accepted by the first input but rejected by the second.

Since: 1.1

Returns the infiltration product of its two input autamata.

Since: 1.1

Returns the shuffle product of its two input autamata.

Since: 1.1

Given an FSA representing an event \(x\) and another representing an event \(y\), returns the FSA accepting all and only those strings that begin with \(x\) and end with \(y\) such that the beginning of \(y\) lies strictly later than the beginning of \(x\) yet no later than the end of \(x\).

Since: 1.2

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

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

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

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

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.

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 Integer is used as a default representation.

The input automaton with unreachable states removed.

Since: 1.0

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.

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

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

Since: 0.2

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

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

Since: 0.2

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.

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.

Remove symbols from the alphabet of an automaton.

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

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

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.

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.

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

Return Just the longest sequence \(u\) of symbols such that every word in the language is \(uv\) for some \(v\). If the language is empty, return None.

Since: 1.2

Return Just the longest sequence \(v\) of symbols such that every word in the language is \(uv\) for some \(u\). If the language is empty, return None.

Since: 1.2

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.

The label of a Transition.

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

The edges of an FSA.