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
Closure properties of Regular languages
• Closure properties of regular languages describe how regular languages remain regular when
certain operations are applied to them.
• A closure property states that if a new language is formed using regular languages and a
specific operation, the resulting language is also regular.
• These properties also explain how DFAs for new regular languages can be constructed using
DFAs of existing regular languages and specific operations.
• Assume L1 and L2 are regular languages, then
• Union : L1 ∪ L2 is regular. (L1 + L2 or L1 | L2 )
• Concatenation : L1L2 is regular
• Kleene Star (∗) : If L is regular, then L* is also regular.
• Complement : If L is regular, then LC or L’ (complement of L) is also regular,L’ = ∑* - L
• Intersection : L1 ∩ L2 is regular.
• Difference : L1 - L2 is regular.
• Reversal : If L is regular, then LR (set of reversed strings) is also regular.
• Homomorphism: A homomorphism (substitution of strings for symbols) of a regular
language is regular.
• The inverse homomorphism of a regular language is regular.
Closure properties of Regular languages
Complement
L = Strings of 0's and l’s that end in 01
Regular Expression: = ((0 +l)*01 )).

• The new DFA 𝑀′ has the same states, alphabet, transitions, and start state as 𝑀
• The accepting states in 𝑀′ are those that were non-accepting in M, and vice versa.

L’ = Strings of 0's and l’s that does not end in 01

Closure properties of Regular languages
Intersection
Assume L1 and L2 are regular languages, then By DeMorgan’s law

• The regular languages are closed under complement and union.

• So, L∩M is regular when L and M are regular.
Closure properties of Regular languages

Construct a new DFA M using the product construction:

M = (Q, ∑, δ, q , F) = (Q1 * Q2, {0,1}, δ, (q , q ), F)

δ((q ,q ), x) = (δ1(q , x), δ2(q , x)) For every x ε ∑

Union  F = {(q1,q2) | q1 ε F1 or q2 ε F2}

Intersection  F = {(q1,q2) | q1 ε F1 and q2 ε F2}
Difference  F = {(q1,q2) | q1 ε F1 and q2 ε F2}
Closure properties of Regular languages

M1 = (Q1, ∑, δ1, q , F1) = ({q ,q }, {0,1}, δ1, q , {q })

M2 = (Q2, ∑, δ2, q , F2) = ({q ,q }, {0,1}, δ1, q , {q })
M = (Q, ∑, δ, q , F) = (Q1 * Q2, {0,1}, δ, (q , q ), F)
Q1 * Q2 = {(q , q ), (q , q ), (q , q ), (q , q )}
δ((q ,q ), x) = (δ1(q , x), δ2(q , x))
δ((q ,q ), 0) = (δ1(q , 0), δ2(q , 0)) = (q ,q )
δ((q ,q ), 1) = (δ1(q , 1), δ2(q , 1)) = (q ,q ) δ((q ,q ), 0) = (δ1(q , 0), δ2(q , 0)) = (q ,q )
δ((q ,q ), 0) = (δ1(q , 0), δ2(q , 0)) = (q ,q ) δ((q ,q ), 1) = (δ1(q , 1), δ2(q , 1)) = (q ,q )
δ((q ,q ), 1) = (δ1(q , 1), δ2(q , 1)) = (q ,q ) δ((q ,q ), 0) = (δ1(q , 0), δ2(q , 0)) = (q ,q )
δ((q ,q ), 1) = (δ1(q , 1), δ2(q , 1)) = (q ,q )
Closure properties of Regular languages
δ((q ,q ), 0) = (δ1(q , 0), δ2(q , 0)) = (q , q ) δ((q ,q ), 0) = (δ1(q , 0), δ2(q , 0)) = (q ,q )
δ((q ,q ), 1) = (δ1(q , 1), δ2(q , 1)) = (q , q ) δ((q ,q ), 1) = (δ1(q , 1), δ2(q , 1)) = (q ,q )
δ((q ,q ), 0) = (δ1(q , 0), δ2(q , 0)) = (q , q ) δ((q ,q ), 0) = (δ1(q , 0), δ2(q , 0)) = (q ,q )
δ((q ,q ), 1) = (δ1(q , 1), δ2(q , 1)) = (q , q ) δ((q ,q ), 1) = (δ1(q , 1), δ2(q , 1)) = (q ,q )
F1= {q } F2= {q })
Union  F = {(q1,q2) | q1 ε F1 or q2 ε F2} Union  F = {(q , q ), (q , q ), (q , q )}
Intersection  F = {(q1,q2) | q1 ε F1 and q2 ε F2} Intersection  F = {(q , q )}
Difference  F = {(q1,q2) | q1 ε F1 and q2 ε F2} Difference  F = {(q , q )}

