Context-free Languages and Grammars
Prof. (Dr.) K.R. Chowdhary
Former Professor & Head, Department of Computer Sc. & Engineering
MBM Engineering College, Jodhpur

kr chowdhary

TOC

1/ 10

K.R. Chowdhary

Theory of Computation
Automata, Formal Languages, Computation and Complexity
Focuses on pedagogy in its writing, that represents a refreshing
approach
Ensures comprehensive and enjoyable learning
Undergone a rigorous classroom testing

©2025

Get 20% off with this code: SPRAUT
Available on Springer Nature Link
Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books
& eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and
titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks,
encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing
address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply.
Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers,
book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us.
Promotions do not work in combination with other discounts or gift cards.

link.springer.com/book/
9789819762347

Introduction
CFLs and CFGs are fundamentals to computer science, because they
help in describing the structure of programming languages. All the
HLL are in the category of CFL. Though natural languages (NLs)
are not CFL, but their analysis is possible only when they are treated
as CFLs.
Context-free languages(CFL) are more powerful than regular
languages. The context-free grammars (CFG) are generators of CFL.
Regular languages are subset of CFL.
CFG is finite specification of rules to generate infinite context-free
language.
To generate all the strings of regex a∗ (b ∗ + c ∗ )b, we follow the
steps:
1
2
3

write character a zero or more times
arbitrarily choose b or c and write it arbitrary times
write b.

kr chowdhary

TOC

2/ 10

Generating Language strings
Let L = L (a∗ (b ∗ + c ∗ )b) is
language corresponding to
regex. We can generate all the
strings by substitution rules:

using production rules.
S ⇒ AMb ;by rule 1
⇒ aAMb ;by rule 2
⇒ aaAMb ;by rule 2

1. S → AMb, 6. B → ε

⇒ aaMb ;by rule 3
⇒ aaCb ;by rule 5

2. A → aA, 7. B → bB

⇒ aacCb ;by rule 8
⇒ aaccCb ;by rule 8

3. A → ε, 8. C → cC

⇒ aaccb ;by rule 9

4. M → B, 9. C → ε

Therefore, aaccb ∈ L. Symbol “→”
stand for “can be substituted by”,
and “⇒” stand for “derives.”
Strings like aacCb or AMb, during
the derivation are called sentential
form.

5. M → C
Consider generating w = aaccb
kr chowdhary

TOC

3/ 10

Generating language strings
symbols, appearing in the
process of derivation

Let us try to generate the strings of
language L = {an b n |n ≥ 0}. The
rules this time are: S → aSb,
S → ε. Consider deriving
w = aaabbb.

Σ is set of terminal symbols
(appearing in the final
generated sentence),
V ∩Σ = φ,

S ⇒ aSb

S is start symbol,

⇒ aaSbb

P is set of production/
substitution rules of the form
A → α, where A ∈ V and
α ∈ (V ∪ Σ)∗ .

⇒ aaaSbbb
⇒ aaabbb
Therefore, S ⇒∗ aaabbb. The
generator of these languages, is
CFG G = (V , Σ, S, P), where:

Symbols in upper case in the
beginning of English alphabets
are variables (non-terminal
symbols), i.e. A, B, C , D, E .

V is finite set of variables

kr chowdhary

TOC

4/ 10

Derivations
Definition
Context-free grammar: A CFG is regular grammar if productions are
like: A → a, A → aB, A → ε, where, a ∈ Σ, and A, B ∈ V . For the regular
expression a∗ (b ∗ + c ∗ )b, a CFG was used in the previous slides to
generate the regular language.
Definition
Derivation: A derivation α1 ⇒G α2 ⇒G · · · ⇒G αn , can be written in
short as α1 ⇒∗G αn . In a derivation: β Aγ ⇒G β αγ, the symbol A can be
substituted by α, if there is production like A → α, irrespective of
presence of substrings β and γ around the non-terminal symbol A.
Languages having this property are called context-free. The substrings β
and γ are called context of variable A. Relation ⇒ is reflexive,
anti-symmetric, and transitive (a partial ordering) relation.
Definition
Language acceptability: L = L(G ) = {w ∈ Σ∗ |S ⇒∗G w }. Two
grammars are equal if they generate the same language.
kr chowdhary

TOC

5/ 10

Derivations
Example
Given grammar G = {V , Σ, S, P}, Σ = {+, −, ∗, /, (, ), id}, V = {E },
S = E , and P = {E → E + E | E − E | E /E | E ∗ E | (E ) | id}, find out the
derivation and derivation tree for id ∗ (id + id)/id − id.
Solution
The generating process:
E ⇒ E −E ⇒ E ∗E −E
⇒ id ∗ E /E − E ⇒ id ∗ (E )/E − E
⇒ id ∗ (E + E )/E − E ⇒ id∗
(id + E )/E − E
⇒ id ∗ (id + id)/E − E
⇒ id ∗ (id + id)/id − E
⇒ id ∗ (id + id)/id − id
kr chowdhary

TOC

6/ 10

Derivations and ambiguity
Compilers derive a given
expression, if it succeed, the
expression is syntactically
correct, else not.

grammar.
If G has maximum n number
of derivation trees, then its
degree of ambiguity n.

In a derivation, e.g.,
S ⇒ ABC , we may start by
first replacing left side
variables (leftmost derivation)
or the right side variable first
(rightmost derivation). In
both, the end result is the
same.

It is recursively unsolvable, to
find out if an arbitrary
grammar is ambiguous. Thus,
there does not exist an
algorithm to find out if a given
grammar is ambiguous.
A grammar is un-ambiguous if
every w ∈ L(G ) has a unique
parse-tree. A grammar is
called reduced, if every
non-terminal appears in some
derivation.

If a language L = L(G ) can be
derived using two or more
different derivation trees, the
grammar G is ambiguous

kr chowdhary

TOC

7/ 10

Ambiguity

Show that grammar for id + id ∗ id is ambiguous.

The two derivation trees have different semantics: first calculates
id + (id ∗ id) while the second does (id + id) ∗ id, hence the grammar
is ambiguous.

kr chowdhary

TOC

8/ 10

Removing ambiguity
The general case of detection of ambiguity in a grammar is unsolvable.
However, if it is found that the grammar is ambiguous, it can be made
unambiguous by adding few more non-terminals in the grammar.
Example
Given Σ = {(, ), +, ∗, id}, P = {E → E + E |E ∗ E |(E )|id}, which is an
ambiguous grammar, find out its equivalent unambiguous grammar.
Solution
Let V = {E , T , F }, and
P = {E → E + T , E → T , T → T ∗ F , T → F , F → (E ), F → id}. Note
that, you can derive a string in one way only.
E ⇒ E +T
⇒ T +T
⇒ F + T ⇒ id + T
⇒ id + T ∗ F ⇒ id + F ∗ F
⇒ id + id ∗ F ⇒ id + id ∗ id
kr chowdhary

TOC

9/ 10

Bibliography

Chowdhary, K.R. (2025). Regular Languages. In: Theory of
Computation. Springer, Singapore.
https://doi.org/10.1007/978-981-97-6234-7_6

kr chowdhary

TOC

10/ 10