# Theory of Computation Simulator

> An open-source, browser-based interactive simulator for automata theory and computation theory.

Theory of Computation Simulator is a free, educational web application for building, editing, and simulating automata used in automata theory and formal language theory. No installation required — everything runs in the browser on an interactive canvas.

## Supported Automata Types

### Finite Automata (DFA / NFA)
Formal definition: M = (Q, Σ, δ, q₀, F)
- Q: finite set of states
- Σ: input alphabet
- δ: transition function (DFA: Q × Σ → Q; NFA: Q × Σ_ε → 2^Q)
- q₀ ∈ Q: start state
- F ⊆ Q: set of accept states

Transition label format: single symbol — `a`, `b`, `ε` (epsilon for NFA)

Features: NFA → DFA subset construction, DFA minimization, GNFA state elimination for regex extraction.

### Pushdown Automata (PDA / NDPA)
Formal definition: M = (Q, Σ, Γ, δ, q₀, Z₀, F)
- Γ: stack alphabet
- Z₀: initial stack symbol
- δ: Q × Σ_ε × Γ_ε → finite subsets of Q × Γ*

Transition label format: `input,pop/push` — e.g., `a,A/BA`, `ε,Z/Z`
- Deterministic (PDA) and nondeterministic (NDPA) variants supported

### Turing Machines (TM)
Formal definition: M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)
- Single-tape and multi-tape variants
- Move directions: L (left), R (right), N (stay)

Transition label format:
- Single-tape: `read/write,direction` — e.g., `0/1,R`, `_/_,N`
- Multi-tape: semicolon-separated segments — e.g., `0/1,R;_/_,N`

### Mealy Machines
Formal definition: M = (Q, Σ, Δ, δ, λ, q₀)
- Δ: output alphabet
- λ: output function on transitions

Transition label format: `input/output` displayed on each arrow.

### Moore Machines
Formal definition: M = (Q, Σ, Δ, δ, λ, q₀)
- λ: output function on states (each state has an output label)

### GNFA (Generalized NFA)
Used for FA → regular expression conversion via state elimination. Generated automatically from any saved DFA/NFA.

### CFG (Context-Free Grammar)
Skeleton CFG extraction from a saved finite automaton.

## Multi-Character Alphabet Support

All alphabet symbols can be multi-character strings (e.g., `ab`, `push`, `nop`). The tokenizer uses longest-match-first with a cached sorted symbol list.

Epsilon is written as `ε` (Unicode) or matched automatically in empty-transition contexts.

## Canvas Interaction

- Infinite scrollable/zoomable canvas
- States: drag to place, click to select, double-click to edit label
- Transitions: click state → drag to target state
- String simulation: highlights active transitions in real time
- Save automata to workspace, export/import as JSON

## Teams & Collaboration

Signed-in users can create or join a Team (via invite code) to work on automata with others:

- **Roles**: owner / admin / member, with promote/demote, remove, and ban actions available to owners and admins.
- **Real-time shared canvas**: everyone viewing a team's scope sees states and transitions appear live as teammates draw them (Supabase Realtime broadcast).
- **Projects**: assignments organized into (optionally foldered) projects, each with an optional submission deadline and member cap; team members submit automatons from the shared pool to a project.
- **Team settings**: rename, cap max members/projects, manage a ban list (blocks re-joining via invite code).
- **Personal cloud library**: automatons saved while signed in (outside a team) sync to the user's account across devices; signed-out use stays entirely local (`localStorage`), no account required.

Entry points: `/teams` (overview, create/join), `/teams/[id]` (dashboard), `/teams/[id]/projects/[projectId]` (project gallery), `/teams/[id]/settings` and `/teams/[id]/projects/[projectId]/settings` (owner/admin only).

## API Endpoints

### MCP (Model Context Protocol) — for AI agents
`POST /api/mcp` — JSON-RPC 2.0 endpoint implementing the MCP protocol.

Available tools:
- `simulate_fa` — test a string against a DFA or NFA
- `simulate_pda` — test a string against a deterministic PDA
- `simulate_ndpa` — test a string against a nondeterministic PDA
- `simulate_tm` — test a string against a single/multi-tape TM
- `simulate_mealy` — run a Mealy machine and return output sequence
- `simulate_moore` — run a Moore machine and return output sequence
- `regex_to_nfa` — convert regex to NFA via Thompson's construction
- `nfa_to_dfa` — determinize an NFA via subset construction
- `fa_to_regex` — extract regex from FA via GNFA state elimination
- `get_transition_table` — render any automaton as a transition table
- `get_automata_info` — return full reference of supported types and syntax
- `build_fa_link` — return a simulator URL that loads a DFA/NFA on the canvas
- `build_pda_link` — return a simulator URL that loads a deterministic PDA on the canvas
- `build_ndpa_link` — return a simulator URL that loads a nondeterministic PDA on the canvas
- `build_tm_link` — return a simulator URL that loads a Turing Machine on the canvas
- `build_mealy_link` — return a simulator URL that loads a Mealy machine on the canvas
- `build_moore_link` — return a simulator URL that loads a Moore machine on the canvas

Account & Teams tools (require `Authorization: Bearer <personal-access-token>`; token self-service UI is planned but not shipped yet):
- `list_my_teams` — list the teams the authenticated user belongs to, with role
- `create_team` — create a new team owned by the authenticated user
- `join_team` — join a team by invite code
- `list_team_members` — list a team's members and roles
- `list_team_projects` — list a team's folders/projects
- `create_project` — create a project (assignment) in a team, owner/admin only
- `list_my_automatons` — list the user's personal automatons, or a team's if `team_id` is given
- `save_automaton` — save (or overwrite by name) an automaton, personal or team-scoped
- `submit_automaton_to_project` — attach/detach a team automaton to a project

OpenAPI spec: /openapi.json
MCP endpoint: /api/mcp

### Blog API (read-only for public)
- `GET /api/posts` — list all blog posts
- `GET /api/posts/[slug]` — get single post

## Technical Details

- **Framework**: Next.js 16 (App Router), React 19, TypeScript 6
- **Styling**: Tailwind CSS 4 + CSS custom properties
- **License**: MIT
- **Repository**: https://github.com/KebanFiru/theory_of_computation_simulator
- **Live app**: https://www.theoryofcomputationsimulator.com/simulator
- **Teams**: https://www.theoryofcomputationsimulator.com/teams
- **Blog**: https://www.theoryofcomputationsimulator.com/blog

## Transition Syntax Reference

| Model | Format | Example |
|-------|--------|---------|
| FA (DFA/NFA) | symbol | `a`, `ε` |
| PDA/NDPA | input,pop/push | `a,A/BA`, `ε,Z/Z` |
| TM (single tape) | read/write,direction | `0/1,R`, `_/_,N` |
| TM (multi-tape) | seg1;seg2;... | `0/1,R;_/_,N` |
| Mealy | input/output | `a/0` |
| Moore | (state output label) | output assigned to state |

## Who It's For

Students and educators studying:
- Formal Languages and Automata Theory
- Theory of Computation (undergraduate CS courses)
- Compiler design foundations
- Computability and complexity theory

Classes and study groups working together on assignments via Teams (shared real-time canvas, project submissions with deadlines).