Suppose that \(L_1\) is a regular language and \(L_2\) is a context-free language. Which one of the following languages is NOT necessarily context-free?
Show Hint
- \(L_1 \cap L_2\)
- \(L_1 \cdot L_2\)
- \(L_1 - L_2\)
- \(L_1 \cup L_2\)
The Correct Option is C
Solution and Explanation
Step 1: Recall closure properties.
Context-free languages are closed under union and concatenation. They are also closed under intersection with regular languages.
Step 2: Analyze each option.
\(L_1 \cap L_2\) is context-free because CFLs are closed under intersection with regular languages.
\(L_1 \cdot L_2\) is context-free because CFLs are closed under concatenation.
\(L_1 \cup L_2\) is context-free due to closure under union.
Step 3: Examine set difference.
The language \(L_1 - L_2 = L_1 \cap \overline{L_2}\). Context-free languages are not closed under complementation. Hence, this operation does not guarantee a context-free language.
Step 4: Conclusion.
Therefore, \(L_1 - L_2\) is NOT necessarily context-free.
Final Answer: (C)
Top Questions on Regular and contex-free languages, pumping lemma
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?- GATE CS - 2022
- Theory of Computation
- Regular and contex-free languages, pumping lemma
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?
- GATE CS - 2022
- Theory of Computation
- Regular and contex-free languages, pumping lemma
- Let \(L_1\) be a regular language and \(L_2\) be a context-free language. Which of the following languages is/are context-free?
- GATE CS - 2021
- Theory of Computation
- Regular and contex-free languages, pumping lemma
- Let \(L \subseteq \{0,1\}^*\) be an arbitrary regular language accepted by a minimal DFA with \(k\) states. Which one of the following languages must necessarily be accepted by a minimal DFA with \(k\) states?
- GATE CS - 2021
- Theory of Computation
- Regular and contex-free languages, pumping lemma
Questions Asked in GATE CS exam
In the diagram, the lines QR and ST are parallel to each other. The shortest distance between these two lines is half the shortest distance between the point P and the line QR. What is the ratio of the area of the triangle PST to the area of the trapezium SQRT?
Note: The figure shown is representative
- GATE CS - 2025
- Geometry
Consider the following process information for Shortest Remaining Time First (SRTF) scheduling:
\[ \begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time (AT)} & \textbf{Burst Time (BT)} \\ \hline P1 & 0 & 10 \\ P2 & 1 & 13 \\ P3 & 2 & 6 \\ P4 & 8 & 9 \\ \hline \end{array} \]Find the turnaround time for each process.
- GATE CS - 2025
- Programming in C
- If IMAGE and FIELD are coded as FHBNJ and EMFJG respectively then, which one among the given options is the most appropriate code for BEACH?
- GATE CS - 2025
- GATE IN - 2025
- GATE MT - 2025
- GATE NM - 2025
- GATE TF - 2025
- Logical and Analytical Reasoning Skills
A square paper, shown in figure (I), is folded along the dotted lines as shown in figures (II) and (III). Then a few cuts are made as shown in figure (IV). Which one of the following patterns will be obtained when the paper is unfolded?
- GATE CS - 2025
- Paper Folding and Cutting
Consider the relationships among P, Q, R, S, and T:
• P is the brother of Q.
• S is the daughter of Q.
• T is the sister of S.
• R is the mother of Q.
The following statements are made based on the relationships given above.
(1) R is the grandmother of S.
(2) P is the uncle of S and T.
(3) R has only one son.
(4) Q has only one daughter.
Which one of the following options is correct?- GATE CS - 2025
- Blood Relations