Skip to content
Tutorials Center
My learning

Topics

Theory of Computation Tutorial

Learn the Theory of Computation step by step: 59 lessons in 11 chapters on automata, regular languages, grammars, pushdown automata, Turing machines, decidability and complexity.

Start learning →

of lessons completed

Getting Started

  1. 1 What Is the Theory of Computation? Learn what the theory of computation studies: abstract machines, languages, decision problems and the limits of what computers can solve, with Python examples.
  2. 2 Alphabets, Strings and Languages Learn the building blocks of automata theory: alphabets, strings, length, concatenation, powers, Kleene star and operations on languages, with Python code.
  3. 3 Grammars and the Chomsky Hierarchy Understand formal grammars, productions and derivations, then classify any grammar into the four Chomsky types with working Python code and examples.
  4. 4 Applications of Automata See where automata are used in practice: lexical analysis, string search, protocol state machines, game logic and hardware, with runnable Python examples.

Finite Automata

  1. 5 Introduction to Finite Automata and DFAs Learn the formal definition of a DFA, how to read state diagrams and transition tables, dead states and acceptance, with a runnable Python DFA simulator.
  2. 6 Designing DFAs: Common Patterns Learn proven DFA design patterns: counting modulo k, substrings, the k-th symbol from the right, combined conditions and divisibility, each tested in Python.
  3. 7 Nondeterministic Finite Automata and ฮต-Moves Learn nondeterministic finite automata: multiple transitions, guessing, ฮต-moves and epsilon closure, with a Python simulator that tracks sets of states.
  4. 8 Converting an NFA to a DFA (Subset Construction) Learn the subset construction that converts any NFA or ฮต-NFA into an equivalent DFA, with step-by-step tables, a Python implementation and the exponential blowup.
  5. 9 Operations on DFAs: Complement, Union, Concatenation, Reverse Learn how to build DFAs for the complement, union, intersection, concatenation and reversal of regular languages, with the product construction and Python code.
  6. 10 Minimization of DFAs Learn how to minimize a DFA by removing unreachable states and merging equivalent states, using partition refinement and the table-filling method, with Python code.
  7. 11 Mealy and Moore Machines Learn Mealy and Moore machines, finite state transducers that produce output, how they differ, how to convert between them, with a binary adder and Python code.

