automata_core 0.1.0

Deterministic and nondeterministic finite-automata algorithms in Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

# automata_core

[![Crates.io](https://img.shields.io/crates/v/automata_core.svg)](https://crates.io/crates/automata_core)
[![Docs.rs](https://docs.rs/automata_core/badge.svg)](https://docs.rs/automata_core)
[![License: MIT OR Apache-2.0](https://img.shields.io/badge/License-MIT%20OR%20Apache--2.0-blue.svg)](https://opensource.org/licenses/MIT)

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

```rust
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`](src/general/): the base `Automaton` trait + determinism/nondeterminism helpers
- [`finite`](src/finite/): finiteness-bound traits and algorithmic operations
- [`simple`](src/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