GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 3

Question

If $A$ is a regular language, $E$ a deterministic context-free language, $F$ a context-free language and for any language $L, L^c$ denotes its complement, which of the following statements is/are TRUE? (Mark all the appropriate choices)

• A. $E \cap F$ is context-free
• B. $A \cap E^c$ is deterministic context-free
• C. $E \cap F^c$ is context-free
• D. $A \cap F^c$ is context-free

Answer 1

A is false. We can take two DCFLs $L_1 = \{a^nb^nc^m|n,m \geq 0\}$

$L_2 = \{a^mb^nc^n|n,m \geq 0\}$

Now, $L_1 \cap L_2 = \{a^nb^nc^n \mid n \geq 0\}$ is not a CFL.

B is true as DCFL set is closed under complement and intersection with a regular language.

CFLs are not closed under complement. So, C and D are false.

Reference: https://gatecse.in/closure-property-of-language-families/

Comments

For option A if we take E as a DCFL and F as an NCFL then wouldn’t DCFL intersection NCFL be NCFL?

---

As shown in the answer, intersection of two DCFLs itself CAN give a non CFL, then how can a DCFL intersection NCFL guarantee to give a CFL? After all any DCFL is also an NCFL.

---

okay Sir, got confused. Thanks for clarifying.