GATE CSE 1999 | Question: 2.4

Question

If $L1$ is context free language and $L2$ is a regular language which of the following is/are false?

• A. $L1-L2$ is not context free

• B. $L1 \cap L2$ is context free

• C. $\sim L1$ is context free

• D. $\sim L2$ is regular

Comments

Regular ⊆ CFL, but regular languages are “weak” enough that intersecting them with a CFL cannot force extra counting power.

Although every regular language is a CFL, CFL ∩ CFL is not closed because some CFLs are too powerful, while CFL ∩ REG is closed because regular languages are restricted.

examples 

 

---

@Sarah Sayed more powerful on what terms?

---

@Taniii it means Intersecting two CFLs can combine their independent constraints in a way that requires more computational power than a PDA provides

Answer 1

$L_2$ is regular, so complement of $L2, ( \sim L2)$, is also regular .

Regular languages are closed under complement. So, D is  True.

$L_1 \cap L_2$ is context free.

Intersection of Context free language with Regular language is Context free.  So, B is True.

$L_1 - L_2 = L_1 \cap (\sim L_2)$  is context free

Intersection of Context free language with Regular language is Context free.  So, A is  False .

$\sim L_1$ is not context free

Context free languages are not closed under complement.  So C is False  (May/not be).

Comments

@Praveen Saini sir L1−L2= L1∩(∼L2)  is context free How we can write like this .

 

---

@chandan sahu – An example from the set theory. Let L1 ={a, b, c} and L2 =  { c, d }. Then L1 - L2 is defined as elements that are in L1 and not in L2. So L1 – L2 = { a, b }.

L1 ∩ (~L2) gives the same answer.

---

got it

Answer 2

Analyzing L1 minus L2 (Is it not context free?) implies FALSE

We can rewrite the set-difference operation using intersections and complements:
L1 minus L2 is equal to L1 intersected with the complement of L2.

Now, let's look at the components:
L2 is Regular. Because Regular languages are strictly closed under complement, the complement of L2 is also Regular.
L1 is a Context-Free Language.
This simplifies the problem down to checking the closure property of a Context-Free Language intersected with a Regular Language.

The Rule: The intersection of any Context-Free Language and a Regular Language is always a Context-Free Language. You can mechanically prove this via a cross-product construction of a pushdown automaton and a deterministic finite automaton.
Because L1 minus L2 is guaranteed to be a Context-Free Language, the statement "L1 minus L2 is not context free" is FALSE.

Analyzing L1 intersected with L2 (Is it context free?) implies TRUE

As established in the previous step, this is the exact closure property of a Context-Free Language intersected with a Regular Language.

The Logic: A pushdown automaton for L1 and a deterministic finite automaton for L2 can be combined together into a new hybrid pushdown automaton. The states of this new machine track both the pushdown automaton and deterministic finite automaton states simultaneously, while still using the single stack from the original pushdown automaton.
Since the resulting machine is a valid pushdown automaton, the language L1 intersected with L2 is always a Context-Free Language. Therefore, this statement is TRUE.

Analyzing the complement of L1 (Is it context free?) implies FALSE

This checks the absolute fundamental boundary rule of regular Context-Free Languages:
The Rule: Context-Free Languages are NOT closed under complement.
The Classic Counterexample: If L1 is the union of the language a to the n, b to the n, c to the m and the language a to the m, b to the n, c to the n (which is a valid Context-Free Language), its complement requires tracking two sets of independent counts at the same time to match errors, which cannot be modeled using one stack.
Because the complement of a Context-Free Language is not guaranteed to be a Context-Free Language, declaring universally that "the complement of L1 is context free" is FALSE.

Analyzing the complement of L2 (Is it regular?) implies TRUE

This checks the closure property of the lowest level of the hierarchy:
The Rule: Regular languages are completely closed under complement.
The Machine Proof: If you take a valid, complete deterministic finite automaton that recognizes L2, you can build an exact machine for the complement of L2 simply by flipping every non-final state into a final state, and every final state into a non-final state.
Since the flipped machine is still a valid deterministic finite automaton, the complement of L2 is guaranteed to be Regular. Therefore, this statement is TRUE.

Answer 3

L1 : CFL , L2 : RL
option A : L1-L2
=L1∩(∼L2)
=CFL∩(∼RL)
=CFL∩(RL) ( as RL is closed under complementation )
=CFL∩CFL ( as if lang is RL then it is CFL also )
may be CFL or not ( as CFL is not closed under intersection)
hence option A statement may be false may not be ( here nothing mentioned about "ALWAYS")
option B : same logic as option A
hence option B statement may be false may not be
option C : CFL is not closed under intersection so we cant say anthing about it whether it is CFL or not 
option D : True as RL is closed under complementation 

but question asking about FALSE statements ( all given options are TRUE)
so Ans is None 

verify this

Comments

what is the meaning of closed in such type of questions

---

It refers to the closure properties of the language.

please refer to this video for a better understanding: https://youtu.be/0E1Mbr1LcZM?si=rKLAd9TJplNDZBSh