Closure properties of Context-free languages and
Gmammars
Prof. (Dr.) K.R. Chowdhary
Email: kr.chowdhary@iitj.ac.in
Former Professor & Head, Department of Computer Sc. & Engineering
MBM Engineering College, Jodhpur

Saturday 19th July, 2025

kr chowdhary

TOC

1/ 7

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

Closure properties of CNF
Intersection of two CFLs: Let G1 , G2 be two context-free
grammars.
G1 :

G2 :

S → AB, S → A,A → 0A1

S → BA, S → A, A → 1A0

B → 0B, B → 0

A → 10, B → 0B, B → 0

∴ L(G ) = {0n 1n 0+ }

∴ L(G2 ) = {0+ 1n 0n }

1

/ CFL for n ≥ 1.
= 0n 1n 0n ∈

∴ L1 ∩ L2
Union of two CFLs: For L1 = (G1 ) and L2 = (G2 ), L1 ∪ L2 ∈ CFL.
S → S1 |S2 , and V1 ∩ V2 = φ
P = P1 ∪ P2 ∪ {S → S1 |S2 }, V = V1 ∪ V2 ∪ {S}, Σ = Σ1 ∪ Σ2 .
Concatenation of two CFLs: For L1 = (G1 ) and L2 = (G2 ),
L1 ◦ L2 ∈ CFL.
S → S1 ◦ S2 , and V1 ∩ V2 = φ
P = P1 ∪ P2 ∪ {S → S1 ◦ S2 }, V = V1 ∪ V2 ∪ {S}, Σ = Σ1 ∪ Σ2 .
Kleene star of two CFLs: For L1 = (G1 ) and L2 = (G2 ), L∗1 ∈ CFL,
where S → S1 S|ε, V1 ∩ V2 = φ .
kr chowdhary

TOC

2/ 7

Closure properties of CFLs
CFL ∩ Reg. lang ∈ CFL
Let M1 is NPDA accepting CF language L1 by final state, and M2 be
a FA accpeting L2 . The PDA recognizing L1 ∩ L2 simulates P and M
simultaneously, like cross-product of two FA.
We construct new NPDA M for L1 ∩ L2 to simulate M1 and M2 in
parallel.

kr chowdhary

TOC

3/ 7

Closure properties of CFLs
CFL ∩ Reg. lang ∈ CFL . . .

Simulaitng start state: For q0 ∈ M1 , p0 ∈ M2 there is (q0 , p0 ) ∈ M
Simulaitng final state: For q1 ∈ F1 , and p1 , p2 ∈ F2 there is
(q1 , p1 ), (q1 , p2 ) ∈ F .

kr chowdhary

TOC

4/ 7

decision problems for CFLs
Membership problem: For CFG G1 , find if w ∈ L(G ) ?
The membership algorithm is: Parser. That is, if we are able to
obtain a parse-tree for given word w , then w ıL(G ) else not.
Empty Language: Is L(G ) = φ ?
Algorithm:
1. Remove useless symbols
2. Check if start symbol is useless? If yes, then L(G ) = φ else not.
Infinite Language Problem: Is L = L(G ) an infinite language?
Algorithm:
1. remove useless symbols
2. remove null and unit productions
3. create dependency graph for variables
4. if there is a loop in the dependency graph, then L is infinite
language else not.

kr chowdhary

TOC

5/ 7

decision problems for CFLs

Infinite Language Problem: Is L = L(G ) an infinite language? . . .
Let the gramamr be:
S → AB, A → aCb|a, B → bB|bb
C → cBS

Since there is a loop in the dependency graph, the language is
infinite. The derivation is S ⇒∗ (acbb)i S(bbb)i .

kr chowdhary

TOC

6/ 7

Bibliography

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

kr chowdhary

TOC

7/ 7