Topics
In our previous lecture we saw that certain languages are not
regular. Hence, if we wish to describe a richer class of languages, we
need a model that is more expressive than regular expressions. In the
next three lectures, we shall look at one such model, viz. the
context-free grammars and the automata that recognize the context-free
languages.
Context-free grammars, which you have already met in the SPO course,
are very important for the description of large parts of the syntax of
programming languages. In particular, to this end, it is important
that they are not ambiguous, a concept that will be
introduced in this lecture.
Context-free grammars were introduced by Noam
Chomsky (who is a professor at Massachusetts Institute of
Technology), who also proposed one of the notions of normal form for
such grammars. This kind of normal form - usually referred to as
Chomsky Normal Form - will also be presented in this lecture. Most
importantly, we shall see that there is an algorithm for converting
every context-free grammar to an equivalent one in Chomsky Normal
Form.
Time and Location
Friday, 1 March 2002 at 10:15 in A4-106.
Reading Material
Exercises
- Complete any starred exercise you may have left over from the previous
exercise class.
- Exercises 2.1(b)(*), 2.3 , 2.4(f), 2.6(a), 2.9(*) and 2.14 on
pages 119-121 of Introduction to
the Theory of Computation by Michael Sipser.
Note: Exercise 2.3 is meant to help you revise your understanding of context-free grammars, and how they can be used to generate strings. Select the subquestions you think you need. You may safely skip this exercise if you think that you have fully understood what a grammar is, and how grammars generate strings.
- Problems 2.15(*), 2.16 on page 121 of Introduction to
the Theory of Computation by Michael Sipser.