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 have also shown that
the class of regular languages is closed under the set-theoretic
operations of union, intersection and complementation. 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.
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
Monday, 11 February, 2002 at 10:15 in B2-104.
Reading Material
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.