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

Week1

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.

Week2

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.

Week3

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

Week4

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

Week5

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

Week6

Mar 17, Friday: