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.
Table of Contents
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.
