Erudex sealErudex
Software & AI Engineering
All levels

Theory of Computation

Academic (University) preparation with worked examples, written practice and independent learning assessments.

Independent university-level study of Theory of Computation. This original curriculum draws on public academic subject descriptions; it is not an official faculty syllabus, university credit, accreditation or an Ivy League qualification. Topics covered: Languages; Alphabets; Strings; Decision problems. Finite automata; Regular expressions; Closure properties; Pumping lemma. Context-free grammars; Pushdown automata; Parse trees; Ambiguity. Turing machines; Encodings; Universal computation; Church-Turing thesis. Decidability; Reductions; Halting problem; Rice theorem. Time complexity; Polynomial reductions; NP completeness; Cook-Levin theorem. Space complexity; PSPACE; Hierarchy theorems; Randomized classes. Computability boundaries; Approximation barriers; Proof construction; Complexity case studies. Projects use safe simulations, public datasets or textual analysis; specialist subject review is required. Includes lessons, supplementary YouTube tutorials, practical exercises, quizzes and free/paid practice tests. Erudex is independent, not affiliated with the source institution or awarding body. Its 80% learning checks are not official grades or university credit. Content requires qualified subject review before use as a complete teaching programme.

32h Certificate available
InternationalAcademic (University)Independent preparation

Curriculum

One complete track with its own final exam and certificate.

Independent university-level study of Theory of Computation. This original curriculum draws on public academic subject descriptions; it is not an official faculty syllabus, university credit, accreditation or an Ivy League qualification. Topics covered: Languages; Alphabets; Strings; Decision problems. Finite automata; Regular expressions; Closure properties; Pumping lemma. Context-free grammars; Pushdown automata; Parse trees; Ambiguity. Turing machines; Encodings; Universal computation; Church-Turing thesis. Decidability; Reductions; Halting problem; Rice theorem. Time complexity; Polynomial reductions; NP completeness; Cook-Levin theorem. Space complexity; PSPACE; Hierarchy theorems; Randomized classes. Computability boundaries; Approximation barriers; Proof construction; Complexity case studies. Projects use safe simulations, public datasets or textual analysis; specialist subject review is required.

Languages; Alphabets; Strings; Decision problems

  • Alphabets, Symbols, and Foundational Formal Structures Lab60 min
  • Strings: Operations, Structural Induction, and Lexicographic Orders Lab60 min
  • Formal Languages: Set Operations, Kleene Star, and Cardinality Bounds Lab60 min
  • Decision Problems, Binary Encodings, and Characteristic Functions Lab60 min

Careers this prepares you for

    How you study

    Every lesson pairs an in-depth video with written notes, key takeaways, a hands-on lab, exercises and a quiz. Work at your own pace, then sit the final examination for your Erudex certificate.