CSE1008 - Theory of Computation

WIN SEM (2024-25)

Dr. K. Srinivasa Reddy

Professor
SCOPE, VIT-AP University
Module No. 3 RE & Context Free Grammar (CFG) 9 Hours
Closure properties of Regular Languages - Decision properties of Regular
Languages - Context-Free Grammar (CFG) – Derivation Trees – Ambiguity in
Grammars and Languages.
Introduction
<sentence>  <noun_phrase> <predicate>
<noun_phrase>  <article> <noun>
<predicate>  <verb>
<article>  a Is it possible to derive the sentence “The boy sleeps”?
<article>  the
<noun>  boy <sentence>  <noun_phrase> <predicate>
<noun>  dog  <article> <noun> <predicate>
<verb>  runs  the <noun> <predicate>
<verb>  sleeps  the boy <predicate>
 the boy <verb>
 the boy sleeps

Language L = { “a boy runs”, “a boy sleeps”, “the boy runs”, “the boy sleeps”,
“a dog runs”, “a dog sleeps”, “the dog runs”, “the dog sleeps” }
Introduction
Introduction
Languages and Machines | Chomsky Hierarchy
Introduction
• Theorems about formal languages can be dealt with as either grammars or
automata.
• Chomsky hierarchy shows the equivalence between the different kinds of
languages and automata.
 Generative Approach Recognition approach
A language is the set of strings generated by a A language is the set of strings accepted by an
grammar automaton.
Generation process Recognition process
• Focuses on how strings in a language are • Determines whether a given string belongs to a
generated using grammars or production language by using automata
rules.
• Humans find grammars appealing because • Machines find automata appealing because they
they provide structured, compact, and finite are formal, compact, and efficient computational
descriptions for languages that may be models that can be directly implemented in
infinite in size. hardware or software.
• They allows to define complex linguistic • Automata, such as finite state machines (FSMs),
structures using a finite set of rules, making are widely used in compilers, network protocols,
them both informative and expressive. and embedded systems due to their predictable and
• If grammars are implemented naively, they low-overhead execution.
can be highly inefficient • Automata can be difficult for humans to
understand, especially as they scale in complexity.
• "How can we generate valid strings?" "Does a given string belong to the language?"
Introduction
Let L = Palindromes over Σ = {0,1}*
• A palindrome is a string that reads the same forward and backward.
• Example: 010, 1001, 11011, etc…
Basis: ɛ, 0 and 1 are palindromes
Induction: If w is a palindrome, so are 0w0 and 1w1.
• No string is palindrome of 0 and 1, unless it follows from this basis and
inductive rule.
A Context Free Grammar is a formal notation for expressing such recursive
definitions of languages
Introduction
• A variable P which represents the set of palindromes; i.e., the class of strings
forming the language L
Rules:
P→ɛ
P→0 Basis
P→1
P→0P0 Inductive
P→1P1
Introduction
• Context-free languages are a larger class of languages that encompasses all
regular languages and many others.
• A context-free grammar basically consists of a finite set of grammar rules.
• Two kinds of symbols are used to define grammar rules:
• The Terminals
• The Non terminals or Variables
• Production rule is of the form A  α, where A is a single nonterminal, and the
right-hand side α is a string of zero or more terminal and/or nonterminal
symbols.
Definition:
Each production rule consists of:
1. A variable that is being (partially) defined by the production. This variable is
often called the head of the production.
2. The production symbol 
3. 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 doing so, terminals are unchanged and substitute for each variable of the body
any string that is known to be in the language of that variable.
Definition:
A Context-Free Grammar (CFG) consisting of a finite set of grammar rules is
a quadruple (V, T, P, S) or (V, ∑, P, S) where
• V is a finite set of non-terminal symbols / variables.
(Each variable represents a set of strings)
• T is a finite set of terminals where V ∩ T = NULL.
(i.e., the symbols that form the strings of the language being defined)
• P is a finite set of rules or productions, P: V → (V ∪ T)*
(represent the recursive definition of the language.)
• S is the start symbol that represents the language being defined.
(Other variables represent auxiliary classes of strings that are used to help
define the language of the start symbol.)
Examples:
1. G= ({S}, {a, b}, P, S), where
P: S → aSb
S → bSa or S  aSb | bSa |ε
S→ε Compact Form
2. G= ({S, F}, {0, 1}, P, S), where
P: S → 00S | 11F
F → 00F | ε
Derivations:
The productions of a grammar are used to derive strings.
One Step Derivation or Direct Derivation:
v is one-step derivable from u, written u  v, if:
u=xαz
v = x β z if αβ in P
and say than x α z derives x β z or x α z yields x β z
Example:
A → aAa | B
B → bB | ε
Let w = aaabbaaa, Derive w.
A  aAa  aaAaa  aaaAaaa  aaaBaaa  aaabBaaa
aaabbBaaa  aaabbaaa
Derivations:
Zero or more derivation steps:

u v (read: u derives v) for k ≥ 0,

u  u1  u2  ….  uk  v
⇒ (single step derivations)
A → aAa | B ⇒k (k step derivations)
B → bB |ε ⇒* (derivations of 0 or more steps)
Let w = aaabbaaa:
A  aAa  aaAaa  aaaAaaa  aaaBaaa  aaabBaaa aaabbBaaa  aaabbaaa

A aaabbaaa
Language specified by CFG:
If G = (V, T, P, S) is a CFG then the language specified by G (or the language of G)
is a Context Free Language denoted as

L(G) = { w ɛ T* | S w}
i.e., the set of strings over T derivable from the start symbol S, and the elements of
L(G) are called sentence.

Examples:
• G = ({S}, {0,1}. {S → 0S1 | ε }, S) L(G) = {0n1n | n > 0}
• All strings of balanced parentheses
P  ε | ( P ) | PP | { P }
W = ((())), (({()}))
Parse Tree or Derivation Tree
• The sequence of substitutions used to obtain a string using a CFG is called a derivation and
may be represented by a tree called derivation tree or a parse tree
• A derivation tree or parse tree is an ordered rooted tree that graphically represents the
semantic information of a string derived from a context-free grammar.
Example:
A → aAa | B
B → bB |ε
w = aaabbaaa

• Root label = start node

• Each interior label = variable.
• Each parent/child relation = derivation step.
• Each leaf label = terminal or ε.
• The leaves of a parse tree when read or concatenated left to
right, are called the frontier or yield of the tree.
• However, if all the leaves are Null, derivation is Null.
Yield of a Tree
Example:
S → SS | aSb | ε
Derive the string w= abaabb
S → SS
→ aSbS
→ abS
→ abaSb
→ abaaSbb
→ abaabb
Parse Tree or Derivation Tree
Sentential Form and Partial Derivation Tree
A partial derivation tree is a sub-tree of a parse tree such that either all its children
are in the sub-tree or none of them are in the sub-tree.

Example:
SaSb | ε
w = aaabbb
Derivation or Yield of a Tree
S ⇾ S S | (S) | ε
Derive Strings i. ()() ii. (())()
S ⇒ SS ⇒ (S)S ⇒ ()S ⇒ ()(S) ⇒ ()()
S ⇒ SS ⇒ (S)S ⇒ ((S))S ⇒ (())S ⇒ (())(S) ⇒ (())()

S ⇒ SS ⇒ S(S) ⇒ (S)(S) ⇒ (S)() ⇒ ()()

Leftmost and Rightmost derivation
• A derivation is basically a sequence of production rules, in order to get the input
string.
• During derivation, choices will be there to replace the nonterminal in the body.
Example
Production rules: Choose first X from Left Side
X→X+X X→X+X
X→X*X
X→a Choose first X from Right Side
String: a + a * a X→X+X
•To decide which non-terminal to be replaced with production rule, two options.
• Leftmost Derivation  Chooses the leftmost nonterminal to expand
• Rightmost Derivation  Chooses the rightmost nonterminal to expand
Leftmost and Rightmost derivation
Example
Production rules:
X→X+X A left-sentential form occurs in a leftmost derivation
X→X*X A right-sentential form occurs in a rightmost derivation
X→a
String: a + a * a

The left-most derivation is: The right-most derivation is:

X→X*X X→X*X
X → X + X* X X→X*a
X→a+X*X X→X+X*a
X→a+a*X X→X+a*a
X→a+a*a X→a+a*a
Leftmost derivation

Rightmost derivation
Ambiguity in context free grammars
• A grammar is said to be ambiguous, if it permits a terminal string to have more
than one parse tree i.e. more than one leftmost derivation or more than one
rightmost derivative for the same string.
• If the grammar is not ambiguous then it is called unambiguous.
Example:
S aSb | SS | ∈
String: aabb

More than one leftmost derivation

Ambiguity in context free grammars
Example:
E  E+E | E*E | id
Prove that grammar is ambiguous or not?
String: id+id*id

Two left most derivations possible, ambiguous grammar

