FSM Builder

A generic finite state machine library for building deterministic finite automata. Solve modulo arithmetic, pattern matching, protocol validation, and more with clean, type-safe APIs.

Features

• Generic FSM Implementation: Build any deterministic finite automaton
• Type-Safe: Full TypeScript support with comprehensive type definitions
• Configuration Validation: Comprehensive FSM validation with clear error messages
• Performance: Optimized for large inputs and repeated operations
• Extensible: Clean API designed for library consumers
• Well-Tested: Comprehensive test suite with >95% coverage

Installation

npm install @dokgu/fsm-builder
# or
yarn add @dokgu/fsm-builder

Quick Start

import { FiniteStateAutomaton } from '@dokgu/fsm-builder';

// Create an FSM that detects even parity (even number of 1s)
const parityFSM = new FiniteStateAutomaton({
  states: new Set(['EVEN', 'ODD']),
  alphabet: new Set(['0', '1']),
  initialState: 'EVEN',
  finalStates: new Set(['EVEN']),
  transitions: new Map([
    ['EVEN,0', 'EVEN'], // 0 doesn't change parity
    ['EVEN,1', 'ODD'], // 1 flips parity
    ['ODD,0', 'ODD'], // 0 doesn't change parity
    ['ODD,1', 'EVEN'] // 1 flips parity
  ])
});

const result = parityFSM.process('1100'); // 2 ones (even)
console.log(result.isAccepted); // true

API Reference

FiniteStateAutomaton<TState, TSymbol>

Generic finite state automaton implementation supporting the formal 5-tuple (Q, Σ, q0, F, δ).

Constructor

new FiniteStateAutomaton(config: FSMConfig<TState, TSymbol>)

Parameters:

• config.states: Set of all possible states (Q)
• config.alphabet: Set of input symbols (Σ)
• config.initialState: Starting state (q0 ∈ Q)
• config.finalStates: Accepting states (F ⊆ Q)
• config.transitions: Transition function (δ: Q × Σ → Q)

Methods

• process(input: string | TSymbol[]): FSMResult<TState> - Process input and return result
• getCurrentState(): TState - Get current state
• isInFinalState(): boolean - Check if in accepting state
• reset(): void - Reset to initial state
• getStates(): Set<TState> - Get copy of states set
• getAlphabet(): Set<TSymbol> - Get copy of alphabet set
• getFinalStates(): Set<TState> - Get copy of final states set

Testing

# Run all tests
npm run test

# Run tests in watch mode
npm run test:watch

# Generate coverage report
npm run test:coverage

Development

# Install dependencies
npm install

# Build the library
npm run build

# Run tests
npm run test

# Run linting
npm run lint

Examples

See the examples/ directory for additional usage examples including:

• Modulo arithmetic
• Pattern matching
• Protocol validation

Run the examples:

cd examples
npm install
npm run demo

Background

This library implements the mathematical concept of Deterministic Finite Automata (DFA), which are computational models consisting of:

• Q: Finite set of states
• Σ: Finite input alphabet
• q0: Initial state (q0 ∈ Q)
• F: Set of accepting/final states (F ⊆ Q)
• δ: Transition function (δ: Q × Σ → Q)

Why Use FSMs?

1. Efficiency: Process inputs in O(n) time with O(1) space
2. Memory: No need to store large intermediate values
3. Hardware-Friendly: Similar to how processors actually work
4. Mathematically Sound: Based on formal computational theory

License

This project is licensed under the MIT License - see the LICENSE file for details.

Author

Patrick Gregorio

• Repository: https://github.com/dokgu/fsm-builder