- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

**If L1 and L2 are CFLs, then their union L1 + L2 is a CFL.**Here CFL refers to Context Free Language.

L1 CFL implies that L1 has a CFG, let it is CFG1, that generates it.

Assume that the nonterminals in CFG1 are S, A, B, C, . . ..

Change the nonterminal in CFG1 to S1, A1, B1, C1, . . ..

Don’t change the terminals in the CFG1.

L2 CFL implies that L2 has a CFG, Let it is CFG2, that generates it.

Assume that the nonterminals in CFG2 are S, A, B, C, . . ..

Change the nonterminal in CFG2 to S2, A2, B2, C2, . . ..

Don’t change the terminals in the CFG2.

Now CFG1 and CFG2 have non intersecting sets of nonterminals.

We create a CFG for L1 + L2 as follows −

Include all of the nonterminal S1, A1, B1, C1, . . . and S2, A2, B2, C2, . . ..

Include all the productions of CFG1 and CFG2.

Create a new nonterminal S and a production.

S → S1 | S2

**Example**

CFG1 for L1 S → S | Aa | Bb | ∧ A → Sa | bB | ab B → S | a CFG2 for L2 S → aS | aA | Bb | ∧ A → aS |bB| ab B → Ba | b

To construct CFG for L1 + L2, follow the below mentioned steps −

Transform CFG1 as follows −

S1 → S1| A1a | B1b | ∧ A1 → S1a | bB1 | ab B1 → S1 | a

Transform CFG2 as follows

S2 → aS2 | aA2 | B2b | ∧ A2 → aS2 |bB2| ab B2 → B2a | b

Construct CFG for L1 + L2 as follows −

S → S1 | S2 S1 → S1| A1a | B1b | ∧ A1 → S1a | bB1 | ab B1 → S1 | a S2 → aS2 | aA2 | B2b | ∧ A2 → aS2 |bB2| ab B2 → B2a | b

- Related Questions & Answers
- Explain the context free language closure under concatenation?
- What are the closure properties for context free language?
- Explain Pumping lemma for context free language
- Explain about pumping lemma for context free language?
- Explain the Closure Under Kleene Star of CFL in TOC?
- How to generate the language for context free grammar?
- Explain the simplification of context free grammar in TOC
- Explain union operation in relational algebra (DBMS)?
- Explain the Union operation on 2D shapes in JavaFX
- What is context free grammar? Explain with examples
- Explain about CYK Algorithm for Context Free Grammar
- Explain removing unit productions in context free grammar
- Explain the Union to pointer in C language
- Give the examples of a context free language that are not regular?
- How to show that regular language is closed under the complementary operation?

Advertisements