0
Explain closure properties of CFL

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: May 2014

0
0
1. Context-free languages are closed under Union

If $L_1$ is context-free and $L_2$ is context-free, then $L_1 \ U \ L_2$

2. Context-free languages are closed under Concatenation If $L_1$ is context-free and $L_2$ is context-free, then $L_1L_2$

3. Context-free languages are closed under Star operation If L is context-free, then L*

Negative properties:

1. Context-free languages are not closed under Intersection If $L_1$ is context-free and $L_2$ is not necessarily context-free, then $L_1 \ ∩ \ L_2$

2. Context-free languages are not closed under Complement If $L_1$ is context-free, then $L_1$ complement is not necessarily context-free

0