If L1 and L2 are context free languages, which of the following is True about L1∩L2 ?
L1∩L2 is Recursively Enumerable
Context-free languages are closed under union, concatenation and Kleene star, but not under intersection. Every context-free language is, however, recursive (membership is decidable by the CYK algorithm), and recursive languages are closed under intersection.
Step 1 — Take L1 = {anbncm} and L2 = {ambncn}; both are context free. Their intersection is {anbncn}, which is not context free (pumping lemma). So the intersection need not be context free, and it certainly need not be regular.
Step 2 — For any string w, decide w ∈ L1 and w ∈ L2 separately (CYK on each grammar) and accept when both succeed. This always halts, so L1∩L2 is recursive and therefore Recursively Enumerable in every case.
Step 3 — The claims 'context free' and 'Regular' fail for the example above, and the intersection need not be finite either: {anbncn} is infinite, and the intersection of a context-free language with itself is the whole (possibly infinite) language. Recursive enumerability, by contrast, holds without any exception.
L1∩L2 is Recursively Enumerable option is correct.
Similar Questions
According to pumping lemma for context free languages :
Let L be an infinite context free language, then there exists some positive integer m such that any \(w \in L\) with \(|w| \ge m\) can be decomposed as \(w = uvxyz\)
Consider a language A defined over the alphabet \(\Sigma = \{0, 1\}\) as \(A = \left\{0^{\lfloor n/2 \rfloor} 1^{n} : n \gt = 0\right\}\).
The expression \(\lfloor n/2 \rfloor\) means the floor of n/2, or what you get by rounding n/2 down to the nearest integer.
Which of the following is not an example of a string in A ?
Given the following two languages :
\(L_{1} = \{a^{n}\, b\, a^{n} \mid n \gt 0\}\)
\(L_{2} = \{a^{n}\, b\, a^{n}\, b^{n+1} \mid n \gt 0\}\)
Which of the following is correct ?
Which of the following are context free language ?
(A) {wi xj yk zl | i + k = j + l, where i, j, k, l ≥ 0}
(B) {wi xj yk zl | i = j and k = l, where i, j, k, l ≥ 0}
(C) {wi xj yk zl | i = j = k and k ≠ l, where i, j, k, l ≥ 0}
(D) {wi xj yk zl | i = j = k + l, where i, j, k, l ≥ 0}
(E) {wi xj yk zl | i = j = l and k ≠ l, where i, j, k, l ≥ 0}
Choose the correct answer from the options given below :
In Pumping Lemma for context free languages, to say a language is satisfying pumping lemma, what is the minimum length of ‘vx’ together, if you consider the string as ‘uvwxy’?
Let L = {0n1n|n ≥ 0} be a context free language.
Which of the following is correct ?
Given the following two statements :
A. L = {w|na(w) = nb(w)} is deterministic context free language, but not linear.
B. L = {an bn} ∪ {an b2n} is linear, but not deterministic context free language.
Which of the following options is correct ?
Given the following two languages :
L1 = {an bn | n ≥ 0, n ≠ 100}
L2 = {w ∈ {a, b, c}*| na(w) = nb(w) = nc(w)}
Which of the following options is correct ?
Important Questions from Context Free Languages
- Let $\Sigma = \{a, b, c, d\}$ and let $L = \{a^ib^jc^kd^\ell \mid i, j, k, \ell \ge 0\}$.
Which of the following constraints ensure(s) that the language $L$ is context-free? According to pumping lemma for context free languages :
Let L be an infinite context free language, then there exists some positive integer m such that any \(w \in L\) with \(|w| \ge m\) can be decomposed as \(w = uvxyz\)
Consider a language A defined over the alphabet \(\Sigma = \{0, 1\}\) as \(A = \left\{0^{\lfloor n/2 \rfloor} 1^{n} : n \gt = 0\right\}\).
The expression \(\lfloor n/2 \rfloor\) means the floor of n/2, or what you get by rounding n/2 down to the nearest integer.
Which of the following is not an example of a string in A ?
Given the following two languages :
\(L_{1} = \{a^{n}\, b\, a^{n} \mid n \gt 0\}\)
\(L_{2} = \{a^{n}\, b\, a^{n}\, b^{n+1} \mid n \gt 0\}\)
Which of the following is correct ?
Which of the following are context free language ?
(A) {wi xj yk zl | i + k = j + l, where i, j, k, l ≥ 0}
(B) {wi xj yk zl | i = j and k = l, where i, j, k, l ≥ 0}
(C) {wi xj yk zl | i = j = k and k ≠ l, where i, j, k, l ≥ 0}
(D) {wi xj yk zl | i = j = k + l, where i, j, k, l ≥ 0}
(E) {wi xj yk zl | i = j = l and k ≠ l, where i, j, k, l ≥ 0}
Choose the correct answer from the options given below :
