Reference

The normative reference for rgxr’s data formats and behavior: the Fa wire format, derived-state naming, auth, saved documents, trace semantics, regex syntax, engine limits, render engines, environment variables and the error envelope. The machine-readable API contract is openapi.yaml at the repo root; producers and consumers derive from these two documents.

Freezing

The shapes documented here are frozen now that users exist: saved documents and API consumers depend on them, so changes are additive and land together with an update to this page and openapi.yaml, never as a silent wire change. The TM wire schema was extended to multi-tape and nondeterministic machines (a tapes field plus action lists per read-tuple); old single-action payloads are still accepted on input.

The Fa type

Canonical wire format (camelCase, arrays sorted):

{
  "alphabet": ["a", "b"],
  "states": ["q0", "q1", "q2"],
  "initial": "q0",
  "accepting": ["q2"],
  "transitions": {
    "q0": { "a": ["q0", "q1"], "b": ["q0"] },
    "q1": { "b": ["q2"] },
    "q2": { "a": ["q2"], "b": ["q2"] }
  }
}

Rules:

Derived-state naming

Constructions (subset construction, product, minimization, state elimination) generate new state names deterministically:

  1. Candidate name derived from the semantic content (e.g. sorted member states joined with ",").
  2. If the candidate collides with any already-used name, append #k with the smallest k ≥ 2 that is free.

No randomness, no format!("q{}", counter) across runs.

Candidates per construction:

Construction Candidate name
to_dfa member states sorted, joined with ,; the empty subset is ∅
union / intersection / difference (s1,…,sn), one component per operand
sink added to complete an operand ∅
concatenation original state name, first operand first
minimize smallest member of the equivalence class
regex_to_nfa q0…qn by BFS rank from the initial state

regex_to_nfa states carry no semantic content beyond their position, so BFS rank over the deterministic Thompson graph is the name: it depends only on the regex.

Auth model

rgxr never stores passwords. Signing in is optional and goes through any OpenID Connect provider:

Saved documents

POST/PUT /automata bodies are { name, data } where

{ "fa": { ...Fa... }, "layout": { "q0": { "x": 250, "y": 80 } } }

layout is frontend-owned (xyflow positions). The backend treats it as opaque JSONB passthrough and must never parse or validate it.

Grammars, PDAs and TMs are saved as their editor source:

{ "kind": "cfg", "text": "S -> a S b | ε" }

kind ∈ fa | cfg | pda | tm, default fa (rows written before kinds existed). fa documents carry fa and no text; the others carry text (≤ 64 KiB) and no fa. List summaries include kind.

Trace semantics

run returns a trace of snapshots: the epsilon-closed set of active states after consuming each symbol, serialized sorted. Step 0 has symbol: null (the initial closure) and symbol is always present in the JSON, null included. accepted = last step's states ∩ accepting ≠ ∅. For DFAs each snapshot is a singleton: same shape, simpler view.

Regex syntax (engine)

| union · juxtaposition concat · * star · + plus · ? option · ( ) grouping · \x escape for literal metacharacters · empty expression or ε = the empty string (\ε is a literal ε). Unicode literals allowed. Parse errors → invalid_regex with a human-readable message naming the 1-based position.

fa_to_regex output always re-parses with this syntax. The empty language has no expression in it and returns invalid_fa. Conversion is size-bounded: an automaton whose equivalent regex would be too large to build returns invalid_fa instead of exhausting memory.

Limits

Every engine request finishes in bounded time and memory. Exceeding a limit is a 400 with a message naming the limit (invalid_regex for regex limits, invalid_fa otherwise), except the body limit.

Limit Value Applies to
Request body 2 MiB every endpoint; over it → 413 with code invalid_request
States per input automaton 10 000 every engine operation and render
Alphabet symbols per input automaton 256 every engine operation and render
State name or symbol length 256 bytes every engine operation and render
Transition targets per input automaton 200 000 every engine operation and render
Transitions derived by ε-removal or completion 1 000 000 union, intersection, difference, fa_to_regex
States built by a construction 10 000 to_dfa, union, intersection, difference
Transitions built by a product 200 000 union, intersection, difference
Automata per n-ary operation 16 union, intersection, concatenation
run input 10 000 symbols run
run trace size 1 000 000 active-state entries and 16 MiB of state names in total run
Regex length 10 000 characters regex_to_nfa
Group nesting 200 levels regex_to_nfa
States eliminated 1 000 fa_to_regex
Saved automata listed 500 newest GET /automata
Expression size 4 096 nodes per edge, 2 000 000 nodes built in total fa_to_regex
Grammar size 200 nonterminals, 2 000 right-hand-side symbols every grammar endpoint
Parsed word 32 symbols; 10 000 000 chart/table steps (over → 400 asking for a shorter word or simpler grammar) grammar/parse, grammar/cyk
CNF rules built 20 000 grammar/cnf, grammar/cyk
PDA size / input 500 states, 5 000 transitions / 200 symbols pda/*
PDA → CFG size normalised transitions × states² ≤ 200 000 pda/to-grammar
PDA search 50 000 configurations, stack depth 400 (limit hit → truncated) pda/run
TM size / input / steps 500 states / 500 symbols / 100 000 steps; 1–4 tapes; nondeterministic search up to 50 000 configurations (trace keeps 2 000) tm/run
Grading sweep 4 000 words up to length 12; 200 000 work units shared across words (a PDA or nondeterministic-TM configuration = 1, a deterministic TM step = 1/16, a parse step = 1/128; over → budgetExhausted) grade
Table-filling 100 reachable states ops/minimize/table

Stacked postfix operators fold while parsing (a*** ≡ a*), so they count toward the length limit only.

Render engines

Every render subprocess runs under a hard timeout (5 s for the fast engine’s dot; the latex stages allow longer).

Latex render responses additionally carry tikz: the TikZ source the image was produced from, for pasting into LaTeX documents (which cannot embed SVG natively). It includes the stroke-width override the rendered image used and a comment naming the required preamble packages. fast responses have no tikz field.

Environment variables

Var Default Meaning
DATABASE_URL none Postgres URL (sqlx)
RGXR_PORT 8080 Listen port
RGXR_DEV_MODE false Dev conveniences: Vite-origin CORS; requests without a token run as anonymous
RGXR_ANONYMOUS_FALLBACK false Requests without a token run as anonymous instead of 401
RGXR_OIDC_ISSUER none OIDC issuer whose access tokens the API accepts; unset → every token is 401
RGXR_OIDC_AUDIENCE rgxr Required aud entry of accepted access tokens
RGXR_LATEX_ENABLED false Enable the latex render engine
RUST_LOG info tracing filter

rgxr-web adds:

Var Default Meaning
OIDC_ISSUER none OIDC issuer for the optional sign-in; unset → no sign-in UI, everyone stays anonymous
OIDC_CLIENT_ID rgxr Public client id registered at the issuer
API_UPSTREAM none Forward api paths to this base URL (compose); unset → the ingress routes them

Locally the variables come from the shell or a .env file. In our production deployment (see Operations) they are injected via OpenBao → ESO → K8s Secret; other deployments pass them however their platform injects environment variables.

Error envelope

{ "error": { "code": "invalid_fa", "message": "initial state `q9` is not in `states`" } }

Codes: invalid_request, invalid_fa, invalid_regex, not_found, unauthorized, conflict, render_unavailable, internal. Input validation is always 400; missing resources 404.