Consider the languages: L1 = {anbncm | n, m > 0} L2 = {anbmcm | n, m > 0}…
2005
Consider the languages:
L1 = {anbncm | n, m > 0}
L2 = {anbmcm | n, m > 0}
Which one of the following statements is FALSE?
- A.
L1 ∩ L2 is a context-free language
- B.
L1 U L2 is a context-free language
- C.
L1 and L2 are context-free language
- D.
L1 ∩ L2 is a context sensitive language
Attempted by 19 students.
Show answer & explanation
Correct answer: A
L1 = {anbncm | n, m > 0} and L2 = {anbmcm | n, m > 0} are both context-free languages. Their intersection L1 ∩ L2 requires strings to have equal numbers of a, b, and c in the form anbncn. This language is not context-free because it requires two comparisons (a=b and b=c), which cannot be handled by a single stack. Therefore, L1 ∩ L2 is not context-free and must be at least context-sensitive.
A video solution is available for this question — log in and enroll to watch it.