Regular Expressions and Languages

  1. 12 Regular Expressions, Regular Grammars and Regular Languages Learn the formal definition of regular expressions, the languages they describe, algebraic identities, regular grammars and star height, with Python examples.
  2. 13 From Regular Expressions to Finite Automata (Thompson's Construction) Learn how to convert any regular expression into an ฮต-NFA with Thompson's construction, then to a DFA, with diagrams and a working Python regex compiler.
  3. 14 From Finite Automata to Regular Expressions: Arden's Theorem and State Elimination Learn Kleene's theorem and two methods for converting a finite automaton to a regular expression, Arden's theorem and state elimination, with Python code.
  4. 15 Closure Properties and Decision Properties of Regular Languages Learn which operations keep a language regular, union, complement, intersection, reversal, homomorphism and more, plus decision algorithms for emptiness and equivalence.
  5. 16 The Pumping Lemma for Regular Languages Learn the pumping lemma for regular languages, why it holds, and how to prove that a^n b^n, prime-length strings and other languages are not regular, with code.

Context-Free Grammars

  1. 17 Context-Free Grammars, Derivations and Parse Trees Learn context-free grammars, leftmost and rightmost derivations, parse trees and how a grammar defines a language, with design patterns and Python code.
  2. 18 Ambiguity in Context-Free Grammars and Languages Learn what makes a context-free grammar ambiguous, how to detect it, how to remove ambiguity with precedence and associativity, and what inherent ambiguity means.
  3. 19 Simplifying Context-Free Grammars Learn how to simplify a context-free grammar by removing useless symbols, ฮต-productions and unit productions in the right order, with a Python implementation.
  4. 20 Chomsky Normal Form and Greibach Normal Form Learn how to convert a context-free grammar to Chomsky Normal Form and Greibach Normal Form, remove left recursion and use CNF in the CYK parsing algorithm.
  5. 21 Closure Properties of CFLs and the Pumping Lemma for CFLs Learn which operations keep a language context-free, why intersection and complement fail, and how to prove a language is not context-free with the pumping lemma.

Pushdown Automata

  1. 22 Introduction to Pushdown Automata Meet the pushdown automaton: a finite automaton with a stack. Learn its formal definition, how a computation runs, and simulate a PDA in Python.
  2. 23 PDA Acceptance and Equivalence with CFGs Compare PDA acceptance by final state and by empty stack, convert between them, and turn any context-free grammar into an equivalent PDA in Python.
  3. 24 Deterministic vs Nondeterministic PDA Understand deterministic and nondeterministic pushdown automata, why NPDAs are strictly stronger, and test determinism of a PDA with Python.
  4. 25 PDAs for Matching Counts: a^n b^n and Friends Design pushdown automata for languages where one block of symbols must match another: a^n b^n c^m, a^n b^m c^n, a^m b^2m and more, with Python checks.
  5. 26 PDAs for Sums of Counts: a^m b^n c^(m+n) and More Design PDAs where one block equals the sum of others: a^m b^n c^(m+n), a^m b^(m+n) c^n, 0^n 1^m 2^m 3^n, m+n=p+q and a^2m c^4n d^n b^m, tested in Python.
  6. 27 PDAs for Either/Or Conditions and Equal Counts Build nondeterministic PDAs that guess which condition holds (i=k or j=l, i=j or j=k) and a one-state PDA for strings with equally many a's and b's.
  7. 28 PDAs for Palindromes and Reversal Languages Construct pushdown automata for even palindromes w w^R, odd palindromes, all palindromes and the marked version w c w^R. Includes runnable Python checks.

Context-Sensitive and Other Models

  1. 29 Context-Sensitive Grammars and Languages Learn context-sensitive grammars: the non-contracting rule, the grammar for a^n b^n c^n, derivations, and a Python tool that classifies grammars by Chomsky type.
  2. 30 Linear Bounded Automata A linear bounded automaton is a Turing machine whose tape is limited to the input. Learn how LBAs match context-sensitive languages and detect infinite loops.
  3. 31 Counter Machines, Two-Stack Machines and Other Models Explore automata beyond the PDA: counter machines, two-stack machines and queue automata, and why two stacks already equal a Turing machine. Python demos included.

Turing Machines

  1. 32 Turing Machines: Definition and First Examples Learn what a Turing machine is: tape, head, states and transitions. Build and trace a machine for 0^n 1^n and a binary incrementer with a Python simulator.
  2. 33 Variants of Turing Machines and the Church-Turing Thesis Multi-tape, nondeterministic and other Turing machine variants all have the same power. Simulate them in Python, then meet the Church-Turing thesis and universal TMs.
  3. 34 Turing Machines for Addition, Subtraction, Multiplication and Comparison Design Turing machines that add, subtract, multiply and compare unary numbers. Each construction is explained state by state and tested in a Python simulator.
  4. 35 Turing Machines for Copying Data and 1's and 2's Complement Build Turing machines that copy a string and compute the 1's and 2's complement of a binary number. Marker technique, state diagrams and Python checks included.
  5. 36 Turing Machines for 0^n 1^n 2^n, w w^R and w w Construct Turing machines for languages that need more than a stack: 0^n 1^n 2^n, even palindromes w w^R and the copy language ww. Python simulator and tests.
  6. 37 Turing Machines for a^n b^m a^(n+m) and a^i b^j c^(i*j) Design Turing machines for languages built from sums and products of block lengths: a^n b^m a^(n+m) and a^i b^j c^k with i*j=k. Includes state design and Python tests.

Decidability and Computability

  1. 38 Recursive and Recursively Enumerable Languages Understand Turing-decidable (recursive) and Turing-recognizable (recursively enumerable) languages, enumerators, closure properties and why co-RE matters, with Python.
  2. 39 Countability, Diagonalization and Decidable Problems Why most languages are unrecognizable: countable and uncountable sets, Cantor's diagonal argument, and a tour of decidable problems for DFAs and CFGs in Python.
  3. 40 The Halting Problem: Proof of Undecidability State and prove the halting problem is undecidable by diagonalization. See the contradiction in Python and learn why A_TM is recognizable but not decidable.
  4. 41 Reductions, Rice's Theorem and the Post Correspondence Problem Prove problems undecidable by reduction from the halting problem, learn Rice's theorem on semantic properties, and explore the Post Correspondence Problem in Python.
  5. 42 Computable Functions, Ackermann and the Busy Beaver Learn total and partial computable functions, primitive recursion, the mu operator, the Ackermann function and the uncomputable busy beaver function with Python.

Complexity

  1. 43 Time Complexity and the Class P Measure how many steps a Turing machine takes, define DTIME and the class P, see why input size matters, and run a Python machine that counts its own steps.
  2. 44 Nondeterminism and the Class NP Learn what NP means with two equivalent views, nondeterministic machines and polynomial-time verifiers, then check certificates for Subset Sum and Hamiltonian paths in Python.
  3. 45 Polynomial-Time Reductions Understand polynomial-time many-one reductions, how to read A <=p B, and why reductions transfer hardness. Test Partition to Subset Sum and Clique to Independent Set.
  4. 46 NP-Completeness and the Cook-Levin Theorem Define NP-hard and NP-complete, follow the idea behind the Cook-Levin theorem, then run a SAT brute-force and DPLL solver and a SAT to 3-SAT converter in Python.
  5. 47 Classic NP-Complete Problems Meet the classic NP-complete problems and their reduction chain: 3-SAT, Clique, Independent Set, Vertex Cover, Hamiltonian cycle and TSP, with tested Python reductions.
  6. 48 Space Complexity, PSPACE and Savitch's Theorem Learn how memory is measured on a Turing machine, the classes L, NL and PSPACE, Savitch's theorem and TQBF, with Python demos of recursive reachability and QBF.
  7. 49 The Complexity Hierarchy and the P versus NP Question See how complexity classes nest, why more time buys more power (the hierarchy theorems), what P versus NP would change, and run a diagonalization demo and a feasibility table.
  8. 50 Coping with NP-Hard Problems What to do when a problem is NP-hard: approximation algorithms, heuristics, special cases, parameterized algorithms and randomization, with Python vertex cover and TSP examples.

Projects

  1. 51 Project: A DFA Simulator and Minimizer Build a complete finite automata toolkit in Python: a DFA simulator, union and complement, the subset construction from NFA to DFA, and a DFA minimizer you can test.
  2. 52 Project: A Regular Expression Engine Build a regular expression matcher from scratch in Python: parse a regex, build an NFA with Thompson's construction, simulate it in linear time and test it against Python's re module.
  3. 53 Project: A Grammar Toolkit with CNF Conversion and a CYK Parser Build a context-free grammar toolkit in Python: remove epsilon and unit rules, convert to Chomsky normal form, parse with the CYK algorithm, count parse trees and test everything.
  4. 54 Project: A Turing Machine Simulator Build a Turing machine simulator that reads rules from plain text, prints step-by-step traces, decides palindromes and increments binary numbers, and searches for busy beavers.

Practice and Review

  1. 55 Practice: Finite Automata and Regular Languages Worked practice problems on DFAs, regular expressions, the pumping lemma and Myhill-Nerode, with every solution checked by a Python test harness you can run and extend.
  2. 56 Practice: Grammars and Pushdown Automata Practice designing context-free grammars and pushdown automata, prove languages are not context-free, and check every answer with a PDA simulator and a grammar tester.
  3. 57 Practice: Turing Machines and Decidability Practice problems on designing Turing machines, classifying languages as decidable, recognizable or neither, and writing reduction proofs, with machines verified by a Python simulator.
  4. 58 Practice: Complexity Problems Practice problems on P, NP, verifiers, reductions and NP-completeness proofs, with tested Python verifiers, a Hamiltonian path reduction, 2-SAT in P and pseudo-polynomial DP.
  5. 59 Theory of Computation Review and Cheat Sheet A complete review of the Theory of Computation: the Chomsky hierarchy, closure and decision properties, key theorems, complexity classes, plus runnable demos of the pigeonhole argument and decision algorithms.