Closure Properties of Context Free Languages Notes | EduRev

Theory of Computation

Computer Science Engineering (CSE) : Closure Properties of Context Free Languages Notes | EduRev

The document Closure Properties of Context Free Languages Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

Closure Properties of Context Free Languages

Context Free Languages (CFLs) are accepted by pushdown automata. Context free languages can be generated by context free grammars, which have productions (substitution rules) of the form :
A -> ρ (where A ∈ N and ρ ∈ (T ∪ N)* and N is a non-terminal and T is a terminal) 

Properties of Context Free Languages 

➤ Union : If L1 and L2 are two context free languages, their union L1 ∪ L2 will also be context free. For example,
L1 = { anbncm | m >= 0 and n >= 0 } and L2 = { anbmcm | n >= 0 and m >= 0 }
L3 = L1 ∪ L2 = { anbncm ∪ anbmcm | n >= 0, m >= 0 } is also context free.  
L1 says number of a’s should be equal to number of b’s and L2 says number of b’s should be equal to number of c’s. Their union says either of two conditions to be true. So it is also context free language.
Note: So CFL are closed under Union. 

Concatenation : If L1 and If L2 are two context free languages, their concatenation L1.L2 will also be context free. For example,
L1 = { anbn | n >= 0 } and L2 = { cmdm | m >= 0 }
L3 = L1.L2 = { anbncmdm | m >= 0 and n >= 0} is also context free.
L1 says number of a’s should be equal to number of b’s and L2 says number of c’s should be equal to number of d’s. Their concatenation says first number of a’s should be equal to number of b’s, then number of c’s should be equal to number of d’s. So, we can create a PDA which will first push for a’s, pop for b’s, push for c’s then pop for d’s. So it can be accepted by pushdown automata, hence context free.
Note: So CFL are closed under Concatenation. 

➤ Kleene Closure : If L1 is context free, its Kleene closure L1* will also be context free. For example,
L1 = { anbn | n >= 0 }
L1* = { anbn | n >= 0 }* is also context free.
Note : So CFL are closed under Kleen Closure. 

➤ Intersection and complementation : If L1 and If L2 are two context free languages, their intersection L1 ∩ L2 need not be context free. For example, 

L1 = { anbncm | n >= 0 and m >= 0 } and L2 = (ambncn | n >= 0 and m >= 0 } 

L3 = L1 ∩ L2 = { anbncn | n >= 0 } need not be context free. 

L1 says number of a’s should be equal to number of b’s and L2 says number of b’s should be equal to number of c’s. Their intersection says both conditions need to be true, but push down automata can compare only two. So it cannot be accepted by pushdown automata, hence not context free.
Similarly, complementation of context free language L1 which is ∑* – L1, need not be context free.
Note : So CFL are not closed under Intersection and Complementation. 

➤ Deterministic Context-free Languages 
Deterministic CFL are subset of CFL which can be recognized by Deterministic PDA. Deterministic PDA has only one move from a given state and input symbol, i.e., it do not have choice. For a language to be DCFL it should be clear when to PUSh or POP.
For example, L1= { anbncm | m >= 0 and n >= 0} is a DCFL because for a’s, we can push on stack and for b’s we can pop. It can be recognized by Deterministic PDA. On the other hand, L3 = { anbncm ∪ anbmcm | n >= 0, m >= 0 } cannot be recognized by DPDA because either number of a’s and b’s can be equal or either number of b’s and c’s can be equal. So, it can only be implemented by NPDA. Thus, it is CFL but not DCFL.
Note : DCFL are closed only under complementation and Inverse Homomorphism. 

Try yourself:Consider the language L1,L2,L3 as given below. 
L1 = { ambn | m, n >= 0 } 
L2 = { anbn | n >= 0 } 
L3 = { anbncn | n >= 0 } 
Which of the following statements is NOT TRUE? 
View Solution

Try yourself:The language L = { 0i12i | i ≥ 0 } over the alphabet {0, 1, 2} is : 
View Solution

Try yourself:Consider the following languages: 
L1 = { 0n1n| n≥0 } 
L2 = { wcwr | w ɛ {a,b}* } 
L3 = { wwr | w ɛ {a,b}* } 
Which of these languages are deterministic context-free languages? 
View Solution

Try yourself:Which one of the following grammars generate the language L = { aibj | i ≠ j } 
View Solution

Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

practice quizzes

,

MCQs

,

Closure Properties of Context Free Languages Notes | EduRev

,

Objective type Questions

,

Exam

,

study material

,

Closure Properties of Context Free Languages Notes | EduRev

,

Viva Questions

,

past year papers

,

Summary

,

Free

,

Sample Paper

,

Closure Properties of Context Free Languages Notes | EduRev

,

Semester Notes

,

Important questions

,

Previous Year Questions with Solutions

,

Extra Questions

,

mock tests for examination

,

shortcuts and tricks

,

ppt

,

pdf

,

video lectures

;