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 will meet again in your compiler 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 the 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
Tuesday, 30 November
2004 at 9:00 in room 303.
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.
- [Programming Exercise] Write a simulator for context-free
grammars in your favourite programming language. The program should
allow the user to input a grammar to be simulated, and the string to
be generated. The user should then be allowed to apply productions in
the grammar in an attempt to generate the string. It should also be
possible to save grammars, and load already saved ones.