Finite State Machine (FSM) Utility Library

Small, well-typed TypeScript utilities to build, validate, and run deterministic finite-state machines (FSMs). This project provides a compact runtime, a set of strongly-typed types for FSM definitions, a schema-driven validation layer that produces clear error messages, and a small CLI example (modulo-3 demo) to illustrate usage.

📘 Documentation: The latest generated API documentation (TypeDoc) is hosted at: https://jimmypalelil.github.io/fsm-util-lib/

Quick start

1. Install dependencies

npm install
Copy

1. Run the modulo-3 demo from the CLI (example input: 1101)

npm run modThreeFSMDemo
Copy

What this project exports

• FiniteStateMachine — a constructor that validates an FSMConfig and creates a runtime FSM instance.
• TransitionFunction<State, Input> and other helpful types under src/types.

Example imports (relative to project root):

import { FiniteStateMachine } from './src/FiniteStateMachine';
import { TransitionFunction } from './src/types';
Copy

Usage

Programmatic example (build and run an FSM):

import { FiniteStateMachine } from './src/FiniteStateMachine';
import { TransitionFunction } from './src/types';

const states = ['S0', 'S1'];
const alphabet = ['a', 'b'];
const transitionFunction: TransitionFunction<
  (typeof states)[number],
  (typeof alphabet)[number]
> = {
  S0: { a: 'S1', b: 'S0' },
  S1: { a: 'S0', b: 'S1' },
};

const fsm = new FiniteStateMachine({
  states,
  alphabet,
  initialState: 'S0',
  finalStates: ['S0'],
  transitionFunction,
});

const final = fsm.process(['a', 'b', 'a']);
console.log(final);
Copy

CLI example (modulo-3 demo):

npm run modThreeFSMDemo
Copy

Options and advanced usage

• The constructor validates the config using the helpers in src/schemas/fsm and then stores the validated, type-safe config on the instance. The schema enforces sensible defaults (like a maximum number of states) internally.
  • States and input symbols are strings by design

Assumptions

• Default maximum number of states: 1000 — enforced by the schema using the MAX_STATES_ALLOWED constant found in src/constants/fsm-constants.ts. This is an intentional guardrail to avoid pathological configs that would otherwise require large amounts of memory or slow validation. The limit is applied during validation and produces a clear error message when exceeded ("Cannot exceed 1000 states").
• States and inputs are strings only. (e.g. S0, S1, or "0", "1").

Validation and errors

• Validation runs during construction and is powered by Zod. The config is validated via the schema in src/schemas/fsm and failures throw a z.ZodError with helpful issue messages and paths.

  Programmatic validation options:

  • Use the class constructor (throws on invalid configs):

    import { FiniteStateMachine } from './src/FiniteStateMachine';
    import { z } from 'zod';
    
    try {
      new FiniteStateMachine(config);
    } catch (err) {
      if (err instanceof z.ZodError) {
        // Inspect structured validation issues
        console.error(err.issues);
      }
      throw err; // or handle otherwise
    }
    Copy

  • Use the schema helpers directly:

    import { createFSMSchema, validateFSMConfig } from './src/schemas/fsm';
    import { z } from 'zod';
    
    // 1) Build a schema (states/inputs are strings)
    const schema = createFSMSchema();
    
    // Parse (throws on error)
    const parsed = schema.parse(config);
    
    // Or safeParse (returns success/failed result without throwing)
    const result = schema.safeParse(config);
    if (!result.success) {
      // result.error is a ZodError
      console.error(result.error.issues);
    }
    
    // 2) Or use the convenience function (wraps schema.parse)
    const validated = validateFSMConfig(config);
    Copy

  Common validation checks enforced by the schema:

  • states and alphabet must be non-empty arrays of unique values.
  • initialState must be a member of states.
  • finalStates must be a subset of states.
  • transitionFunction must include a target state for every (state, symbol) pair.

• When validation fails the library throws an Error with a descriptive message indicating which part of the config is invalid. The schema helpers in src/schemas/fsm return rich error messages that are useful for diagnostics in tests and CLI output.

Performance

• process(input) runs in O(n) time where n is the input length; each step is an O(1) lookup in the nested transition table. Memory usage is dominated by the transition table size (|states| × |alphabet|).

Testing

Vitest is used as the testing framework. Test config is located at <root>/vitest.config.ts file.

• Run tests:

npm run test
Copy

• Coverage:

npm run test:coverage
Copy

Documentation Site (TypeDoc)

This project uses TypeDoc to generate API documentation.

• Generate locally:

  npm run docs
  Copy

• Output is placed in the docs/ directory (served by GitHub Pages).