Mathematics for Computation Theory

Lecturer: Dr J.K.M. Moody (km@cl.cam.ac.uk)

No. of lectures + classes: 12 + 3  

Part A. Discrete Mathematics

Modelling discrete systems.

Computation as a discrete process. Sets: membership, subsets, union, intersection, complement, difference. Symmetric difference. Boolean algebra. Venn diagrams.

Constructions on sets.

Cartesian product. Disjoint union (connection with datatypes). Relations as a subset of a product. Binary relations. Functions and partial functions. Multi-sets (bags).

Algebra of relations.

Product and inverse relations. Composition of functions. Bijections. Function spaces. Power set. Predicates, characteristic functions. n-ary predicates. Examples of natural bijections between sets.

Relations on a set.

Reflexive, symmetric and transitive properties of a relation on a set. Equivalence relations. Orders, partial and total. Examples.

Principle of induction.

Well-ordering, partial and total. Mathematical induction. Algebraic structures. Structural induction. Examples.

Part B. Finite Automata and Regular Languages

Deterministic finite automata (DFA).

Mechanical recognition of strings in a language. Stimulus-response behaviour, event detection. Mealey machines, Moore machines. Examples. Accepting strings via some output of a DFA. Examples.

Using automata to recognize languages.

Events/languages as sets of strings. Non-deterministic finite automata (NDFA). Proof that the language classes accepted by DFAs and NDFAs coincide.

Algebraic operations on languages.

Finite union and intersection, concatenation, and Kleene closure. Regular expressions and the languages they denote. Examples of regular languages, including recognizers.

Kleene's theorem.

Arden's rule as a recursive definition. Its proof by induction. Extension to matrices of events. Statement of Kleene's Theorem, including an overview of the proof structure. Regular events can be represented: proof by induction on the event structure using NDFAs. Representable events are regular: proof by induction on the number of states using transition matrices and Arden's rule.

Properties of regular languages.

Strings accepted by an n-state machine. The Pumping Lemma. Examples of languages that are not regular, including palindromes. Complements and intersections of regular languages are regular. Some decidable problems for regular languages. Extended regular expressions. A non-elementary problem. (Cook's tour)

Recommended books:

Stanat, D.F. & McAllister, D.F. (1977). Discrete Mathematics in Computer Science. Prentice-Hall.

Stone, H.S. (1973). Discrete Mathematical Structures and their Applications. SRA.

Hopcroft, J.E. & Ullman, J.D. (1979). Introduction to Automata Theory, Languages and Computation. Addison-Wesley.

Hopcroft, J.E. & Ullman, J.D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley.

Conway, J.H. (1971). Regular Algebra and Finite Machines. Chapman and Hall.

Sudkamp, T.A. (1988). Languages and Machines. Addison-Wesley.