THEORY OF COMPUTATION (BCS503)

MODULE – 3

CONTEXT FREE GRAMMARS

A Context Free Grammar is a formal notation for expressing recursive definition of languages. A grammar
consists of one or more variables that represent classes of strings i.e. languages.

Context-free grammars have played a central role in compiler technology since the 1960's; they turned the
implementation of parsers (functions that discover the structure of a program) from a time-consuming, ad-hoc
implementation task into a routine job that can be done in an afternoon.

More recently, the context-free grammar has been used to describe document formats, via the so-called
document-type definition (DTD) that is used in the XML (extensible markup language) community for
information exchange on the Web.

DEFINITION OF CONTEXT FREE GRAMMARS

There are four important components in a grammatical description of a language:

1. There is a finite set of symbols that form the strings of the language being defined. We called this as 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.
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.
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.

The four components just described form a context-free grammar, or just grammar, 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.

Example 1:
Let us consider the language of palindromes. A palindrome is a string that reads the same forward and
backward, such as otto or madamimadam. Put another way, string w is a palindrome if and only if w = wR. 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.

BASIS: ε, 0, and 1 are palindromes.

INDUCTION: If w is a palindrome, so are 0w0 and 1w1. No string is a palindrome of 0's and 1's, unless it
follows from this basis and induction rule. The context free grammar for palindromes:
The context free grammar G = (V, T, P S) where
V = {P}
T = {0, 1}
A={
Pϵ
P0
P1
P  0P0
P  1P1

}
P = Start symbol

Example 2:
Obtain a CFG to generate a language consisting of equal number of a’s and b’s.
The grammar:
S  aB | bA
A  aS | bAA | a
B  bS | aBB | b
The context free grammar G = (V, T, P S) where
V = {S, A, B}
T = {a, b}
P={
S  aB | bA
A  aS | bAA | a
B  bS | aBB | b
}
S = Start symbol

Example 3:
Obtain the grammar to generate the language L = { w | na(w) = nb(w) }
The context free grammar G = (V, T, P S) where
V = {S}
T = {a, b}
P={
Sϵ
S  aSb
S  bSa
S  SS
 }
S = Start symbol

Example 4:
Obtain the grammar to generate the language L = {0m1m2n | m ≥ 1 and n ≥ 0}.
In the language L = {0m1m2n}, if n = 0, the language L contains the „m‟ number of 0‟s ad „m‟ number of 1‟s.
The grammar for this can be of the form
A  01 | 0A1
If „n‟ is greater than zero, the language L should contain „m‟ number of 0‟s followed by „m‟ number of 1‟s
followed by one or more 2‟s.
S  A | S2
A  01 | 0A1

The context free grammar G = (V, T, P S) where

V = {S, A}
T = {0, 1, 2}
P={
S  A | S2
A  01 | 0A1
}
S = Start symbol

Example 5:
Obtain a CFG to generate a string of balanced parentheses.
The context free grammar G = (V, T, P S) where
V = {S}
T = { (, ), [, ], {, } }
P={
S  (S)
S  [S]
S  {S}
S  SS
S ϵ
}
S = Start symbol

Example 6:
Obtain a grammar to generate the language L = {0i1j | i ≠ j, i ≥ 0 and j ≥ 0}.
The context free grammar G = (V, T, P S) where
V = {S, A, B C}
T = {0, 1}
P={
S  0S1 {Generates 0n1n recursively}
SA {To generate more 0‟s than 1‟s}
SB {To generate more 1‟s than 0‟s}
 A 0A | 0 {At least one 0 is generated}
B  1B | 1 {At least one 1 is generated}
}
S = Start symbol

Example 7:
Obtain a grammar to generate the language L = {anbn-3 | n ≥ 3}.
The context free grammar G = (V, T, P S) where
V = {S, A}
T = {a, b}
P={
S  aaaA
A  aAb | ϵ
}
S = Start symbol

Example 8:
Obtain a grammar to generate the language L = {w : |w| mod 3 = 0} on ∑ = {a}.
It is clear from this definition that any string generated should have the length multiples of 3.
L = { ϵ, aaa, aaaaaa, aaaaaaaaa, ……………………}
The context free grammar G = (V, T, P S) where
V = {S}
T = {a}
P={
S  aaaS | ϵ
}
S = Start symbol