DFA for L1 ∪ L2 accepts when DFA for L1 ∩ L2 accepts DFA for L1 − L2 accepts when
either M1 or M2 accepts. when both M1 and M2 accept. M1 accepts and M2 rejects.
CONSTRUCTING THE CROSS-PRODUCT DFA
Construct a DFA that accepts all strings from the language L = {strings with size multiples of 2
and 3} where Σ = {a}
Language L1 = {strings with size multiples of 2}
Language L2 = {strings with size multiples of 3}

Language L1 ∩ L2 = {strings with size multiples of 2 and 3}

Closure properties of Regular languages
Language containing even number of a’s and any number of b’s.
• L1 = {ε, aab, b, baa, aabbbbb, aaaab, ..........} - Accepted
• L1 = {aaa, abbb, baaa, bbaaba, ...........} - Not Accepted

Language containing even number of b’s and any number of a’s.

• L2 = {ε, bba, a, abb, bbbbaaaa, bbbba, ...........} - Accepted
• L2 = {bbb, bbba, abbb, aaba, ...........} - Not Accepted

Language containing even number of a’s and b’s

• L = {ε, aa, bb, abab, aabb, baba, bbaa, .......} - Accepted
• L = {aaa, aaabb, aaabaabb, aaabb, baaba, bbbaa, .......} - Not Accepted
Closure properties of Regular languages
• Reversal of a Regular Language is Regular
• The reversal of a string a1a2 ... an is the string written backwards, that is, anan-1 ... A2a1
• wR for the reversal of string w.
• Example: w = 0010 and wR = 0100 and εR = εR
• LR is the reversal of a language L, consisting of the reversals of all its strings.
• If L={001,10,111}, then LR ={100, 01, 111}
Proof: (proof by automaton creation)
• Let L be recognized by a Finite Automaton (FA) M.
• Turn M into a FA for LR, by
1. Reverse all the arcs in the transition diagram for M,
2. Make the start state of M be the only accepting state for the new automaton.
3. Create a new start state p0 with transitions on ε to all the accepting states of M.
• The result is an automaton that, simulates M "in reverse" and therefore accepts a string
w if and only if M accepts wR
Closure properties of Regular languages
L = {wa or wb | w ∈ {a, b, c, d}∗}
M = (Q, ∑, δ, q0, F)
M = ({q0, q1, q2, q3,q4}, {a,b,c,d}, δ, q0, {q2,q4})

1. Reversing the direction of the transitions

2. Adding new initial state having ϵ-transitions to the original final states

3. Change original initial state to the unique new final state

MR = (Q U {q5}, ∑, δR, q5, {q0})

