Lectures Regular expressions. Specifying sets of strings by pattern-matching. Finite state machines. Deterministic and non-deterministic finite automata and the languages they accept. The language determined by a regular expression is regular.
Every regular language is determined by some regular expression.
The Pumping Lemma. Proof and applications. Context-free and regular grammars. The class of regular languages coincides with the class of languages generated by a regular grammar. Automata and Computability .