Crate deterministic_automata

Expand description

A framework for implementing deterministic and mutation automata with arbitrary state complexity.

This crate provides a generic trait-based framework for creating deterministic and mutation automata that can handle state machines more complex than traditional finite state automata. States can carry arbitrary data, allowing recognition of some patterns beyond regular languages, and multiple automata can be composed using product constructions.

§Core Concepts

Blueprint: Defines the structure and behavior of an automaton through the DeterministicAutomatonBlueprint or MutationAutomatonBlueprint traits
State: Can be any Clone type, not limited to simple enums
Alphabet: Input symbols that can be compared for equality
StateSort: Classification of states (e.g., Accept/Reject)
Paradigms: Functional (deterministic) vs. in-place mutation approaches
Product Construction: Combining multiple automata to run in parallel

§Modules

§`counter_automaton_example`

Demonstrates recognition of the context-free language a^n b^n using counter-based states, showcasing capabilities beyond regular languages.

§`product_automaton`

Provides product construction blueprints for combining automata, including general product operations and specialized boolean operations (union, intersection) for automata with BasicStateSort.

§`either_automaton`

Provides runtime choice between two different automaton blueprint types using Either sum types, with separate implementations for deterministic and mutation paradigms in the deterministic and mutation submodules.

§`mutation_automaton`

Provides the MutationAutomatonBlueprint trait for automata that modify state in-place rather than returning new states, with automatic interoperability with deterministic automata through a blanket implementation.

§`dynamic_automaton`

Provides dyn-compatible traits enabling runtime polymorphism over automata with different state types. Solves the trait object compatibility problem by erasing only the state type while keeping alphabet, state sort, and error types concrete.

§Examples

§Simple Context-Free Language Recognition

use deterministic_automata::{DeterministicAutomatonBlueprint, BasicStateSort, counter_automaton_example::CounterAutomatonBlueprint};

let blueprint = CounterAutomatonBlueprint::new('a', 'b');
let input: Vec<char> = "aabb".chars().collect();

assert_eq!(blueprint.characterise(&input).unwrap(), BasicStateSort::Accept);

§Mutation Automaton with In-Place State Updates

use deterministic_automata::{BasicStateSort, MutationAutomatonBlueprint};

struct CountingBlueprint;

impl MutationAutomatonBlueprint for CountingBlueprint {
    type State = i32;
    type Alphabet = char;
    type StateSort = BasicStateSort;
    type ErrorType = String;

    fn initial_mutation_state(&self) -> Self::State { 0 }

    fn mutation_state_sort_map(&self, state: &Self::State) -> Result<Self::StateSort, Self::ErrorType> {
        Ok(if *state >= 0 { BasicStateSort::Accept } else { BasicStateSort::Reject })
    }

    fn mutation_transition_map(&self, state: &mut Self::State, character: &Self::Alphabet) -> Result<(), Self::ErrorType> {
        match character {
            '+' => *state += 1,
            '-' => *state -= 1,
            _ => return Err("Invalid character".to_string()),
        }
        Ok(())
    }
}

let blueprint = CountingBlueprint;
assert_eq!(blueprint.mutation_characterise(&['+', '+', '-']).unwrap(), BasicStateSort::Accept);

§Basic Finite State Automaton

Here’s a simple DFA that detects byte sequences containing the pattern [0,0]:

use deterministic_automata::{DeterministicAutomatonBlueprint, BasicStateSort};

#[derive(Clone, PartialEq, Debug)]
enum ContainsDoubleZeroState {
    Start,     // Initial state - haven't seen pattern yet
    SawZero,   // Just saw a 0, looking for another
    Found,     // Found [0,0] - accepting state
}

struct ContainsDoubleZero;

impl DeterministicAutomatonBlueprint for ContainsDoubleZero {
    type State = ContainsDoubleZeroState;
    type Alphabet = u8;
    type StateSort = BasicStateSort;
    type ErrorType = String;

    fn initial_state(&self) -> Self::State {
        ContainsDoubleZeroState::Start
    }

    fn state_sort_map(&self, state: &Self::State) -> Result<Self::StateSort, Self::ErrorType> {
        Ok(match state {
            ContainsDoubleZeroState::Found => BasicStateSort::Accept,
            _ => BasicStateSort::Reject,
        })
    }

    fn transition_map(&self, state: &Self::State, byte: &Self::Alphabet) -> Result<Self::State, Self::ErrorType> {
        Ok(match (state, *byte) {
            (ContainsDoubleZeroState::Start, 0) => ContainsDoubleZeroState::SawZero,
            (ContainsDoubleZeroState::Start, _) => ContainsDoubleZeroState::Start,
            (ContainsDoubleZeroState::SawZero, 0) => ContainsDoubleZeroState::Found,
            (ContainsDoubleZeroState::SawZero, _) => ContainsDoubleZeroState::Start,
            (ContainsDoubleZeroState::Found, _) => ContainsDoubleZeroState::Found, // Stay accepting
        })
    }
}

let dfa = ContainsDoubleZero;
assert_eq!(dfa.characterise(&vec![1, 0, 0, 2]).unwrap(), BasicStateSort::Accept);
assert_eq!(dfa.characterise(&vec![0, 0]).unwrap(), BasicStateSort::Accept);
assert_eq!(dfa.characterise(&vec![1, 0, 1, 0]).unwrap(), BasicStateSort::Reject);
assert_eq!(dfa.characterise(&vec![1, 2, 3]).unwrap(), BasicStateSort::Reject);

§Dynamic Dispatch Over Heterogeneous State Types

use deterministic_automata::{DynamicAutomatonBlueprint, counter_automaton_example::CounterAutomatonBlueprint};

let pattern_automaton = ContainsDoubleZero;  // Uses enum state
let counter_automaton = CounterAutomatonBlueprint::new(1, 2);  // Uses counter state

// Store automata with different state types in the same collection
let automata: Vec<&DynamicAutomatonBlueprint<u8, BasicStateSort, String>> = vec![
    &pattern_automaton,
    &counter_automaton,  
];

// Use them polymorphically despite different internal state representations
assert_eq!(automata[0].characterise(&vec![1, 0, 0]).unwrap(), BasicStateSort::Accept);
assert_eq!(automata[1].characterise(&vec![1, 1, 2, 2]).unwrap(), BasicStateSort::Accept);

These examples demonstrate how the framework handles both individual complex automata and compositions of multiple automata, maintaining deterministic behavior throughout.

Re-exports§

pub use mutation_automaton::MutationAutomatonBlueprint;
pub use mutation_automaton::MutationAutomaton;
pub use dynamic_automaton::DynamicAutomaton;
pub use dynamic_automaton::DynamicAutomatonBlueprint;

Modules§

counter_automaton_example: Example automaton that recognizes the context-free language a^n b^n.
dynamic_automaton: Dynamic dispatch for automaton blueprints with heterogeneous state types.
either_automaton: Either automaton implementation for runtime choice between two automata blueprints.
mutation_automaton: Mutation automaton implementation for in-place state modification.
product_automaton: Product construction and boolean operations for deterministic automata.

Structs§

DeterministicAutomaton: A runtime instance of a deterministic automaton.

Enums§

BasicStateSort: Basic binary classification for automaton states.

Traits§

DeterministicAutomatonBlueprint: A blueprint for defining deterministic automata with custom state and alphabet types.

Crate deterministic_automata Copy item path