Closure properties of Regular languages
• The Regular Languages are Closed under Homomorphism
• A homomorphism is a transformation where each symbol in a string is replaced with another
string in a consistent way.
• Let, Σ = {a, b} and string w = abab,
• Let h(a) = 00 and h(b) = 11 then applying h to w gives
• h(w) = h(a) h(b) h(a) h(b) = 00110011
• Similarly, homomorphism can be applied to every string in a language.
• Let L = ab*b then the strings in L are {ab, abb, abbb, abbbb, ...}
• Applying h to each string in L, h(L) = {0011, 001111, 00111111, 0011111111, ...}
• h(L) = 00 (11)* which is a regular language.
• Thus, if a language L is regular, its homomorphic image h(L) is also regular. This proves that
regular languages are closed under homomorphism.
Closure properties of Regular languages
Single-Character Substitutions

• Replace ‘a’ by ‘x’, ‘b’ by ‘y’, and ‘c’ by ‘z’, the existence
of the resulting finite automata proves that the language
is still regular.
Closure properties of Regular languages
• The replacement doesn’t have to be one-to-one.
• For example, if 'a' and 'b' are both replaced by 'w', and 'c' is replaced by 'z', the resulting
automaton becomes non-deterministic. However, it is still a finite automaton, which means
the language it accepts remains regular.
Closure properties of Regular languages
String Substitutions
• Replacing each character in a language with a string.
• Replace 'a' with "cat“
• Replace 'b' with "dog"
Closure properties of Regular languages
Example:
1. Let Σ0 = {0, 1}, Σ1 = {a, b}, and h(0) = ab, h(1) = a.
• h(10) = aab
• h(010) = abaab
• h(1100) = aaabab

2. h(0) = ab; h(1) = ε.

• h(01010) = ababba
• Let L be the language of regular expression 01* + 10*.
• Then h(L) is the language of regular expression abε* + ε(ab)*.
Closure properties of Regular languages
Suppose h is the homomorphism from the alphabet {0,1,2} to the alphabet {a,b} defined
by: h(0)=a, h(1)=ab, and h(2)=ba.
a) What is h(0120)?
b) What is h(21120)?
c) If L is the language L(01*2), what is h(L)?
d) If L is the language L(0 + 12), what is h(L)?
Solution:
What is h(0120)?
h(0)=a,h(1)=ab,h(2)=ba,h(0)=a
h(0120)=a⋅ab⋅ba⋅a=aabba
What is h(21120)?
h(2)=ba,h(1)=ab,h(1)=ab,h(2)=ba,h(0)=a
h(21120)=ba⋅ab⋅ab⋅ba⋅a=baababbaa
If L is the language L(01*2), what is h(L)?
Closure properties of Regular languages
If L is the language L(01*2), what is h(L)?

The language 𝐿=01∗2 consists of strings that start with

0, followed by zero or more occurrences of 1, and end with 2.

That is, strings of the form:

0,02,012,0112,01112,…

Applying h:
h(0)=a
h(1∗)=(ab) (zero or more repetitions of "ab")
h(2)=ba

Thus, the homomorphic image of L is:

h(L)=a(ab)∗ba
Closure properties of Regular languages
If L is the language L(0 + 12), what is h(L)?

The language 𝐿=0 + 12 consists of the strings either "0" or "12":

h(L)={a,abba}

Suppose L is the language {ababa} that is the language consisting of only the one string ababa
What is h-1(L).
Breaking "ababa" into valid segments based on
h(1)=ab
h(2)=ba
h(0)=a
Now, let's find possible sequences that produce "ababa":
h(1)h(2)h(0)=ab+ba+a=ababa
This corresponds to the string "120" in {0,1,2}. h-1(L) = 120
Closure properties of Regular languages
Inverse Homomorphism:
• Let h be a homomorphism, and let L be a language where the alphabet matches the output of h.
• h-1(L) = {w | h(w) is in L}

Let h(0) = ab; h(1) = ε.

Let L = {abab, baba}.

• h-1(L) consists of strings where there are exactly two 0's (since each 0 maps to ab) and any
number of 1's (since 1 is mapped to ε, meaning it can appear anywhere without affecting the
output).
• The language h-1(L) can be expressed as L = 1*01*01* which means any number of 1’s, with
exactly two 0’s anywhere in the string.