autour_core

AUTOUR (AUTomata Utilities and Representation) is a Rust library for constructing, transforming, and analysing finite automata and regular expressions. The name comes from the French word for Goshawk.

---

Formalisms

The library is generic over any alphabet type Letter that satisfies Eq + Hash + Copy + Clone + Debug + Ord — char, u8, and custom enums all work out of the box.

Type	Description
AutDFA<Letter>	Deterministic finite automaton
AutNFA<Letter>	Non-deterministic finite automaton
AutNFAIT<Letter>	ε-NFA (NFA with epsilon / immediate transitions)
AutGNFA<Letter>	Generalized NFA — transitions are BRE terms, not single letters
ExpBRE<Letter>	Basic Regular Expression: Empty | Epsilon | Literal | Union | Concat | Kleene

An Extended Regular Expression type (ExpERE) covering intersection, negation, and wildcard is a work in progress and is not yet part of the public API.

---

Constructors

Every type provides a from_raw constructor that validates state indices and alphabet membership before building the automaton, returning Result<Self, AutError<Letter>> on invalid input.

Convenience constructors available on AutNFA (and where sensible on the other types):

AutNFA::new_empty_language(alphabet)  // one non-accepting state — accepts no word
AutNFA::new_empty_word(alphabet)      // accepts only the empty word ε
AutNFA::new_matching(alphabet, word)  // accepts exactly one word
AutNFA::new_universal(alphabet)       // accepts every word
AutNFA::new_length(alphabet, n)       // accepts every word of length n
AutNFA::new_accepts_nothing(alphabet) // synonym for new_empty_language

---

Operations via traits

All major operations are exposed through traits so they work uniformly across the different automaton types. Import the trait you need from autour_core::traits.

Running

AutRunnable — runs_trace, run_transition

use autour_core::traits::run::AutRunnable;

let accepted: bool = dfa.runs_trace(&['a', 'b', 'c'])?;
let next_states: HashSet<usize> = nfa.run_transition(&current_states, &'a')?;

Characterisation

AutCharacterizable — is_complete, is_empty, is_universal, language_contains, language_equals

use autour_core::traits::characterize::AutCharacterizable;

assert!(dfa1.language_equals(&dfa2));
assert!(big.language_contains(&small));

Accessibility

AutAccessible — is_accessible, make_accessible, is_coaccessible, make_coaccessible, is_trimmed, trim, plus the corresponding get_all_* query methods.

State colours used in Graphviz output:

• Green — accessible and coaccessible
• Purple — accessible but not coaccessible
• Blue — coaccessible but not accessible
• Red — neither

Building new languages

AutBuildable — all methods return Result<Self, AutError> when alphabet mismatches are possible, and Self otherwise.

Method	Language
unite(other)	L ∪ L′
concatenate(other)	L · L′
kleene()	L*
repeat(n)	Lⁿ
at_most(n)	L⁰ ∪ ... ∪ Lⁿ
at_least(n)	Lⁿ · L*
repeat_range(r)	union over the range
intersect(other)	L ∩ L′ (via AutTransformable)
interleave(other)	shuffle product (via AutTransformable)

Transformations

AutTransformable — complete, negate, reverse, minimize, intersect, interleave.

use autour_core::traits::transform::AutTransformable;

let minimal_dfa = dfa.minimize();
let complement  = nfa.negate();
let reversed    = nfa.reverse();
let complete    = nfa.complete(); // adds a sink state for missing transitions

Alphabet substitution and hiding

AutAlphabetSubstitutable — substitute_letters, hide_letters.

use autour_core::traits::letter::AutAlphabetSubstitutable;

// Replace every 'b' with 'c':
let renamed = gnfa.substitute_letters(true, &|l| if *l == 'b' { 'c' } else { *l });

// Erase 'b' from every transition (project it away):
let projected = gnfa.hide_letters(true, &|l| *l == 'b');

Translation between formalisms

AutTranslatable — to_dfa, to_nfa, to_nfait, to_gnfa, to_bre.

Every type can be converted to every other type. Translations that go through determinisation or minimisation may produce smaller automata than a naive structural conversion.

---

Minimization

DFA — Brzozowski's algorithm

dfa.minimize() applies Brzozowski's double-reversal algorithm: reverse → determinise → reverse → determinise. The result is the unique minimal complete DFA for the language.

NFA — Kameda-Weiner algorithm

nfa.minimize() runs the Kameda-Weiner algorithm, which finds the minimum-state NFA by:

1. Building the state matrix from the subset construction and its dual.
2. Reducing the matrix by merging equivalent rows and columns.
3. Searching for a minimum cover of the reduced matrix by prime grids.
4. Converting the best cover found into an NFA.

---

Visualization

Automata can be rendered to Graphviz .dot / SVG via the AutGraphvizDrawable trait, which is implemented for all types. The graphviz_dot_builder dependency handles graph construction; you supply a AbstractLanguagePrinter that controls how alphabet symbols and operators are printed.

A ready-to-use printer for char alphabets is provided:

use autour_core::printers::p_chars::CharAsLetterPrinter;
use autour_core::traits::repr::AutGraphvizDrawable;

let graph = nfa.to_dot(true, &HashSet::new(), &CharAsLetterPrinter {});

---

Error handling

All fallible operations return Result<_, AutError<Letter>>. AutError implements Display, Debug, and std::error::Error, so it integrates with ?, anyhow, and Box<dyn Error>.

match AutNFA::from_raw(alphabet, initials, finals, transitions) {
    Ok(nfa)  => { /* use it */ }
    Err(e)   => eprintln!("invalid automaton: {e}"),
}

---

Dependencies

Crate	Purpose
map-macro	hash_map!, hash_set!, btree_set! literal macros
itertools	Combination generation in Kameda-Weiner
strum / strum_macros	IntoStaticStr for BRE term variants
graphviz_dot_builder	Graphviz graph construction
num	Integer logarithm utilities