Step 1: Recall closure properties of context-free languages.
Context-free languages (CFLs) are closed under:
• Union
• Concatenation
• Intersection with regular languages
Step 2: Analyze the given operations.
Intersection (L1 ∩ L2):
Since one of the languages involved is regular, the intersection remains
context-free.
Concatenation (L1 · L2):
CFLs are closed under concatenation, so the resulting language is
context-free.
Union (L1 ∪ L2):
CFLs are closed under union, hence the result is context-free.
Step 3: Examine set difference.
The set difference can be written as:
L1 − L2 = L1 ∩ ̅L2
Context-free languages are not closed under complementation. Therefore, ̅L2 may not be context-free, and the intersection does not guarantee a CFL.
Final Conclusion:
The operation that does not necessarily preserve context-freeness is:
Final Answer: (C)
Consider the following languages: \[ L_1 = \{a^n w a^n | w \in \{a, b\}^*\} \] \[ L_2 = \{ w x w^R | w, x \in \{a, b\}^*, |w|, |x| > 0 \} \] Note that \( w^R \) is the reversal of the string \( w \). Which of the following is/are TRUE?
Consider the following languages:
\( L_1 = \{ ww \mid w \in \{a,b\}^* \} \)
\( L_2 = \{ a^n b^n c^m \mid m, n \geq 0 \} \)
\( L_3 = \{ a^m b^n c^n \mid m, n \geq 0 \} \)
Which of the following statements is/are FALSE?