automata_core 0.1.2

Deterministic and nondeterministic finite-automata algorithms in Rust
Documentation

automata_core

Crates.io Docs.rs License: MIT OR Apache-2.0

Deterministic and nondeterministic automaton algorithms in Rust.

The crate is built around a generic automaton trait layer (general). Some algorithms live in the finite module and require enumerating states and input symbols (so they work with finite-state/finite-alphabet automata). The public trait layer does not include ε-transitions.

This crate is not affiliated with the unrelated crate on crates.io named automata (https://crates.io/crates/automata).

What it does

The library provides:

  • Base trait layers for generic automata concepts (general)
  • A finiteness layer for algorithms that require finite state sets and finite alphabets (finite)
  • Concrete reference implementations (simple), plus a set of integration tests

The main emphasis is to keep the public trait layer free of ε-transitions.

Implemented

High-level operations (typically provided as trait methods):

  • Determinization (to_dfa) for NFAs
  • Boolean/structural operations: union, intersection, difference, concatenate, star
  • N-ary operations: union_all, intersect_all, concatenate_all
  • Closure operations: reverse, trimmed, accessible, co_accessible
  • DFA completion and complement: complete, complement (requires a total DFA pipeline)
  • Brzozowski minimization (minimize)

Debug/interop helpers:

  • FiniteAutomaton::to_dot (Graphviz DOT) for visual inspection
  • DeterministicFiniteAutomaton::to_matrix (DFA transition matrix)

Quick example

use automata_core::simple::SimpleDFA;
use automata_core::finite::deterministic::DeterministicFiniteAutomaton;
use automata_core::general::deterministic::DeterministicAutomaton;

let alphabet = ['a'];
// 0 = even length, 1 = odd length
let edges = [(0usize, 'a', 1usize), (1usize, 'a', 0usize)];
let dfa = SimpleDFA::try_new(2, 0, [0], alphabet, edges).unwrap();

assert!(dfa.accepts(&[]));
assert!(!dfa.accepts(&['a']));
assert!(dfa.accepts(&['a', 'a']));

Module organization

  • general: the base Automaton trait + determinism/nondeterminism helpers
  • finite: finiteness-bound traits and algorithmic operations
  • simple: SimpleDFA / SimpleNFA concrete implementations

WIP / status

This library is work-in-progress. While the core constructions and trait APIs are in place, test coverage is still incomplete and some debug helpers are not finished yet.

Known TODOs:

  • FiniteAutomaton::to_dot (Graphviz DOT export) is not implemented yet.

License

MIT OR Apache-2.0