Notes on the lectures

Lecture 1:

The mathematical preliminaries and examples of proof techniques should be a review of topics covered in CSE 1019 (or equivalent) for you. If you had any difficulty with any of these, please browse a Discrete Math book (Chapter 0 of the text is very brief). If you took 1019 at York, you (very likely) used the text by Rosen.

The most important new concept in this lecture is the idea of recognizing languages. This idea is initially cumbersome to many students. If you do not become comfortable with this idea, you may find many of the later topics difficult.

The second most important concept is the idea that decision problems are as general as (the usual) input/output problems.

Reading: Ch 0
Exercises: Problems 0.1, 0.10-0.13 in Edition 3, 0.1, 0.10-0.12 in Edition 2 (Problem 0.11 in Edition 3 is not in Edition 2).

Lecture 2:

We used the same slides as the last class, and covered a quick review of logic and functions, followed by the definitions of, and relationship between, input/output problems, decision problems and languages.

The most important concept in this class was the equivalence of the three forms of writing a function.

It is also good to remember why we are doing all this. We would like to make claims of the form "Model A can compute function every function B can, and further it can compute a function f, but model B cannot", which would imply model A is strictly more powerful than B. To simplify the math, what we will (typically) prove is "Model A accepts every language model B accepts and in addition a language L that model B cannot accept".

Lecture 3:

Students have a lot of trouble with proofs, and for good reason. A very enjoyable article on proofs is here.
Here is a good pedagogic discussion (not required reading): link.

We saw several different types of proofs today. We also saw the Pigeonhole principle that we use quite a bit in this course. We then covered recursive definitions of sets.

We covered the (informal) definition of deterministic finite automata today. Please remember three crucial aspects -- finite alphabet, finite number of states and all possible edges drawn.

Lecture 4:

We will see several examples of DFA design.

Lecture 5:

We covered some complicated DFA constructions, particularly the union construction and then highlighted the difficulty of the concatenation construction. Then we introduced nondeterminism, This is not an easy concept and needs some reflection. We also constructed some NFAs. Please practice DFA and NFA construction.

Lecture 6:

We covered closure of regular languages under regular languages using NFA. Note how using NFA's simplifies the construction vastly.

Lecture 7:

We cover a big result -- the equivalence of DFA's and NFA's.