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 :
(A), (B) Only
A language is context-free when a pushdown automaton can accept it. A PDA has one stack, so it can match one count against another, but it cannot keep two independent equalities over three or more blocks.
Step 1 — (A) i + k = j + l: track the single difference (i + k) − (j + l) on the stack. Push a symbol for each w; for each x pop one (or push a 'negative' marker when empty); for each y push or cancel a negative marker; for each z pop a positive marker (or push a negative marker when none is left). Accept on an empty stack. One counter with a sign is enough, so (A) is context-free.
Step 2 — (B) i = j and k = l: it is the concatenation of {wixi} and {ykzk}, each generated by a grammar S → wSx | ε, so (B) is context-free.
Step 3 — (C) i = j = k and k ≠ l: taking l = 0 and k ≥ 1 gives wnxnyn, which fails the pumping lemma for context-free languages, so (C) is not context-free.
Step 4 — (D) i = j = k + l: with l = 0 this is again wnxnyn; pumping wpxpyp changes at most two of the three blocks, breaking i = j = k + l, so (D) is not context-free.
Step 5 — (E) i = j = l and k ≠ l: three equal counts over w, x and z (with y between) again defeat a single stack by the same pumping argument, so (E) is not context-free.
Only (A) and (B) are context-free. Every combination containing (C), (D) or (E) includes a language that needs two simultaneous equalities.
(A), (B) Only 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 ?
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 ?
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 ?
If L1 and L2 are context free languages, which of the following is True about L1∩L2 ?
