Alphabets and languages. Finite automata. Properties of finite automata and their accepting languages. Regular expressions and regular languages. Equivalence of finite automata and regular expressions. The pumping lemma for regular expressions. Grammars and the Chomsky hierarchy. Context-free languages. Pushdown automata and the pumping lemma for context-free languages. Equivalence of context-free grammars and pushdown automata. The notion of computability. Turing Machines. Decidable and enumerable languages. Church-Turing thesis. Solvable and non-solvable problems. The halting problem. Introduction to computational complexity. Time complexity, the P class, the Cook-Karp thesis. Reduction and completeness. Non-determinism and NP-completeness, P vs. NP. Space complexity, the PSPACE class and PSPACE-complete problems.
