# Closure Properties of CFL

Languages that lack context are known as CFLs. Pushdown automata, or CFLs, are accepted by the machine. Regular languages are also supported by pushdown automata. According to the Chomsky Hierarchy of Languages, CFLs are type 2 languages and include regular languages.

In this article, we will look more into the Closure Properties of CFL according to the GATE Syllabus for (Computer Science Engineering) CSE. We will read ahead to find out more about it.

## What are the Closure Properties of CFL?

A context-free language is closed under the following:

## Union

In case L1 and L2 are two context-free languages, L1 âˆª L2 will also be context-free.

### Example

In case L1 = { anbn , n > 0}

The G1 corresponding grammar would have P: S1 â†’ aAb|ab

In case L2 = { cmdm , m â‰¥ 0}

The G2 corresponding grammar would have P: S2 â†’ cBb| Îµ

The union of L1 and L2 would be L = L1 âˆª L2 = { anbn } âˆª { cmdm }

Here, the G corresponding grammar would have the additional production, that is, S â†’ S1 | S2

## Concatenation

In case L1 and L2 are CFLs, then L1L2 would also be context-free.

### Example

The union of the languages L1 and L2 would be L = L1L2 = { anbncmdm }

The G corresponding grammar would have the additional production, that is, S â†’ S1 S2

## Kleene Star

In case L is a CFL, then L* would also be context-free.

### Example

In case L = { anbn , n â‰¥ 0}

Then, the G corresponding grammar would have P: S â†’ aAb| Îµ

Thus, the Kleene Star L1 = { anbn }*

Here, the G1 corresponding grammar would have additional productions, and they are S1 â†’ SS1 | Îµ

The CFLs do not get closed under the following:

• Intersection âˆ’ In case L1 and L2 are CFLs, then the L1 âˆ© L2 is not context-free.
• Intersection with regular language âˆ’ In case L1 happens to be a regular language, while L2 is a CFL, then L1 âˆ© L2 would be a CFL.
• Complement âˆ’ In case the L1 is a CFL, L1â€™ might not be context-free.

Keep learning and stay tuned to get the latest updates onÂ GATE ExamÂ along withÂ GATE Eligibility Criteria,Â GATE 2023,Â GATE Admit Card,Â GATE Syllabus,Â GATE Previous Year Question Paper, and more.