Which of the following is a context-free language? (A) {wⁱ xʲ yᵏ zˡ | i + k = j + l, i, j, k, l ≥ 0} (B) {wⁱ xʲ yᵏ zˡ | i = j, k = l} (C) {wⁱ xʲ yᵏ zˡ | i = j = k and k ≠ l} (D) {wⁱ xʲ yᵏ zˡ | i = j = k + l} (E) {wⁱ xʲ yᵏ zˡ | i = j = l and k ≠ l}

1. A(A) and (B) Only
2. B(B) and (C) Only
3. C(C) and (D) Only
4. D(D) and (E) Only

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: A. (A) and (B) Only

Explanation

(A) needs only one counter (push for w and y, pop for x and z) and (B) is two independent nested matches — both context-free. (C), (D) and (E) each need two simultaneous equalities among three blocks, which a single stack cannot track.