Automaton{S} aka. DFA

Struct for deterministic finite automata (DFA) with states of type S.

initial(A::Automaton)

Return the initial state of a (deterministic) automaton.

hasedge(A::Automaton, σ, label)

Check if A contains an edge starting at σ labeled by label

isfail(A::Automaton, σ)

Check if state σ is a fail state in automaton A.

isaccepting(A::Automaton, σ)

Check if state σ is an accepting (terminal) state of automaton A.

trace(label, A::Automaton, σ)

Return τ if (σ, label, τ) is in A, otherwise return nothing.

trace(w::AbstractVector, A::Automaton[, σ=initial(A)])

Return a pair (l, τ), where

• l is the length of the longest prefix of w which defines a path starting

at σ in A and

• τ is the last state (node) on the path.

returned.

infiniteness_certificate(ia::IndexAutomaton)

Find a family of irreducible words of unbounded length if it exists.

Returns a witness w of the infiniteness, i.e.

    [w.prefix * w.suffix^n for n in ℕ]

is an infinite family of words irreducible with respect to ia.

Conversly if w.suffix is the trivial word no such infinite family exists and therefore the there are only finitely many irreducible words for ia.

isfinite(ia::Automaton)

Return true if the language of the automaton is proven to be finite.

irreducible_words(a::Automaton[, min_length=0, max_length=typemax(UInt)])

All words from the language of a, of length between min_length and max_length.

The words are returned form depth-first search, and hence are not ordered lexicographically.