Topics
Regular expressions are a notation for describing regular languages
which appear over and over again in Computer Science. Variants on
regular expressions are, for instance, used in text editors like Emacs
and in UNIX.
In our previous lecture, we have seen how adding nondeterminism to the
model of finite automata did not yield a more powerful model of
computation. In particular, we saw that there is an algorithm that
allows us to convert any nondeterministic automaton into an equivalent
deterministic one.
In this lecture we shall see that regular expressions are also
equivalent to finite automata, and that there are algorithmic
conversions between these two formalisms. To this end, we shall first
show how to convert a regular expression R into an NFA that
recognizes the language denoted by R. Next, we shall show
how, given a DFA M, we can build a regular expression
describing the language L(M). As a tool in this conversion,
we shall employ Generalized NFAs, which are just NFAs whose
transitions may be labelled by arbitrary regular expressions. Both
these conversions are achieved by means of algorithms, which you may
find implemented in the DAT2
project developed last year by some of your colleagues.
Time and Location
Friday, 15 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.
- Complete any starred exercise you may have left over from the previous
exercise class.
- Exercises 1.14(a)(*), 1.14(c), 1.15(a)(*), 1.15(c) and 1.16(a) on page
86 of
Introduction to the Theory of Computation by Michael Sipser.
- (*) Is a finite language regular? Argue for your answer.
- (*) You are given a regular expression R. How would you find a
regular expression that denotes the complement of L(R)? Argue for
your answer.
- Let L be a language. Let rev(L) be the language consisting of all
the reverses of the strings in L.
- Define, for every regular expression
R, a regular expression rev(R) denoting the language rev(L(R)). [Hint:
Use induction on the structure of R.]
- Use your solution to the above question to argue that
regular languages are closed under the rev(.) operation. Can you
establish this fact using a construction on automata?
- [Extra exercise] Let L be a language. Let pref(L) be the
language consisting of all the prefixes of the strings in L.
- Define, for every regular expression
R, a regular expression pref(R) denoting the language pref(L(R)). [Hint:
Use induction on the structure of R.]
- Use your solution to the above question to argue that
regular languages are closed under the pref(.) operation. Can you
establish this fact using a construction on automata?