Theory of Computation

What you'll learn

The key areas this subject covers, mapped to the official curriculum.

• Formal models: DFA, NFA, PDA and Turing machines
• Equivalence between automata, regular expressions and grammars
• The hierarchy of formal languages (Chomsky hierarchy)
• Decidable vs undecidable problems via reduction
• Complexity classes P, NP and NP-completeness

Course units

The structured path through this subject.

1. 1

   Basic Foundations

   The mathematical toolkit - sets, strings, induction and proof techniques - used throughout the course.

   4 topics · 4 lessons available

2. 2

   Introduction to Finite Automata

   Deterministic and non-deterministic finite automata and what they can and cannot recognize.

   5 topics · 5 lessons available

3. 3

   Regular Expressions

   Algebraic descriptions of regular languages and the closure and decision properties that make them tractable.

   5 topics · 5 lessons available

4. 4

   Context Free Grammar

   Grammar-based generation of context-free languages, parse trees, ambiguity and normal forms.

   5 topics · 5 lessons available

5. 5

   Push Down Automata

   Automata with a stack that recognize exactly the context-free languages.

   4 topics · 4 lessons available

6. 6

   Turing Machines

   The most powerful machine model, variants, and the languages it can decide and enumerate.

   5 topics · 5 lessons available

7. 7

   Undecidability and Intractability

   Problems that no algorithm can solve, and problems that are too hard to solve efficiently.

   5 topics · 5 lessons available