MODULE 3

170 CHAPTER 5. CONTEXT-FREE GRAMMARS AND LANGUAGES

the process of "derivation," whereby it is determined which strings are in the

language of the grammar.

5.1.1 An Informal Example

Let us consider the language of palindromes. A palindrome is a string that reads
the same forward and backward, such as otto or madamimadam ("Madam, I'm
Adam," allegedly the first thing Eve heard in the Garden of Eden). Put another
way, string w is a palindrome if and only if w w". To make things simple,
=

we shall consider describing only the palindromes with alphabet {0, 1}. This
language includes strings like 0110, 11011, and e, but not 011 or 0101.
It is easy to verify that the language Lpal of palindromes of 0's and 1's is
not a regular language. To do so, we use the pumping lemma. If Lpat is a
regular language, let n be the associated constant, and consider the palindrome
w = 0n10n. If Lpal is regular, then we can break w into w xyz, such that =

y consists of one or more 0's from the first group. Thus, xz, which would also
have to be in Lpal if Lpat were regular, would have fewer O's to the left of the
lone 1 than there are to the right of the 1. Therefore xz cannot be a palindrome.
We have now contradicted the assumption that Lpat is a regular language.
There is a natural, recursive definition of when a string of O's and 1's is in
Lpal. It starts with a basis saying that a few obvious strings are in Lpal, and
then exploits the idea that if a string is a palindrome, it must begin and end
with the same symbol. Further, when the first and last symbols are removed,
the resulting string must also be a palindrome. That is:
BASIS: e, 0, and 1 are palindromes.
INDUCTION: If w is a palindrome, so are Ow0 and 1w1. No string is a palin-
drome of 0's and 1's, unless it follows from this basis and induction rule.

A context-free grammar is a formal notation for expressing such recursive

definitions of languages. A grammar consists of one or more variables that
represent classes of strings, i.e., languages. In this example we have need for
only one P, which represents the set of palindromes; that is the class of
variable
strings forming the language Lpat. There are rules that say how the strings in
each class are constructed. The construction can use symbols of the alphabet,
strings that are already known to be in one of the classes, or both.

Example 5.1: The rules that define the palindromes, expressed in the context-
free grammar notation, are shown in Fig. 5.1. We shall see in Section 5.1.2 what
the rules mean.

The first three rules form the basis. They tell us that the class of palindromes
includes the strings e, 0, and 1. None of the right sides of these rules (the
portions following the arrows) contains a variable, which is why they form a
basis for the definition.
The last two rules form the inductive part of the definition. For instance,
rule 4 says that if we take any string w from the class P, then Owo is also in
class P. Rule 5 likewise tells us that lwl is also in P.
5.1. СОNTEXT-FREE GRAMMARS 171

1. P ← ε

2. P0
3. P 1
4. P → OPO
5. P→ 1P1

Figure 5.1: A context-free grammar for palindromes

5.1.2 Definition of Context-Free Grammars

There are four important components in a grammatical description of a lan-

guage:

1. There is a finite set of symbols that form the strings of the language being
defined. This set was {0,1} in the palindrome example we just saw. We
call this alphabet the terminals, or terminal symbols.

2. There is a finite set of variables, also called sometimes nonterminals or

syntactic categories. Each variable represents a language; i.e., a set of

strings. In our example above, there was only one variable, P, which we
used to represent the class of palindromes over alphabet {0,1}.

3. One of the variables represents the language being defined; it is called the
start symbol. Other variables represent auxiliary classes of strings that
are used to help define the language of the start symbol. In our example,
P, the only variable, is the start symbol.

4. There is a finite set of productions or rules that represent the recursive

definition of a language. Each production consists of:

(a) A variable that is being (partially) defined by the production. This

variable is often called the head of the production.

(b) The production symbol →.

(c) A string of zero or more terminals and variables. This string, called
the body of the production, represents one way to form strings in the
language of the variable of the head. In so doing, we leave terminals
unchanged and substitute for each variable of the body any string
that is known to be in the language of that variable.

We saw an example of productions in Fig. 5.1.

The four components just described form a context-free grammar, or just gram-
mar, or CFG. We shall represent a CFG G by its four components, that is,
G = (V,T, P,S), where V is the set of variables, T the terminals, P the set of
productions, and S the start symbol.
172 CHAPTER 5. CONTEXT-FREE GRAMMARS AND LANGUAGES

Example 5.2: The grammar Gpat for the palindromes is represented by

Gpal = ({P], {0, 1},A, P)

where A represents the set of five productions that we saw in Fig. 5.1.

Example 5.3: Let us explore a more complex CFG that represents (a simplific-
ation of) expressions in a typical programming language. First, we shall limit
ourselves to the opcrators + and *, representing addition and multiplication.
We shall allow arguments to be identifiers, but instead of allowing the full set of
typical identifiers (letters followed by zero or more letters and digits), we shall
allow only the letters a and b and the digits 0 and 1. Every identifier must
begin with a or b, which may be followed by any string in {a, b, 0, 1)*.
We need two variables in this grammar. One, which we call E, represents
expressions. It is the start symbol and represents the language of expressions
we are defining. The other variable, I, represents identifiers. Its language is
actually regular; it is the language of the regular expression

(a+ b)(a+b+0+1)*

However, we shall not use regular expressions directly in gramnars. Rather,

we use a set of productions that say essentially the same thing as this regular
expression.

1. E→ I
2. E→E+E
3. E EE
4. E (E)

5. I→ a

6. I b
7. I Ia
8. I Ib
9. I 10
10. I → 11

Figure 5.2: A context-free grammar for simple expressions

The grammar for expressions is stated formally as G = ({E,I},T, P, EЕ),

where T is the set of symbols {+, *, (,), a, b, 0, 1) and P is the set of productions
shown in Fig. 5.2. We interpret the productions as follows.
Rule (1) is the basis rule for expressions. It says that an expression can
be asingle identifier. Rules (2) through (4) describe the inductive case for
expressions. Rule (2) says that an expression can be two expressions connected
by a plus sign; rule (3) says the same with a multiplication sign. Rule (4) says
5.1. СОNTEXT-FREE GRAMMARS 173

Compact Notation for Productions

It is convenient to think of a production as "belonging" to the variable

of its head. We shall often use remarks like "the productions for A" or
"A-productions" to refer productions whose head is variable A. We
to the

may write the productions for a grammar by listing each variable once, and
then listing all the bodies of the productions for that variable, separated by
vertical bars. That is, the productions A a, A→02,..., A→an can
be replaced by the notation A→a1/02an. For instance, the grammar
for palindromes from Fig. 5.1 can be written as Pє0|1|OP0 | 1P1.

that if we take any expression and put matching parentheses around it, the
result is also an expression.
Rules (5) through (10) describe identifiers I. The basis is rules (5) and (6);
they say that a and b are identifiers. The remaining four rules are the inductive
case. They say that if we have any identifier, we can follow it by a, b, 0, or 1,
and the result will be another identifier.

5.1.3 Derivations Using a Grammar

We apply the productions of a CFG to infer that certain strings are in the
language of a certain variable. There are two approaches
inference. The
to this
more conventional approach is to use the rules from body
head. That is, we to
take strings known to be in the language of each of the variables of the body,
concatenate them, in the proper order, with any terminals appearing in the
body, and infer that the resulting string is in the language of the variable in
the head. We shall refer to this procedure as recursive inference.
There is another approach to defining the language of a grammar, in which
we use the productions from head to body. We expand the start symbol using

one of its productions (i.e., using a production whosc head is the start symbol).

We further expand the resulting string by replacing one of the variables by the
body of one of its productions, and so on, until we derive a string consisting
entirely of terminals. The language of the grammar is all strings of terminals
that we can obtain in this way. This use of grammars is called derivation.
We shall begin with an example of the first approach recursive inference.
-

However, it is often more natural to think of grammars as used in derivations,

and we shall next develop the notation for describing these derivations.

Example 5.4: Let us consider some of the inferences we can make using the
grammar for expressions in Fig. 5.2. Figure 5.3 sumnarizes these inferences.
For example, line (i) says that we can infer string a is in the language for
I by using production 5. Lines (ii) through (iv) say we can infer that 200