Theory of Computation (TOC)
Zero-fluff theoretical computer science notes, formal language derivations, finite state automaton schematics, computational limits proofs, and high-yield interview frameworks for university semester exams, systems engineering, and foundational computing.
Foundations & Deterministic Finite Automata (DFA)
Formal alphabet definitions, combinatorial substring counting formulas, 5-tuple DFA formalisms, state transition tables, modulo-N divisibility, cross-product construction, and complementation invariants.
NFA, Subset Construction & DFA Minimization
Non-deterministic finite automata (NFA), epsilon-NFA transitions, epsilon-closure, subset construction algorithm (power set 2^Q), unreachable state elimination, and Myhill-Nerode table-filling minimization.
Finite Automata with Output (Moore & Mealy Machines)
State-associated vs transition-associated output models, output string length relations, timing diagrams, and bidirectional state conversion algorithms between Moore and Mealy machines.
Regular Expressions & Arden's Theorem
Regular expression algebraic identities, language modeling, Arden's theorem state elimination proofs (R = Q + RP implies R = QP*), and algorithmic conversion from finite automata to regular expressions.
Regular Grammars & The Chomsky Hierarchy
Formal phrase-structure grammar 4-tuple, derivation conventions, the 4-level Chomsky hierarchy, Type-3 Right-Linear and Left-Linear regular grammars, and interconversions with finite automata.
Regular Language Identification, Pumping Lemma & Properties
Memory constraints of finite state systems, adversarial game formulations of the Pumping Lemma for regular languages, non-regularity proofs, decision algorithms, and closure property theorems.
Context-Free Grammars (CFG) & Normal Forms
Context-free grammar formalisms, derivation parse trees, leftmost vs rightmost derivations, ambiguity detection, inherently ambiguous languages, simplification, and Chomsky & Greibach Normal Forms.
Pushdown Automata (PDA) & CFL Properties
Stack-augmented automaton architecture, instantaneous descriptions, acceptance by final state vs empty stack equivalence, deterministic PDA (DPDA) vs NPDA, and CFL decision/closure matrices.
Turing Machines & Linear Bounded Automata (LBA)
Universal computational models, infinite tape head mechanics, transition functions, Church-Turing thesis, multi-tape/non-deterministic variants, Linear Bounded Automata, and Context-Sensitive Languages.
Decidability, Undecidability & Complexity Theory
Recursive (REC) vs Recursively Enumerable (RE) languages, Turing halting problem, Post Correspondence Problem (PCP), Rice's theorem, reductions, Class P, Class NP, and NP-Completeness.