Theory of Computation
DFA, NFA, grammars, derivations, Turing machines
99 simulators found.
DFA String Acceptance Checker
DFA String Acceptance Checker — interactive visual simulator with step-by-step explanation and exam answer format.
DFA State Transition Visualizer
DFA State Transition Visualizer — interactive visual simulator with step-by-step explanation and exam answer format.
NFA String Acceptance Checker
NFA String Acceptance Checker — interactive visual simulator with step-by-step explanation and exam answer format.
NFA to DFA Conversion Basic
NFA to DFA Conversion Basic — interactive visual simulator with step-by-step explanation and exam answer format.
Regular Expression to Automata Basic
Regular Expression to Automata Basic — interactive visual simulator with step-by-step explanation and exam answer format.
Grammar Derivation
Grammar Derivation — interactive visual simulator with step-by-step explanation and exam answer format.
Leftmost Derivation
Leftmost Derivation — interactive visual simulator with step-by-step explanation and exam answer format.
Rightmost Derivation
Rightmost Derivation — interactive visual simulator with step-by-step explanation and exam answer format.
Parse Tree Generator Basic
Parse Tree Generator Basic — interactive visual simulator with step-by-step explanation and exam answer format.
Turing Machine Basic Tape Demo
Turing Machine Basic Tape Demo — interactive visual simulator with step-by-step explanation and exam answer format.
Epsilon Closure
States reachable by epsilon moves.
DFA Minimization
Merge equivalent states into the smallest DFA.
Mealy Machine
Output produced on each transition.
Moore Machine
Output produced on each state.
Pumping Lemma
Prove a language is not regular.
CFG to CNF Conversion
Convert a grammar to Chomsky Normal Form.
PDA for a^n b^n
Pushdown automaton accepting a^n b^n by stack.
Language Classification
Classify a language by its machine.
Closure Properties
Closure of Regular vs Context-Free languages.
Chomsky Hierarchy
The four grammar types and their machines.
DFA: Ends with 0
DFA: Ends with 0 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Ends with 1
DFA: Ends with 1 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Ends with 01
DFA: Ends with 01 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Starts with 0
DFA: Starts with 0 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Starts with 1
DFA: Starts with 1 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Contains 01
DFA: Contains 01 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Contains 11
DFA: Contains 11 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Contains 101
DFA: Contains 101 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Even number of 0s
DFA: Even number of 0s — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Odd number of 0s
DFA: Odd number of 0s — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Even number of 1s
DFA: Even number of 1s — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Even 0s and Even 1s
DFA: Even 0s and Even 1s — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Even Length
DFA: Even Length — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Length Multiple of 3
DFA: Length Multiple of 3 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Binary Divisible by 3
DFA: Binary Divisible by 3 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: At Least Two 0s
DFA: At Least Two 0s — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: At Most One 1
DFA: At Most One 1 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Exactly Two 1s
DFA: Exactly Two 1s — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Third Symbol is 1
DFA: Third Symbol is 1 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: No Substring 00
DFA: No Substring 00 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: 0*1*
DFA: 0*1* — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Ends with 00
DFA: Ends with 00 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA over a,b: Ends with a
DFA over a,b: Ends with a — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: a count Multiple of 3
DFA: a count Multiple of 3 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DFA: Same Start and End
DFA: Same Start and End — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
NFA Basics
NFA Basics — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
NFA: Ends with 01
NFA: Ends with 01 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
NFA for Union
NFA for Union — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Epsilon-NFA
Epsilon-NFA — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
NFA to DFA Equivalence
NFA to DFA Equivalence — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Regex: a*
Regex: a* — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Regex: a+
Regex: a+ — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Regex: a?
Regex: a? — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Regex: a or b
Regex: a or b — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Regex: ab*
Regex: ab* — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Regex: Identifier
Regex: Identifier — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Regex: Binary Ending in 0
Regex: Binary Ending in 0 — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Regex: (ab)+
Regex: (ab)+ — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Regex: a(a|b)*b
Regex: a(a|b)*b — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Thompson Construction
Thompson Construction — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Context-Free Grammar
Context-Free Grammar — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Derivation
Derivation — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Ambiguous Grammar
Ambiguous Grammar — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Left Recursion
Left Recursion — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Left Factoring
Left Factoring — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
FIRST Set
FIRST Set — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
FOLLOW Set
FOLLOW Set — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
LL(1) Parsing Table
LL(1) Parsing Table — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Recursive Descent Parsing
Recursive Descent Parsing — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Shift-Reduce Parsing
Shift-Reduce Parsing — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Regular Grammar
Regular Grammar — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Right-Linear Grammar
Right-Linear Grammar — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Regular vs Context-Free
Regular vs Context-Free — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Greibach Normal Form
Greibach Normal Form — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Useless Symbols Removal
Useless Symbols Removal — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
PDA Definition
PDA Definition — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
PDA Acceptance by Final State
PDA Acceptance by Final State — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
PDA Acceptance by Empty Stack
PDA Acceptance by Empty Stack — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
PDA for Palindrome
PDA for Palindrome — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
PDA for Balanced Parentheses
PDA for Balanced Parentheses — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
CFG to PDA
CFG to PDA — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
DPDA vs NPDA
DPDA vs NPDA — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
PDA Stack Operations
PDA Stack Operations — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
PDA for a^n b^2n
PDA for a^n b^2n — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Two-Stack PDA
Two-Stack PDA — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Turing Machine Definition
Turing Machine Definition — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
TM for a^n b^n
TM for a^n b^n — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
TM Unary Addition
TM Unary Addition — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
TM String Copy
TM String Copy — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
TM Transition Table
TM Transition Table — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Multi-tape Turing Machine
Multi-tape Turing Machine — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Universal Turing Machine
Universal Turing Machine — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
TM Halting Outcomes
TM Halting Outcomes — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Recursive vs RE Languages
Recursive vs RE Languages — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Linear Bounded Automaton
Linear Bounded Automaton — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Halting Problem
Halting Problem — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Decidable vs Undecidable
Decidable vs Undecidable — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
P vs NP
P vs NP — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.
Rice's Theorem
Rice's Theorem — Theory of Computation simulator with a state-diagram / formal explanation and step-by-step trace.