Example 9:
Obtain a grammar to generate the language L = {w : |w| mod 3 = 0} on ∑ = {a,b}.
It is clear from this definition that any string generated should have the length multiples of 3.
The context free grammar G = (V, T, P S) where
V = {S, A}
T = {a, b}
P={
S  AAAS | ϵ
Aa|b
}
S = Start symbol

Example 10:
Obtain the grammar to generate the language L = {w | na(w) > nb(w)}.
The following grammar produces equal number of a‟s and b‟s:
 A  aAb
A  bAa
A  AA
Aϵ
Since number of a‟s should be greater than number of b‟s, w should be in a position to generate 1 or more a‟s.
One or more a‟s can be generated using the production:
B  aB | a
Since more number of a‟s can occur in the beginning, at the end or at the middle, we should have a production
to generate as many a‟s as possible in the respective places. Equal number of a‟s and b‟s can be followed by one
or more a‟s which can be achieved by introducing the production.
S  AB

Equal number of a‟s and b‟s can be preceded by one or more a‟s which can be achieved by introducing the
production
S  BA

Equal number of a‟s and b‟s can have one or more a‟s in the middle which can be achieved by introducing the
production.
S  ABA
The context free grammar G = (V, T, P S) where
V = {S, A, B}
T = {a, b}
P={
S  AB | BA| ABA
A  aAb | bAa | AA | ϵ
B  aB | a
}
S = Start symbol

Example 11:
For the regular expression (011+1)*(01)* obtain the context free grammar.
The RE (011+1)*(01)* is of the form A*B* where A can be 011 or 1 and B is 01. The RE A*B* means any
number of A‟s are followed by any number of B‟s. Any number of A‟s can be generated using the productions:
A  011A | 1A | ϵ
Any number of B‟s can be generated using the productions
B  01B | ϵ
Now, the language generated from the regular expression (011+1)*(01)* can be obtained by concatenating A
and B using the production
S  AB
The context free grammar G = (V, T, P S) where
V = {S, A, B}
T = {0, 1}
P={
S  AB
A  011A | 1A | ϵ
 B  01B | ϵ
}
S = Start symbol

DERIVATIONS USING GRAMMAR

There are two ways to infer the language of a grammar.

The more conventional approach is to use the rules from body to head. That is, we 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 whose 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.

A derivation is the process of generating a string from the start symbol of a grammar by repeatedly applying
the production rules of the grammar. This process is used to show how a string belongs to the language defined
by the grammar.

LEFTMOST AND RIGHTMOST DERIVATIONS

 In order to restrict the number of choices while deriving a string, it is often useful to require that at each
step we replace the leftmost variable by one of its production bodies. Such a derivation is called a

Leftmost Derivation, and we indicate that a derivation is leftmost by using the relations ,
for one or many steps, respectively.

 In the derivation process if a right most variable is replaced at every step, then the derivation is said to

be Rightmost Derivation and use the symbols to indicate one or many rightmost
derivation steps respectively.

Example 1:
Obtain the Leftmost and Rightmost derivation for the string a*(a+b00) using the following grammar.
E  I | E+E | E*E | (E)
I  a | b | Ia | Ib | I0 | I1

The leftmost derivation for the string a*(a+b00) is shown below:

E E*E
 I*E
 a*E
 a * (E)
 a * (E+E)
 a * (I+E)
 a * (a+E)
 a * (a+I)
  a * (a+I0)
 a * (a+I00)
 a * (a+b00)

The Rightmost derivation for the string a*(a+b00) is shown below:

E E*E
 E * (E)
 E * (E+E)
 E * (E+I)
 E * (E+I0)
 E * (E+I00)
 E * (E+b00)
 E * (I+b00)
 E * (a+b00)
 I * (a+b00)
 a * (a+b00)

Example 2:
Obtain the leftmost derivation for the string aaabbabbba using the following grammar.
S  aB | Ba
A aS | bAA | a
B  bS | aBB | b

The leftmost derivation:

S  aB (Applying S  aB)
 aaBB (Applying B  aBB)
 aaaBBB (Applying B  aBB)
 aaabBB (Applying B  b)
 aaabbB (Applying B  b)
 aaabbaBB (Applying B  aBB)
 aaabbabB (Applying B  b)
 aaabbabbS (Applying B  bS)
 aaabbabbbA (Applying S  bA)
 aaabbabbba (Applying A  a)

THE LANGUAGE OF A GRAMMAR

