Automata Theory

DFAs, Regex, PDAs, and Turing Machines.

Parameters

Preset DFA

Input String

Regex Pattern

Test Strings (one per line)

Input

Tape Input

Quick Reference

a|b → a or b

a* → 0+ repetitions

a+ → 1+ repetitions

a? → optional

^ → start, $ → end

[abc] → char class

Automata & Formal Languages Handbook

Mathematical Principles & Theorems

Models Deterministic Finite Automata (DFA) \(M = (Q, \Sigma, \delta, q_0, F)\) where \(Q\) is states, \(\Sigma\) is alphabet, \(\delta: Q \times \Sigma \to Q\) is transition function, \(q_0\) is start state, and \(F \subseteq Q\) is accept states. Kleene's Theorem establishes equivalence between DFAs, Non-Deterministic Automata (NFA), and Regular Expressions. The Pumping Lemma proves non-regularity by stating \(\forall s \in L\) with \(|s| \ge p\), \(s = xyz\) with \(|xy| \le p, |y| > 0\) such that \(xy^i z \in L, \forall i \ge 0\).

Operating Instructions

Select an automaton preset (e.g., Even binary numbers, Alternating bits, Substring search) or construct custom states.
Enter an arbitrary test string in the input field.
Use 'Step' to step through transitions one symbol at a time or 'Run' to evaluate total acceptance.
Watch active state nodes highlight on the interactive graph canvas and review transition history.