Automaton Simulator Help

Introduction

This simulator supports visualization and step-by-step execution of several types of automata and formal language models:

Example Files

The easiest way to explain the input file format is by example; see several examples below.

Type File Description
DFA no-000-end.dfa Rejects strings ending in "000"
NFA 0-three-from-end.nfa Accepts strings with "0" as third symbol from end
NFA 0s1s2s.nfa Recognizes 0*1*2* with ε-transitions
TM double.tm Doubles the input: 0^n → 0^{2n}
TM palindrome-single-tape.tm Recognizes palindromes using one tape
TM count-a-wildcard.tm Demonstrates wildcard usage
CFG balanced-parens.cfg Generates balanced parentheses
Regex contains-010.regex Binary strings containing "010"

Getting Started

Basic Usage

  1. Select the model type from the Model menu
  2. Enter your automaton definition in the left panel using YAML syntax
  3. Type your test string in the input field
  4. Toggle "Run immediately?" for automatic computation, or use the "Run" button for manual control
  5. Use navigation controls to step through the computation
💡 Tip: Try loading a default example using File → Load Default (Ctrl+L) to see the expected format for each model type.

File Management

Navigation Controls

For DFA, NFA, and TM models, you can step through the computation:

YAML Syntax

All automaton definitions use YAML (YAML Ain't Markup Language) format. YAML is a human-readable data serialization standard.

Key YAML Concepts

Arrays: Lists of items can be written in two ways:

states: [q0, q1, q2]    # Inline format
states:                 # Block format
  - q0
  - q1
  - q2

Objects: Key-value mappings use colons:

delta:
  q0:
    a: q1
    b: q0

Comments: Use # for documentation

# This is a comment explaining the automaton

Special Characters: Some characters need quotes in YAML, or if you want to avoid using quotes in state names and alphabet symbols, then avoid these YAML special characters:

YAML Numeric Interpretation Pitfalls

YAML automatically converts unquoted values that look like numbers. This can cause unexpected errors when using numeric state names with leading zeros:

The Leading Zero Problem

Problem: Leading zeros collapse to the same number

# WRONG - 00 and 01 become numbers 0 and 1
states: [q0, 00, 01, 02]  # 00 becomes 0, 01 becomes 1, etc.
delta:
  q0:
    a: 00   # References state 0 (number)
  00:       # This is actually state 0 (number)
    b: 01
  01:       # This is actually state 1 (number)  
    c: 02

Error you'll see: Map keys must be unique or state reference errors if you have both 0 and 00 in your states list.

Solution: Quote State Names with Leading Zeros

When using numeric state names with leading zeros, always use quotes:

# CORRECT - All state names are strings
states: [q0, '00', '01', '02']  # Preserves leading zeros
delta:
  q0:
    a: '00'   # References string state "00"
  '00':       # String state "00" - different from "0"
    b: '01'
  '01':       # String state "01" - different from "1"
    c: '02'
📝 Rule of Thumb: When in doubt, use quotes! It's safer to quote symbols than deal with type conversion errors. The simulator expects string symbols, so '0' is always safer than unquoted 0.

Model-Specific Syntax

DFA (Deterministic Finite Automaton)

Required fields:

Example: DFA that rejects strings ending in 000

# DFA recognizing { x in {0,1}* | x does not end in 000 }

states: [q, q0, q00, q000]
input_alphabet: [0, 1]
start_state: q
accept_states: [q, q0, q00]

delta:
  q:
    1: q
    0: q0
  q0:
    1: q
    0: q00
  q00:
    1: q
    0: q000
  q000:
    1: q
    0: q000

NFA (Nondeterministic Finite Automaton)

Same fields as DFA, but delta can map to either individual states (like DFA) or arrays of states for nondeterminism. When there is only one target state, do not put it in an array. NFAs also support ε-transitions:

Example: NFA recognizing 0*1*2*

# NFA recognizing the language described by the regular expression 0*1*2*

states: [q0, q1, q2]
input_alphabet: [0, 1, 2]
start_state: q0
accept_states: [q2]

delta:
  q0:
    0: q0       # Single target state (no array needed)
    "": q1      # ε-transition (empty string)
  q1:
    1: q1       # Single target state
    "": q2      # ε-transition
  q2:
    2: q2       # Single target state

For transitions with multiple target states, use arrays:

delta:
  q0:
    a: [q1, q2]  # Nondeterministic: both q1 and q2
    b: q0        # Single target: no array needed
📝 Note: Use empty string "" for ε-transitions in NFAs. Only use arrays when there are multiple target states.

TM (Turing Machine)

Required fields:

Tape Alphabet: Automatically includes _ (blank) and all symbols from input_alphabet and tape_alphabet_extra.

Transition Format: current_symbols: [new_state, new_symbols, moves]

Example: TM that doubles input (0^n → 0^{2n})

# TM computing the function f(0^n) = 0^{2n}

states: [q0, q1, q2, qD, qA, qR]
input_alphabet: [0]
tape_alphabet_extra: ['!']  # ! needs quotes as it's a YAML special character
start_state: q0
accept_state: qA
reject_state: qR

delta:
  q0:
    0_: [q1, 0!, SR]      # Mark first 0, move right on tape 2
  q1:
    0_: [q2, 00, SR]      # For each 0, write two 0s on tape 2
    __: [qD, __, SL]      # End of input, start cleanup
  q2:
    0_: [q1, 00, RR]      # Continue processing
  qD:
    _0: [qD, _0, SL]      # Move left to start of tape 2
    _!: [qA, _!, SR]      # Found marker, accept

Wildcard Transitions

Turing Machines support wildcard symbols (?) in transition rules, allowing you to write more concise and general transitions. The wildcard ? matches any symbol in the tape alphabet.

Wildcard Precedence Rules

When multiple transition rules could apply to the current configuration, the simulator follows these precedence rules:

  1. Specific rules override wildcard rules: A transition with exact symbols takes priority over one with wildcards
  2. More specific wildcards override less specific: Rules with fewer wildcards take priority over those with more wildcards
  3. First match wins: Among rules of equal specificity, the first one encountered in the delta definition is used

Wildcard Examples

Single-tape wildcards:

delta:
  q1:
    '?': [q2, x, R]    # Replace any symbol with 'x', move right
    '0': [q3, '0', L]   # Specific rule: if '0', stay '0', move left

Multi-tape wildcards:

delta:
  q1:
    '?_': [q1, '?_', RS]  # Copy any symbol from tape 1, stay/right
    'a_': [q2, 'a0', RR]  # Specific: if 'a', also write '0' on tape 2

Precedence in action: For input symbol 'a' on tape 1 with blank on tape 2:

See full example: count-a-wildcard.tm - Demonstrates wildcard usage for counting 'a' symbols

See full example: w-marker-w-wildcard.tm - Shows wildcards in palindrome recognition

📝 Wildcard Best Practices: Use wildcards to handle general cases and specific rules for special cases. This creates cleaner, more maintainable TM definitions.

TM String Output

For Turing Machines, the simulator displays both:

📝 Performance: TM computation is limited to 1,000,000 steps. If this limit is reached, you'll see "MAX_STEPS=1,000,000 limit reached" instead of accept/reject.

CFG (Context-Free Grammar)

Define production rules using YAML mapping:

Example: Grammar for balanced parentheses

# CFG generating language of balanced () parentheses

S: [(S), SS, '']

This defines: S → (S) | SS | ε

Regex (Regular Expression)

Define subexpressions and main expression:

Example: Binary strings containing "010"

# Matches any binary string containing the substring 010
B = (0|1)*  # subexpression matching any binary string
B 010 B

Advanced Features

Local Storage

Your automaton definitions are automatically saved in your browser's local storage. This means your work persists between sessions, but it's stored locally on your device only.

Run Modes

Themes

Choose from multiple editor themes via View → Theme including:

Tips and Best Practices

💡 Comments: Use # comments liberally to document your automata. They help understand complex logic and are ignored by the parser.
💡 State Names: Use descriptive state names like reading_zeros instead of q1 to make your automata more readable.
💡 Testing: Test your automata with various inputs including edge cases like empty strings, very short inputs, and boundary conditions.
📝 Browser Compatibility: This simulator works best in modern browsers like Chrome, Firefox, Safari, and Edge. JavaScript must be enabled.

Troubleshooting

Common Errors

Performance Issues

Further Resources

This simulator was built with SolidJS and TypeScript.