If G(V, T, P, S) is a CFG, the language of G, denoted L(G), id the set of terminal strings that have derivations
from the start symbol. That is,

If a language L is the language of some context-free grammar, then L is said to be a context-free language or
CFL.
SENTENTIAL FORMS

Example:
Consider the grammar for expressions, for example, E*(I+E) is a sentential form, since there is a derivation
E  I | E+E | E*E | (E)
I  a | b | Ia | Ib | I0 | I1

E E*E
 E * (E)
 E * (E+E)
 E * (I+E)

However this derivation is neither leftmost nor rightmost, since at the last step, the middle E is replaced.

PARSE TREES
The derivation can be shown in the form of a tree. Such trees are called derivation or parse trees. The leftmost
derivation as well as the right most derivation can be represented using derivation trees. The derivation tree can
be defined as shown below:
Let G = (V, T, P, S), the parse trees for G are trees with the following conditions:
1. Each interior node is labeled by a variable in V.
2. Each leaf is labeled by either a variable, a terminal, or ϵ. However, if the leaf is labeled ϵ, then it must be
the only child of its parent.
3. If an interior node is labeled A, and its children are labeled
X1, X2, X3, ……………….Xk
respectively, from the left, then A  X1X2……….Xk is a production in P. Note that the only time one of
the X‟s can be ϵ is if that is the label of the only child, and A  ϵ is a production of G.

Example:
Construct the parse tree for the following grammar.
E  I | E+E | E*E | (E)
I  a | b | Ia | Ib | I0 | I1
For the string a*(a+b00) obtain parse tree using any derivation.

Derivation:
E E*E
 I*E
 a*E
 a * (E)
 a * (E+E)
 a * (I+E)
  a * (a+E)
 a * (a+I)
 a * (a+I0)
 a * (a+I00)
 a * (a+b00)
Parse Tree:

THE YIELD OF A PARSE TREE

If we look at the leaves of any parse tree and concatenate them from the left, we get a string, called the yield of
the tree, which is always a string that is derived from the root variable. The fact that the yield is derived from
the root will be proved shortly. Of special importance are those parse trees such that:

1. The yield is a terminal string. That is, all leaves are labeled either with a terminal or with ε.
2. The root is labeled by the start symbol.

These are the parse trees whose yields are strings in the language of the underlying grammar.

AMBIGUITY IN GRAMMARS AND LANGUAGES

Ambiguous Grammar:

Let G = (V, T, P, S) be a context free grammar. A grammar G is ambiguous if and only if there exists at least
one string w ϵ T* for which two or more different parse trees exist by applying either the left most derivation or
right most derivation.
Example 1:
Is the following grammar ambiguous?
E  I | E+E | E*E | (E)
I  a | b | Ia | Ib | I0 | I1
Consider the two derivations for the string E + E*E.

The parse trees for the derivations:

Since the two parse trees are different for the same string, the grammar is ambiguous.

Example 2:
Is the following grammar ambiguous?
S  aB | bA
A  aS | bAA | a
B  bS | aBB | b
The string aabbab can be obtained by applying the leftmost derivation as shown below:
The same string aabbab can be obtained again by applying leftmost derivation as shown below:

Note that there are two parse trees for the string aabbab by applying leftmost derivation and so the given
grammar is ambiguous.

Example 3:
Is the following grammar ambiguous?
S  iCtS | iCtSeS | a
Cb
The string ibtibtaea can be obtained by applying the leftmost derivation as shown below:

The string ibtibtaea can be obtained again by applying the leftmost derivation but using different sets of
productions as shown below:
Since there are two different parse trees for the string „ibtibtaea‟ by applying leftmost derivation the given
grammar is ambiguous.

REMOVING AMBIGUITY FROM GRAMMARS

There are two causes of ambiguity in the grammar. They are:

(1) The precedence of operators is not respected.

(2) A sequence of identical operators can group either from the left of from the right.

The solution to the problem of enforcing precedence is to introduce several different variables, each of which
represents those expressions that share a level of “binding strength” specially:

