All mock tests are FREE till 31 December — register to save your progress
Unit 8 · Theory of Computation and Compilers Paper 2 CS · June 2024 Re-Exam

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

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

Show answer & explanation

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

Explanation

(B) is the concatenation of wⁱxⁱ and yᵏzᵏ, so it is CF. (A) needs one counter: add for w and y, subtract for x and z, and accept if the counter ends at 0. A PDA can track the sign with its bottom marker. (C), (D) and (E) each need two independent equalities (three-way comparisons), which no PDA can check.

More Theory of Computation and Compilers questions