2023 Fall

Theory of Computation, Acquincum Institute of Technology, Wednesday 16:00-17:50, Friday 9:00-10:50

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

Midterm: October 20, Final Exam: December 13.

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

Week 2

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.

Week 3

"Reduction method" to prove non-regularit of languages. Context-free grammars/languages (CFG/CFL), corresponding parse trees and reduction steps to generate words, formal definition of CFG, Union, concatenation, star of CFLs also CFL, regular languages are CF, Pushdown automata.
Recommended extra practice exercises: 2.1-14, 2.30, 2.32

Week 4

CFL iff there is a PDA recognizing it, Pumping Lemma for CFLs, adversary game, complement and intersection of CFLs, intersection of CFL with regular language is CF,
Recommended extra practice exercises: 2.42-46