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 ?
L1 is context free language, L2 is not context free language.
Context-free languages are closed under intersection with a regular language, and \(\{a^n b^n c^n\}\) is the standard non-context-free language.
L1: it equals \(\{a^n b^n : n \ge 0\} \cap \overline{\{a^{100} b^{100}\}}\). The first set is context free and the complement of a single string is regular, so L1 is context free (a PDA simply also rejects the one string with 100 a’s).
L2: intersect it with the regular set \(a^* b^* c^*\). The result is \(\{a^n b^n c^n : n \ge 0\}\), which the pumping lemma shows is not context free. If L2 were context free the intersection would be too, so L2 is not context free.
Calling both context free ignores the three-way count in L2; calling L1 non-context-free ignores that removing one string keeps a CFL context free.
L1 is context free language, L2 is not context free language. 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 :
If L1 and L2 are context free languages, which of the following is True about L1∩L2 ?
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 ?
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 :
