ToolSphere
All tools

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.

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.