Please enable JavaScript.
Coggle requires JavaScript to display documents.
COMP 330 Theory of Computation - Coggle Diagram
COMP 330 Theory of Computation
Regular Language & Finite Automata
Language
Deterministic Finite Automata (DFA)
Regular Language: a set of strings that are accepted by a DFA
Kleene's Theorem
Union, Concatenation, Star
Intersection, Difference, Complement, Reversal
Prove by constructing NFA
Prove Regular
Proof by reduction (Kleene's Theorem) / Other NFA
A language is regular iff some regular expression describe it
Prove by induction the language is recognized by some DFA
Prove Non-regular
Myhill-Nerode Theorem
Pumping Lemma
Inverse use of reduction from Kleene's Theorem
Regular Expression
Convert Regex to NFA
Convert NFG to Regex by constructing GNFA
Context-free Language & Pushdown Automata
Turing Machine, Computability & Complexity