(1) A factor is an expression that cannot be broken apart by any adjacent operator, either a * or a +. The
only factors in our expression language are:
(a) Identifiers. It is not possible to separate the letters of an identifier by attaching an operator.
(b) Any parenthesized expression, no matter what appears inside the parentheses. It is the purpose
of parentheses to prevent what is inside from becoming the operand of any operator outside the
parentheses.
(2) A term is an expression that cannot be broken by the + operator. In our example, where + and * are the
only operators, a term is a product of one or more factors. For instance, the term a * b can be "broken" if
we use left associativity and place a1+ to its left. That is, a1 * a * b is grouped (a1 * a) * b, which breaks
apart the a * b. However, placing an additive term, such as a1+, to its left or +a1 to its right cannot break
a * b. The proper grouping of a1 + a * b is a1 + (a * b), and the proper grouping of a * b + a1 is (a * b) +
a1.
(3) An expression will henceforth refer to any possible expression, including those that can be broken by
either an adjacent * or an adjacent +. Thus, an expression for our example is a sum of one or more terms.

LEFTMOST DERIVATIONS AS A WAY TO EXPRESS AMBIGUITY

While derivations are not necessarily unique, even if the grammar is unambiguous, it turns out that, in an
unambiguous grammar, leftmost derivations will be unique, and rightmost derivations will be unique. We shall
consider leftmost derivations only, and state the result for rightmost derivations.

Example: As an example, notice the two parse trees of Figure that each yield E+E∗E. If we construct leftmost
derivations from them we get the following leftmost derivations from trees (a) and (b), respectively:
Note that these two leftmost derivations differ. This example does not prove the theorem, but demonstrates how
the differences in the trees force different steps to be taken in the leftmost derivation.

INHERENT AMBIGUITY

A context-free language L is said to be inherently ambiguous if all its grammars are ambiguous. If even one
grammar for L is unambiguous, then L is an unambiguous language.
 PUSHDOWN AUTOMATA

The context-free languages have a type of automaton that defines them. This automaton, called a "pushdown
automaton," is an extension of the nondeterministic finite automaton with ϵ-transitions, which is one of the
ways to define the regular languages. The pushdown automaton is essentially an ϵ-NFA with the addition of a
stack. The stack can be read, pushed, and popped only at the top, just like the "stack" data structure.

Figure: A pushdown automaton is essentially a finite automaton with stack data structure

We can view the pushdown automaton informally as the device suggested in Fig. A “finite-state control” reads
inputs, one symbol at a time. The pushdown automaton is allowed to observe the symbol at the top of the stack
and to base its transition on its current state, the input symbol, and the symbol at the top of stack. Alternatively,
it may make a “spontaneous” transition, using ϵ as its input instead of an input symbol. In one transition, the
pushdown automaton:

1. Consumes from the input the “symbol” that it uses in the transition. If e is used for the input, then no
input symbol is consumed.
2. Goes to a new state, which may or may not be the same as the previous state.
3. Replaces the symbol at the top of the stack by any string. The string could be ϵ, which corresponds to a
pop of the stack. It could be the same symbol that appeared at the top of the stack previously; i.e., no
change to the stack is made. It could also replace the top stack symbol by one other symbol, which in
effect changes the top of the stack but does not push or pop it. Finally, the top stack symbol could be
replaced by two or more symbols, which has the effect of (possibly) changing the top stack symbol, and
then pushing one or more new symbols onto the stack.

The Formal Definition of Pushdown Automata

The formal definition of Pushdown Automaton (PDA) involves seven components:

P = (Q, ∑, Γ, 𝞭, q0, Z0, F)

The components have the following meanings:

Q: A finite set of states, like the states of a finite automaton.
Σ: A finite set of input symbols, also analogous to the corresponding component of a finite automaton.
Γ: A finite stack alphabet. This component, which has no finite-automaton analog, is the set of symbols that
we are allowed to push onto the stack.
δ: The transition function. As for a finite automaton, δ governs the behavior of the automaton. Formally, δ
takes as argument a triple δ(q,a,X), where:
1. q is a state in Q.
2. a is either an input symbol in Σ or a = ε, the empty string, which is assumed not to be an input symbol.
3. X is a stack symbol, that is, a member of Γ.
The output of δ is a finite set of pairs (p,γ), where p is the new state, and γ is the string of stack symbols that
replaces X at the top of the stack. For instance, if γ = ε, then the stack is popped; if γ = X, then the stack is
unchanged; and if γ = YZ, then X is replaced by Z, and Y is pushed onto the stack.
q0: The start state. The PDA is in this state before making any transitions.
Z0: The start symbol. Initially, the PDA‟s stack consists of one instance of this symbol, and nothing else.
F: The set of accepting states, or final states.

