Overview
This course develops the mathematical foundations of computation through formal languages, abstract computational models, computability, and computational complexity. Students begin with proof techniques, sets, relations, functions, induction, and formal reasoning before studying alphabets, strings, languages, regular expressions, deterministic and nondeterministic finite automata, epsilon transitions, equivalence, minimization, closure properties, and the pumping lemma for regular languages.
The course then examines context-free grammars, parse trees, ambiguity, normal forms, pushdown automata, closure properties, and the pumping lemma for context-free languages. The computability component addresses Turing machines, equivalent machine variants, encodings, decidability, recognizability, reductions, diagonalization, the halting problem, and fundamental undecidable languages. An introduction to complexity distinguishes tractable and intractable problems and includes P, NP, polynomial-time reductions, NP-completeness, and representative examples.
Students construct and compare computational models, prove language properties, design automata and grammars, formulate reductions, distinguish decidable from undecidable problems, and communicate rigorous mathematical arguments. Assessment emphasizes formal proofs, model construction, problem sets, examinations, and a computational theory project.
Learning Outcomes
- Construct rigorous mathematical proofs using induction, contradiction, direct reasoning, and related proof techniques.
- Analyze and compare regular expressions, deterministic finite automata, nondeterministic finite automata, and epsilon-transition automata.
- Prove language properties using closure arguments, equivalence results, minimization procedures, and pumping lemmas.
- Design context-free grammars and pushdown automata for specified languages and evaluate ambiguity and normal forms.
- Formulate and justify Turing machine constructions, encodings, reductions, and equivalence arguments.
- Distinguish decidable, recognizable, and undecidable languages using diagonalization, reductions, and halting-problem arguments.
- Classify computational problems by tractability and intractability and evaluate polynomial-time reductions and NP-completeness claims.
- Communicate computational theory solutions through precise notation, structured proofs, formal models, and reproducible computational examples.
Timetable
| Type | Length | Frequency | Period |
|---|---|---|---|
| Lecture | 2 hours | Weekly | All semester |
| Tutorial | 2 hours | Weekly | All semester |
| Lab | 2 hours | Fortnightly | All semester |
Assessment Schedule
| Type | Description | Weighting |
|---|---|---|
| Assignment | Weekly problem sets (10 × 3%) | 30.00% |
| Capstone | Automata and grammar construction project | 15.00% |
| Exam | Mid-semester examination | 20.00% |
| Test | Formal proof and reduction test | 15.00% |
| Exam | Final examination | 20.00% |
Prerequisites
Teaching Staff & Programs
This course is delivered jointly by faculty from the participating programs listed below. In line with the Douchewater Way, the University of Sexology tailors core instruction directly to each cohort's specific discipline — adapting curriculum to program needs rather than forcing students into a one-size-fits-all model. Learn more about our approach at The Douchewater Way.
