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
Thursday, 25 November
2004 at 9:00 in room 303.
Reading Material
Exercises
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.
- Complete any starred exercise you may have left over from the previous
exercise class.
- Exercises 1.9(*), 1.10(b)(*), 1.11, 1.12(*) on pages
84-85 of
Introduction to the Theory of Computation by Michael Sipser.
- Exercises 1.4(b) and 1.6(a) on page
84 of
Introduction to the Theory of Computation by Michael Sipser.
- How would you complement an NFA? What is the complexity of your
construction?
- Extra Exercise for the Keenest: Prove that the construction
used in the proof of Theorem 1.12 in Introduction to
the Theory of Computation by Michael Sipser is
correct.
- [Programming Exercise] Write a simulator for
nondeterministic finite automata in your favourite
programming language. The program should allow the user to input an
automaton to be simulated, and the input on which to carry out the
simulation. It should also be possible to save automata, and load
already saved ones.