A Context Free Language (CFL) is a language produced by a Context Free Grammar, according to formal language theory (CFG). The majority of arithmetic expressions are produced using Context Free Grammars, one of the many programming language applications for Context Free Languages.
In this article, we will look more into the Context Free Language Closure Properties according to the GATE Syllabus for (Computer Science Engineering) CSE. We will read ahead to find out more about it.
What are Context Free Language Closure Properties?
Context Free Languages fall under the following:
- Union
- Concatenation
- Kleene Star Operation
Union
If L1 and L2 are two CFLs, L1 ∪ L2 will also be Context Free.
Example
If L1 = { pnqn , n > 0}. The corresponding grammar G1 would have P: S1 → pPq|pq
If L2 = { rmsm , m ≥ 0}. The corresponding grammar G2 would have P: S2 → rQq| ε
The union of L1 and L2, L = L1 ∪ L2 = { pnqn } ∪ { rmsm }
The increased production will be in the matching grammar G. Here, S → S1 | S2
Concatenation
In case L1 and L2 are CFLs, then L1L2 would also be Context Free.
Example
The union of the L1 and L2 languages, L = L1L2 = { pnqnrmsm }
The G corresponding grammar will have the additional S → S1 S2 production.
Kleene Star Operation
In case L is a CFL, then L* would also be Context Free.
Example
If L = { anbn , n ≥ 0}
The corresponding grammar G would have P: S → pPq | ε
Kleene Star L1 = { pnqn }*
The G1 corresponding grammar will consist of additional productions S1 → SS1 | ε
The CFL is not closed under the following:
- Intersection − In case L1 and L2 are CFL, then L1 ∩ L2 is not Context Free necessarily.
- Intersection with regular language − In case L2 is a CFL and L1 is a regular language, then L1 ∩ L2 is a CFL.
- Complement − If L1 is a CFL, then 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.
Also Explore,