Ambiguity in context free grammars
S → if ( E ) S | if ( E ) S else S
S → other
E → expr
Example: if ( expr ) if ( expr ) other else other
Two different rightmost derivations:
S ⟹ if ( E ) S
⟹ if ( E ) if ( E ) S else S
⟹2 if ( E ) if ( E ) other else other
⟹2 if ( expr ) if ( expr ) other else other
S ⟹ if ( E ) S else S
⟹ if ( E ) S else other
⟹ if ( E ) if ( E ) S else other
⟹ if ( E ) if ( E ) other else other
⟹2 if ( expr ) if ( expr ) other else other
Ambiguity in context free grammars
S → if ( E ) S | if ( E ) S else S
S → other
E → expr
Example: if ( expr ) if ( expr ) other else other

•The two parse trees translate differently the else part

•The else part can be attached to inner if (should be the case) or to outer if
Two right most derivations possible, ambiguous grammar
Problems
Prove that the following grammars are ambiguous
1. S  A | A B
A  ε | a | A b | AA
B b|bc|Bc|bB
w = aabb
S  AB  AAB  aAB  aaB  aabB  aabb
S  AB  AbB  Abb  AAbb  Aabb  aabb
 These two derivations use same productions, but in different orders.

S -> S1S
S -> 0
w = 0101010
Problems
Show that the following grammars are ambiguous
1. SaB|ab
AaAB|a
BABb|b w= ab
2. SSaSbS | SbSaS | ε w=aabbab
3. S  A | A B
A  ε | a | A b | AA
B  b | b c | B c | b B w = aabb
4. S -> S1S | 0 w = 0101010.
5. S -> 1A0S | 1A0S1S | 0
A -> 1 w = 110110010
6. S -> AA
A -> AAA | 1A | A1 | 0 w = 010
Problems
[Link] the CFG for Set of all integers.
Show the derivation steps for +17 and -123
Answer: SAI
A+|-
IDI|D
D0|1|2|3|4|5|6|7|8|9
Derivation of -123
SAI
Derivation of +17
-I
SAI
-DI
+I
-1I
+DI
-1DI
+1I
-12I
+1D
-12D
+17
-123
Problems
2. Design the CFG for L = {wcwr | w is in {a,b}*}
Answer: SaSa | bSb | c
3. Design the CFG for L = {anbn | n≥1}
Answer: SaSb| ab
4. Design the CFG for L = {anbncmdm | n≥1, m≥1}
Answer: SAB 7. Design the CFG for L = {w ɛ {0,1}* | #0(w) = #1(w)}
AaAb | ab
Answer: S1S0S|0S1S|ɛ
BcBd | cd
5. Design the CFG for L = {anbmcmdn | n≥1, m≥1}
Answer: SaSd | aAd
AbAc | bc
6. Design the CFG for L = {anb2n | n≥0}
Answer: SASB |ɛ
Aa
B bb
Problems
Given a CFG, Find
(a) Left most derivation
(b) Right most derivation
(c) Derivation Tree
1. S0B|1A, A0|0S|1AA, B1|1S|0BB
w = 00110101
2. SA|B, A0A|ε, B0B|1B|ε,
w =00101
3. S  (S) | S ⸧S |~S| p| q
w= (~~p⸧(p⸧~~q))
Problems
Given a CFG, Find (a) Left most derivation (b) Right most derivation (c)
Derivation Tree for the following
1. S0B|1A, A0|0S|1AA, B1|1S|0BB
w = 00110101
2. SA|B, A0A|ε, B0B|1B|ε,
w =00101
3. S  (S) | S ⸧S |~S| p| q w= (~~p⸧(p⸧~~q))
1. SaAcB | BdS AaB | aBc | a BaAcA | cAB | b
w1=aacb w2=abcaababcd w3=aacbbcc w4=bccaacdca
5. EE+T | T TT*F|F F(E) | a w= a+a*a
Problems
Prove that the following grammars are ambiguous
1. S  A | A B
A  ε | a | A b | AA
B b|bc|Bc|bB
w = aabb
2. S -> S1S | 0
w = 0101010.
3. S -> 1A0S | 1A0S1S | 0
A -> 1
w = 110110010
4. S -> AA
A -> AAA | 1A | A1 | 0
w = 010
Applications of CFG
• Context-free grammars are used as basis for compiler design and implementation
• Context-free grammars are used as specification mechanisms for programming
languages, like describing syntax of programming languages
• Arbitrary nesting of operators
• Parenthesis balancing
• Designers of compilers use such grammars to implement compiler’s components, such
as scanners, parsers, code generators, code synthesizers
• The implementation of almost any programming languages is preceded by a context-
free grammar that specifies it.
• Markup languages i.e.
a. Nested Tag Matching HTML
<html> …<p> …
<a href=…> … </a>
</p> …
</html>
b. XML