Lab / Finite automata

Finite automata simulator

Draft a DFA or NFA and feed it a string: every active state glows as the input is read (an NFA lights up several at once). Stages separated by --- compose with op: union, op: intersect, or op: complement — the drawing you get is the product construction itself.

Program sheetInput string

Library

Tested automatons to start from — load one, run it, take it apart.

Even number of a's
The two-state parity DFA: the smallest machine with a memory.
Ends with ab
An NFA that guesses where the ending starts — watch several states light up at once.
Intersection (a product)
Two machines joined by op: intersect. The drawing is the product construction itself.
Complement
op: complement determinizes and flips acceptance: a determinized redraw, the opposite language.

Format

name: <text>              # optional; shown on the brass plate
start: <state>            # required
accept: <state>, ...      # optional

<state>, <symbol> -> <state>
q, a -> q2                # several rules per (state, symbol) = an NFA
q, eps -> q2              # ε-moves

---                       # composition; later stages open with
op: intersect             # union | intersect, then an automaton —
...                       # or a bare `op: complement` stage that
                          # flips everything before it.

# '#' starts a comment. Composition determinizes via the subset
# construction and joins via the product construction; the
# combined machine is capped at 256 states.