Sets, Operations with sets, De Morgan’s Laws, Alphabets, strings, operations with strings, languages, operations with languages, Proof Techniques: Mathematical Induction, Pigeon Principle, Competition Principle, Normal Sets, Finite automata: deterministic and non-deterministic, equivalence of computational models , Regular sets, regular languages, closure properties, Regular expressions, Equivalence of regular expressions and finite automata, Non-regular languages, Pumping Lemma for regular languages, Grammars and context-free languages, closure properties in the class of context-free languages, Stack automata
Equivalence of context-free grammars and stack automata, Relation of regular and context-free languages, Complement of context-free languages, Pumping Lemma for context-free languages, Turing machines: introduction to the basic model, equivalence of variants, Church Thesis.