Topics
In lecture 4 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 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
Thursday, 20 February 2003 at 10:15 in A4-106.
Reading Material
Exercises
- 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(*) and 2.16 on page 121 of Introduction to
the Theory of Computation by Michael Sipser.