Topics
In the previous lecture, we introduced our first
example of abstract machine, viz. the Deterministic Finite
Automata (DFAs), and the class of languages they recognize,
viz. the regular languages. Using constructions on DFAs, we
shall now argue that the class of regular languages is closed under
the set-theoretic operations of union, intersection and
complementation. This means that if A and B are two
regular languages, then so are their union, intersection and
complements. The same holds true for the language-theoretic operations
of concatenation and Kleene star, but this is not so easy to show
using DFAs. Moreover, sometimes it is quite hard to come up with DFAs
recognizing a given regular language. In both these cases, one would
often like to make use of nondeterminism in describing the
behaviour of automata.
In this lecture we shall introduce a nondeterministic version of
finite automata, the Nondeterministic Finite Automata
(NFAs). Their main feature is that, unlike in a DFA, the next state of
a computation, if any, is not uniquely determined by the current state
and the next input symbol. Moreover, NFAs can jump from state to
another without reading the next input symbol.
Despite these, apparently magic features, NFAs are no more
powerful than DFAs. We shall see how, given an NFA, we can build a DFA
which recognizes the same language. The algorithm used for this
purpose is called, for good reasons, the subset
construction. It finds numerous applications in compiler
construction, and is used by e.g. the LEX tool for the automatic
generation of lexical analyzers (for use in compiler
construction).
However, since it is usually not possible to "have the cake and eat
it", the conversion from NFAs to DFAs has a price. In the worst case,
the DFA delivered by the subset construction is going to be
exponentially bigger than the input NFA.
Time and Location
Friday, 10 September, 2004 at 10:15 in A4-106.
Reading Material
Section 1.2 of Introduction to
the Theory of Computation by Michael Sipser.
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.