Computer Science and Engineering 105
Introduction to the Theory of Computing
Summer 2003
Assignments

Revised August 4, 2003

Monday, June 30, 2003

Lecture subject: regular languages and finite automata

I will assume that you are familiar with the material in Sections 0.2 through 0.4 of your textbook, pages 3-27, since that material should have been covered in the prerequisite courses. In practice, this means that you should read these sections to make sure that you recall the material, and possibly ask questions in the discussion section tomorrow.
I recommend that everyone who is unsure of himself on this material work Exercises 0.1 to 0.9 on pages 25-27 of your textbook. (But do not hand them in.)

Today's lecture will begin with a brief summary of Section 0.1 of your textbook (pages 1-3). We will then begin the main subject of the first portion of the course, regular languages and finite automata, starting with Sections 1.1 and 1.2 of your textbook.

One of the fundamental themes of the course is that a problem is a language. (Actually, only 0/1 problems are languages, but that's a mere technicality.) Additional discussion.

I will end the lecture a few minutes early today, in order to deal with registration problems.

Tuesday, July 1, 2003

Lecture subject: regular languages and finite automata

Derministic versus non-deterministic automata.

Discussion Session 2:00 - 3:00

Wednesday, July 2, 2003

Lecture subject: regular languages and finite automata

Today I will discuss the equivalence of the three definitions of regular language, and I will discuss regular expressions in depth.

Thursday, July 3, 2003

Lecture subject: regular languages and finite automata

Today, I will give the pumping lemma for regular languages, and prove it.

The purpose of the pumping lemma is to prove that certain languages are not regular, for example, any language which allows unlimited nesting of parentheses, such as any modern programming language.

Much later in the course, I will give the pumping lemma for context-free languages. (Same name, different lemma, kind of like "the fundamental theorem," of which there are several.)
I will tell a joke which is actually a true story which relates to the statement of the pumping lemma.
Another method for proving languages not regular is by use of distinguishing strings. (See problems 1.34, 1.35 on page 89.)
If there is extra time, I might begin the subject of context-free languages, context-free grammars, push-down automata, and parsers. Class question: Does Pascal have a context-free grammar? Here is a more detailed discussion.

Monday, July 7, 2003

Homework 1 is due today.

Lecture subject: context-free languages and push-down automata

Derivations and derivation trees.

Ambiguous and unambiguous context-free grammars.

Recursively defined sets.

Tuesday, July 8, 2003

Lecture subject: context-free languages and push-down automata

Push-down Automata. A push-down automaton is also knows as a PDA.

Discussion Session 2:00 - 3:00

Wednesday, July 9, 2003

Lecture subject: context-free languages and push-down automata

Today I will attempt to prove that a language is context-free if and only if it is accepted by some PDA.
It is important to realize that the construction given in the proof does not necessarily give the simplest PDA which accepts a context-free language. The purpose is only to prove that there is at least one.

Thursday, July 10, 2003

Lecture subject: context-free languages and push-down automata

I will complete the proof that, for any context-free language L, there is a PDA that accepts (recognizes) L.

I will also prove the converse, i.e., that given any PDA M, there is a context-free grammar for the language accepted by M. (The proof is given on pages 110-113 of your textbook, and will certainly be the most sophisticated proof so far in this course.)

I will give some interesting context-free grammars, and discuss closure theorems for the class of context-free languages.

I will introduce Chomsky normal form grammars and Greibach normal form grammars. These are special classes of context-free grammars which are equivalent to the class of all context-free grammars.

Friday, July 11, 2003

Discussion Session 8:00 - 9:00

Monday, July 14, 2003

Homework 2 is due today.

Lecture subject: context-free languages and push-down automata

We will finish the proof that any language accepted by a PDA is context-free.

We will introduce the pumping lemma for context-free languages, and use it to prove that some languages are not context-free.

Tuesday, July 15, 2003

Lecture subject: context-free languages and push-down automata

Today we will give a proof of the pumping lemma.

Today we will begin to review material for the mid-term examination on Thursday.

Discussion Session 2:00 - 3:00

Wednesday, July 16, 2003

Lecture subject: context-free languages and push-down automata

Today we will continue reviewing material for the mid-term examination on Thursday.

Thursday, July 17, 2003

Midterm Examination today

Some old exams are now available in pdf format.

Friday, July 18, 2003

Discussion Session 8:00 - 9:00

Monday, July 21, 2003

Homework 3 is due today.

Lecture subject: Turing machines and undecidability

What is a Turing machine?

Challenge for the top students: Work these problems

before the end of the term.

Tuesday, July 22, 2003

Lecture subject: Turing machines and undecidability

The Church-Turing thesis.

Discussion Session 2:00 - 3:00

Wednesday, July 23, 2003

Lecture subject: Turing machines and undecidability

The Church-Turing thesis.

Thursday, July 24, 2003

Lecture subject: Turing machines, undecidability, and time complexity.

Reductions.

Polynomial time languages, otherwise known as P, and non-deterministic polynomial time languages, otherwise known as NP, will be defined. The meaning of the term "NP-complete" will be explained. Don't miss this.

Friday, July 25, 2003

Discussion Session 8:00 - 9:00

I will be in email contact Friday and Saturday from Las Vegas.

Monday, July 28, 2003

Homework 4 is due today.

Lecture subject: Reductions.

Certain special versions of Boolean satisfiability are also NP-complete, and are easier to work with. The two that I will mention are CNF-Sat and 3-CNF-Sat.

3-CNF-Sat polynomially reduces to the independent set problem. We can thus prove that the independent set problem is NP-complete, since it is obviously NP.

.

Tuesday, July 29, 2003

Lecture subject: complexity theory and tractibility

Enumerators.

General grammars.

Discussion Session 2:00 - 3:00

Special Office Hours, Bogdan Warinschi, 4:00 - 5:00

Wednesday, July 30, 2003

Final Examination, Part 1.

Study guide for the final.

Thursday, July 31, 2003

Final Examination, Part 2.

Friday, August 1, 2003

I can email CSE 105 grades now. Please include your student ID in the message.

Eventually, grades will be available at Student Link. Click on Academic History.