Machine Workspace Guide

Machine Workspace Guide

The Machine Workspace is AutomataLab's flagship environment for building, executing, and visually debugging formal automata.

It supports seven distinct models of computation, scaling from simple regular language recognizers to Turing-complete machines. This guide provides a deep dive into the features, execution mechanics, and advanced tooling available in the Machine Workspace.

---

1. Supported Machine Types

You can change the active machine type using the dropdown in the main toolbar. Warning: Changing the machine type on an existing canvas may invalidate certain transitions (e.g., if you switch from a PDA down to a DFA, stack operations will be stripped).

Finite Automata (Regular Languages)

• DFA (Deterministic Finite Automaton): Strictly one transition per symbol per state. No $\epsilon$-transitions allowed.
• NFA (Nondeterministic Finite Automaton): Allows multiple transitions for the same symbol from a single state, branching the computation.
• $\epsilon$-NFA: Introduces empty transitions (ε or eps), allowing the machine to change states without consuming an input character.

Pushdown Automata (Context-Free Languages)

• DPDA (Deterministic Pushdown Automaton): Incorporates a Stack. At most one valid transition can exist for any (state, input, top-of-stack) combination. Supports multi-character pushes and pops based on the explicitly defined Stack Alphabet ($\Gamma$).
• NPDA (Nondeterministic Pushdown Automaton): Like a DPDA, but allows non-deterministic branching on stack operations.

Turing Machines (Recursively Enumerable Languages)

• TM (Turing Machine): A standard single-tape, deterministic Turing Machine. Reads/writes to an infinite tape and moves the head L (Left) or R (Right).
• LBA (Linear Bounded Automaton): A restricted Turing Machine where the tape head cannot move past the initial bounds of the input string, flanked by specialized end-markers [ and ].

---

2. Core Editing Mechanics

Canvas Navigation

• Pan: Click and drag on the empty grid.
• Zoom: Scroll the mouse wheel, or use the zoom controls in the bottom-right corner.

State Management

• Add a State: Press N or select the + State icon on the left rail, then click anywhere on the canvas.
• Select States: Click a state to select it. Hold Shift to select multiple states.
• Move States: Drag a selected state to reposition it.
• Delete States: Select a state and press Backspace or Delete.
• Set Start/Accept: Right-click a state to open the context menu, then toggle Start or Accept.

Transition Management

• Create a Transition: Hover over a source state until the connection handle (a small dot) appears. Click and drag the handle to the target state.
• Edit a Transition: Click an existing transition edge to open the Edge Label Editor.
• Transition Syntax:
  • Finite Automata: Comma-separated symbols (e.g., a, b). Leave empty for an $\epsilon$-transition (if supported).
  • Pushdown Automata: The format is Read ; Pop → Push.
    • E.g., a ; X → YZ means: read a, pop X, push Y then Z.
    • Multi-character tokens: AutomataLab dynamically checks your Stack Alphabet ($\Gamma$). If you push id, and id is defined in $\Gamma$, it pushes it as a single token. Otherwise, it pushes i and d separately!
  • Turing Machines: The format is Read → Write , Move.
    • E.g., 0 → 1 , R means: read 0, write 1, move Right.
    • Use blank or ␣ for the blank symbol.

---

3. Simulation & Execution

The execution engine in AutomataLab is deterministic for DFAs/DPDAs/TMs, and recursively branches for NFAs/NPDAs.

The Input Bar

At the bottom of the screen is the Input Bar.

• For Finite and Pushdown Automata, type the string you wish to test (e.g., aabb).
• For Turing Machines and LBAs, type the initial tape contents.

Execution Controls

• Play/Pause (Space): Starts an automated, animated execution of the machine.
• Step Forward (S or →): Manually advance the computation by one step.
• Step Backward (←): Rewind the computation (supports time-travel debugging!).
• Reset (R): Reset the machine to its initial state.
• Speed Slider: Adjust the playback speed (0.5x to 4x).

Visual State Feedback

During execution, the active state(s) will be highlighted. For non-deterministic machines, multiple states may be highlighted simultaneously.

The simulation ends when the input string is fully consumed (or when a TM halts). The status badge will display:

• 🟢 Accepted: The machine halted in an Accept state after consuming all input.
• 🔴 Rejected: The machine exhausted the input without reaching an Accept state, or crashed.

---

4. Advanced Debugging Tools

The Computation Tree

For non-deterministic machines (NFA, $\epsilon$-NFA, NPDA), branching execution paths can be difficult to track on the canvas alone. Click the Tree icon on the right sidebar to open the Computation Tree panel. This provides a hierarchical visualization of every branched execution path. You can click on any node in the tree to instantly jump the canvas state to that specific timeline branch.

Stack & Tape Visualizers

• Stack Visualizer (PDA): When simulating a DPDA or NPDA, the right sidebar automatically displays the active Stack. You can watch tokens being pushed and popped in real-time.
• Tape Visualizer (TM/LBA): When simulating a Turing Machine, the bottom panel expands to show the infinite tape, the current head position, and live write operations.

Transition Table View

Prefer a spreadsheet over a graph? Click the Table icon in the right sidebar. The Transition Table allows you to view and rapidly edit the formal $\delta$ transition function matrix. Any changes made in the table instantly reflect on the canvas, and vice versa.

Machine Validation

AutomataLab runs an active validation sweep before allowing execution. If your machine violates formal textbook rules (e.g., a DFA missing transitions, or a PDA pushing an undeclared symbol), a Warning Banner will appear at the top. Click the banner to view detailed diagnostics and locate the exact nodes causing the issue.