Topics
After an introduction to the contents of this course, we begin our
investigation of the topics covered in the part of the course dealing
with Syntax. Our main topics of interest over the first few
lectures will be strings and languages. We shall
then introduce the formalism of finite automata, and begin to
study some of its properties and its computational power.
Finite automata are our first example of abstract
machine. Abstract machines are mathematical models of
computational devices, and we shall characterize their expressive
power in terms of the collection of languages that they recognize. The
languages recognized by finite automata are called
regular.
Time and Location
Monday, 6 September 2004 at 10:15 in A4-106.
Reading Material
Sections 0.2 and 1.1 of Introduction to
the Theory of Computation by Michael Sipser.
Slides for the lecture (PDF).
Exercises
In general, I shall give you more exercises than you might conceivably
be able to solve during one exercise class. The exercises marked with
a star are those that I consider more important for your
understanding. All the exercises will be "doable", and working them
out will greatly increase your understanding of the topics covered in
the course. The best advice I can give you is to work them all out by
yourselves, and to make sure you understand the solutions if the other
members of your group (or me) gave you the solutions on a golden
plate. Above all, don't give up if you cannot find the key to the
solutions right away. Problem solving is often a matter of mental
stamina as much as creativity.
Whenever you construct an automaton, try to argue that it does the job
that it was meant to do. You may not need (some of) the material
covered in this course in your future careers, but having an
analytical and critical attitude will always help you.
- Exercises 1.1(*), 1.2, 1.4(a)(*), 1.4(d)(*) and 1.4(j)(*) on pages
83-84 of
Introduction to the Theory of Computation by Michael Sipser. (You are
encouraged to try to solve more of the sub-items in exercise 1.4, if
you have time.)
- Let Sigma be an alphabet. What language do we obtain by
concatenating Sigma* with itself? What if we do the same with Sigma+?
Argue for your answers.
- (*) Argue that if L is regular, then so is its complement.
- Argue that if L and M are regular, then so it the intersection of
L and M.