Closure properties of CFLs. I mentioned in class that if L is a CFL and R is reg

Question

Closure properties of CFLs. I mentioned in class that if L is a CFL and R is regular, then L cap R is a CFL. What about L1 cap L2 when both are CFLs, and what about other properties you might expect? For each of the following, let L1 and L2 be arbitrary CFLs and determine whether the given language MUST be a CFL ("YES"), or you can find a counterexample ("NO"), i.e., particular choices of CFLs L1 and L2 such that the language is not a CFL. For the YES's give a short justification involving the construction of a grammar/PDA from the given grammars/PDAs. For the NO's, use the CFL pumping lemma or known non-context-free languages to establish your counterexample.
(a) L1 L2 (concatenation)
(b) L1 cap L2 (intersection)
(c) L1 cup L2 (union)
(d) L1* (asterate)
(By the way, the book gives an example showing ~L1 is not necessarily a CFL; not helpful for this problem but good to know.)

Explanation / Answer

Context-free languages are closed under

Union

Let L1 and L2 be two context free languages. Then L1 L2 is also context free.

Example

Let L1 = { anbn , n > 0}. Corresponding grammar G1 will have P: S1 aAb|ab

Let L2 = { cmdm , m 0}. Corresponding grammar G2 will have P: S2 cBb|

Union of L1 and L2, L = L1 L2 = { anbn } { cmdm }

The corresponding grammar G will have the additional production S S1 | S2

Concatenation

If L1 and L2 are context free languages, then L1L2 is also context free.

Example

Union of the languages L1 and L2, L = L1L2 = { anbncmdm }

The corresponding grammar G will have the additional production S S1 S2

Kleene Star

If L is a context free language, then L* is also context free.

Example

Let L = { anbn , n 0}. Corresponding grammar G will have P: S aAb|

Kleene Star L1 = { anbn }*

The corresponding grammar G1 will have additional productions S1 SS1 |

Context-free languages are not closed under

Intersection If L1 and L2 are context free languages, then L1 L2 is not necessarily context free.

Intersection with Regular Language If L1 is a regular language and L2 is a context free language, then L1 L2 is a context free language.

Complement If L1 is a context free language, then L1’ may not be context free.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.