Theory of Computation Lab
Every theory of computation tool on the site, from finite automata to Turing machines and grammars. Draw or describe a machine, trace a string, and see each construction step by step.
1. Finite automata and regular languages
Draw and trace DFAs and NFAs, turn an NFA into a DFA with subset construction, minimize it, and build an NFA from a regular expression with Thompson's construction. Every result can be passed straight to the next tool.
Finite Automata Simulator (NFA/DFA)
Draw a finite automaton and trace strings step by step
NFA to DFA Converter
Turn an NFA into a DFA with the subset construction shown
DFA Minimizer
Merge equivalent DFA states and see each minimization step
Regex to NFA Converter
Turn a regular expression into an NFA diagram
2. Pushdown automata and Turing machines
Watch the stack of a PDA at every move, including ε-moves and nondeterminism, and run Turing machines step by step on the tape.
3. Context-free grammars
Draw parse trees and find ambiguous strings, convert a grammar to Chomsky normal form, and test membership with the CYK table.
Other labs
Frequently asked questions
Is this a replacement for JFLAP?
For finite automata, PDAs and Turing machines it covers most of what a course needs, in the browser with no Java. JFLAP still does more with grammars and some machine types; see the JFLAP comparison page for the details.
Can I build a DFA from the question text?
Yes. Type a description such as "strings over {a,b} ending with ab" in the DFA and NFA simulator and it builds the minimal DFA, which you can then trace or minimize.
Can I share an automaton with my class or lecturer?
Yes. The finite automaton tools make a share link that opens the same machine, and can export LaTeX TikZ code and PNG images for reports.