2023 Spring

Theory of Computation, Acquincum Institute of Technology, Wednesday 14:00-15:50, Friday 14:00-15:50

Book: Sipser, Michael. Introduction to the Theory of Computation. 3rd Edition.
Slides: check on Moodle


Feb 8, Wednesday: Decision Problems, Languages, Definition of (deterministic) finite automata, regular language, examples.
Recommended extra practice exercises: 1.3 and 1.6 from Sipser book.
Feb 10, Friday: Complement, union and intersection of regular languages are regular, Definition of Non-deterministic Finite Automata, equivalence to a deterministic automata
Recommended extra practice exercises: 1.4, 1.5, 1.7, 1.13 from Sipser book.


Feb 15, Wednesday and Feb 17, Friday: Proof of closure of regular languages under regular operations using NFAs.
Definition of regular expressions, examples. Regular iff described by RE, converting RE to equivalent NFA, Pumping Lemma.
Recommended extra practice exercises: 1.8, 9, 10, 12, 15, 16, 17, 18, 19, 20, 29.


Feb 22, Wednesday and Feb 24, Friday: Context-free grammars/languages (CFG/CFL), reduction steps to generate words, formal definition of CFG, Union, concatenation, star of CFLs also CFL, regular languages are CF (without proof). Pushdown automata, examples, CFL iff there is a PDA recognizing it.
Recommended extra practice exercises: 2.1-14, 2.30, 2.32


Mar 1, Wednesday and Mar 3, Friday: Pumping Lemma for CFLs, adversary game, complement and intersection of CFLs, intersection of CFL with regular language is CF, Turing machines, formal definition. Recursive and recursively enumerable languages.
Recommended extra practice exercises: 2.42-46


Mar 8, Wednesday and Mar 10, Friday: T_M(n) or computational time of a TM, Modifying a TM for more/less power: (no 'stay' of tape head, only halting states are accept and reject, one way infinite tape, multitape TM, non-deterministic TM)
Recommended extra practice exercises: 3.1,2,5,7,8,9,10,11,12


Mar 17, Friday: