This webpage hosts the materials required for the course.

Schedule

Syllabus

Module 1 — Formal Language Fundamentals Alphabets, strings, languages; Kleene star; language operations; finite specification of languages; regular expressions; context-free grammars; Chomsky hierarchy classification.

Module 2 — Finite Automata and Regular Languages DFA; NFA; NFA-to-DFA conversion; minimization; regular language recognition; Myhill-Nerode theorem; pumping lemma for regular languages; limitations of finite automata.

Module 3 — Context-Free Grammars and Pushdown Automata CFG; CFG simplification and normal forms (CNF, GNF); parse trees; ambiguity; pushdown automata (PDA); CFG-PDA equivalence; deterministic vs. non-deterministic PDA; pumping lemma for CFLs.

Module 4 — Turing Machines and Computability Context-sensitive grammars and linear bounded automata; Turing machine definition and variants (single-tape, multi-tape, non-deterministic); Church-Turing thesis; decidability; the halting problem; universal Turing machine; Turing completeness.

Module 5 — Undecidability and Reduction Techniques Undecidable problems; proof techniques and reduction methods; recursion theorem; Rice’s theorem; Post’s correspondence problem; practical undecidable problems in computer science; Turing unrecognizability.

Module 6 — Hilbert’s Problems and Computational Limits Hilbert’s tenth problem; the word problem; Church-Turing thesis implications; consequences of undecidability; limits of computation.

Module 7 — Alternative Computational Models Limitations of classical computation; quantum computing fundamentals (qubits, superposition, quantum gates); DNA computing; hypercomputation and oracle machines; future directions in computational theory.

Course materials

# Topics Materials Flashcards Mindmap
Unit 1 Formal Language Fundamentals   Flashcards  
Unit 2 Finite Automata and Regular Languages   Flashcards  
Unit 3 Context-Free Grammars and Pushdown Automata   Flashcards  
Unit 4 Turing Machines and Computability      
Unit 5 Undecidability and Reduction Techniques      
Unit 6 Hilbert’s Problems and Computational Limits      
Unit 7 Alternative Computational Models