Example 1:

Obtain a PDA to accept the language L = {anbn | n ≥ 1} by a final state.

Note: The machine should accept n number of a's followed by n number of b's.

General Procedure:

Since n number of a's should be followed by n number of b's, let us push all the symbols onto the stack as long
as the scanned input symbol is a. Once we encounter b's, we should see that for each b in the input, there should
be a corresponding a on the stack. When the input pointer reaches the end of the string, the stack should be
empty. If the stack is empty, it indicates that the string scanned has n number of a's followed by n number of b's.

Step 1:

Let q0 be the start state and Z0 be the initial symbol on the stack. As long as the next input symbol to be
scanned is a, irrespective of what is there on the stack, keep pushing all the symbols onto the stack and remain
in q0. The transitions defined for this can be of the form:

δ(q0, a, Z0) = (q0, aZ0)

δ(q0, a, a) = (q0, aa)

Step 2:

In state q0, if the next input symbol to be scanned is b and if the top of the stack is a, change the state to q1 and
delete one b from the stack. The transition for this can be of the form:

δ(q0, b, a) = (q1, ϵ)

Step 3:

Once the machine is in state q1, the rest of the symbols to be scanned will be only b's, and for each b there
should be a corresponding symbol a on the stack. So, as the scanned input symbol is b and if there is a matching
a on the stack, remain in q1and delete the corresponding a from the stack. The transitions defined for this can be
of the form:

δ(q1, b, a) = (q1, ϵ)
Step 4:

In state q1, if the next input symbol to be scanned is ϵ and if the top of the stack is Z0, (it means that for each b
in the input there exists a corresponding a on the stack), change the state to q2, which is an accepting state. The
transition defined for this can be of the form:

δ(q1, ϵ, Z0) = (q2, Z0)

So, the PDA to accept the language:

L = {anbn | n ≥ 1}
along with the transition diagram is given by:
P = (Q, Σ, Γ, δ, q0, Z0, F)
Where:
Q = {q0, q1, q2}
Σ = {a,b}
Γ = {a, Z0}
δ is as shown below:
δ(q0, a, Z0) = (q0, aZ0)
δ(q0, a, a) = (q0, aa)
δ(q0, b, a) = (q1, ϵ)
δ(q1, b, a) = (q1, ϵ)
δ(q1, ϵ, Z0) = (q2, Z0)
q0 ∈ Q is the start state of the machine.
Z0 ∈ Γ is the initial symbol on the stack.
F={q2} is the final state.
The transition diagram for the PDA:

Instantaneous Descriptions of a PDA

To Accept the String:

The sequence of moves made by the PDA for the string aaabbb is shown below.
Initial ID
(q0,aaabbb,Z0) ⊢(q0,aabbb,aZ0)
⊢(q0,abbb,aaZ0)
⊢(q0,bbb,aaaZ0)
⊢(q1,bb,aaZ0)
⊢(q1,b,aZ0)
⊢(q1,ϵ,Z0)
⊢(q2,ϵ,Z0)
(Final Configuration)
Since q2 is the final state and input string is ϵ\epsilonϵ in the final configuration, the string aaabbb is accepted
by the PDA.
EQUIVALENCE OF PDA’s and CFG’s

FROM GRAMMARS TO PUSHDOWN AUTOMATA

Given a CFG G, we construct a PDA that simulates the leftmost derivations of G. Any left-sentential form that
is not a terminal string can be written as xAα, where A is the leftmost variable, x is whatever terminals appear
to its left, and α is the string of terminals and variables that appear to the right of A.

We call Aα the tail of this left-sentential form. If a left-sentential form consists of terminals only, then its tail is
ϵ.

The idea behind the construction of a PDA from a grammar is to have the PDA simulate the sequence of left-
sentential forms that the grammar uses to generate a given terminal string w. The tail of each sentential form
xAα appears on the stack, with A at the top. At that time, x will be "represented" by our having consumed x
from the input, leaving whatever of w follows its prefix x. That is, if w = xy, then y will remain on the input.

Suppose the PDA is in an ID (q, y, Aα), representing left-sentential form xAα. It guesses the production to use
to expand A, say A → β. The move of the PDA is to replace A on the top of the stack by β, entering ID (q, y,
βα). Note that there is only one state, q, for this PDA.