Closure properties of context free grammar

Context free language
Context free Grammar
Closure properties of context free language.
Closure properties of context free grammar.
Union, Concatenation, Kleene closure, Intersection, Complement, Applications of CFL

1. Presented by:
Malaika, Hajira, Anisa
Presented to:
Dr. Fouzia
1/24/2020

2. CLF has several properties.
Context free languages are closed under union.
Context free languages are closed under concatenation.
Context free languages are closed under Kleene Closure.
Context free languages are closed under Reversal.
Context free languages are closed under Intersection.
Context free languages are closed under Complement.
ontext
Free Languages
Closure Properties
Union
Concatenation
Kleene closure
Reversal
Intersection
Complement

3. R.G
F.A
R.L
PDA
CFL
CFG

4. Context Free Language
•A language generated by context
free grammar is known as context
free language.
•The set of all context free language is
identical to the set of languages
accepted by PDA or more powerful
than PDA.

5. P = production
rule

P = production
rule

V = set of
variable or
non terminal

S = Start
Symbol
Σ = set of
terminal

1/24/2020
Context Free Grammar is Defined by 4 Tuples

6. • A α
Where
• α ∈ {V υ Σ}*
And
• A ∈ V

Production Rule
•Context free grammar has a production
rule in the form of:

7. •For generating a language that
generates equal number of a’s and
b’s in the form of a
n
b
n
.

Where

•L = (a
n
b
n
| n > = 0)

EXAMPLE:

8. 1/24/2020
G = {(S,A), (a, b), (S aAb, A aAb ∕ ϵ)}
–The start symbol is S
•S aAb (A aAb)
•S aaAbb (A aAb)
•S aaAbb (A aAb)
•S aaaAbbb (A ϵ )
•S aaabbb
Finally we get string aaabbb
oThis is of the form
a
3
b
3

EXAMPLE:

9. Closure
Properties of
Context Free
Languages:

10. What is Closure Property?
•A set is closed under an operation if
doing the operation on a given set
always produces a member of the
same set.
Example:
oIf a and b are two integers. Then
a + b is also an integer.
oSo + operation is closed under
addition.

11. Example:
oIf a and b are two integers. Then a / b may not
be an integer.
oSo / operation is not closed under integers.

Example:
oIf A = { 1, 2, 3, 4}. If a, b ∈ A Then a + b is also
an integer. But a + b may not belong to A.
oSo + operation is not closed under addition
Cont.

12. Kleene star Concatenation Union
1/24/2020
This means that Closure Property for CFL is:

•When operation is applied to a certain context-
free languages the result will also be a
context-free language.


•Some of the Closure Property of context
free language are there:

13. Union:
•If L1 and If L2 are
two context free
languages, their
union L1 ∪ L2 will
also be context free.

14. Example:

•L
1 = { a
n
b
n
c
m
| m >= 0 and n >= 0 } and
•L
2 = { a
n
b
m
c
m
| n >= 0 and m >= 0 }

•L = L
1 ∪ L
2 = { a
n
b
n
c
m
∪ a
n
b
m
c
m
| n >= 0, m >= 0 }
is also context free.

•L
1 says number of a’s should be equal to number of
b’s and L
2 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.

15. •If L1 and If L2 are two context free languages,
their concatenation L1.L2 will also be context
free.
Concatenation

16. Example

•L
1 = { a
n
b
n
| n >= 0 } and L
2 = { c
m
d
m
| m >= 0 }
•L = L
1.L
2 = { a
n
b
n
c
m
d
m
| m >= 0 and n >= 0} is also
context free.
•L
1 says number of a’s should be equal to number of
b’s. L
2 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.

17. Kleene Closure

18. INTERSECTION
&
COMPLEMENT

19. 1/24/2020
INTERSECTION:

The CFG is Not necessarily closed under intersection.
oL
1={a
n
b
n
a
m
| m, n >= 1} is context free language.
•G
1 = { S→AB
•AaAb|ab
•BcB|c}
oL
2={a
n
b
m
a
m
| m,n >=1} is context free language.
•G
2={SAB
•AaA|a
•BbBc|bc}
oL
1∩ L
2 = {a
n
b
n
a
n
| n ≥ 1}, which is known not to be a CFL
(pumping lemma).
oNote: L
1∩ L
2 can be defined by a TM.

20. COMPLEMENT
oAssume that CFL is closed under
complementation.
•Let L
1 and L
2 are CFL.
•L
1
c
and L
2
c
are CFL.
•L
1
c
∪ L
2
c
is also a CFL. (As union closed under CFL)
•(L
1
c
∪ L
2
c
)
c
has to be CFL.
•But
•According to DEMORGANS LAW:
•(L
1
c
∪ L
2
c
)
c
= L
1 ∩ L
2 is NOT necessarily a CFL.
CONTRADICTION !!!
•Hence CFL is NOT necessarily closed under
complementation.

21. A
P
P
L
I
C
A
T
I
O
N
s
Context Free Grammar (CFG) is of great
practical importance.
oIt is used for following purposes:

•For defining programming languages
•For translation of programming
languages
•For describing arithmetic expressions
•For construction of compilers
•Data Processing

22. Question
1. Consider the language L
1, L
2, L
3 as given below.
L
1 = { a
m
b
n
| m, n >= 0 }
L
2 = { a
n
b
n
| n >= 0 }
L
3 = { a
n
b
n
c
n
|n>= 0 }
Which of the following statements is NOT TRUE?
A.Push Down Automata (PDA) can be used to recognize
L
1 and L
2.
B.L
1 is a regular language
C.All the three languages are context free
D.Turing machine can be used to recognized all three
languages.

23. THANKS