Which of the following are context free language ? (A) {wⁱxʲyᵏzˡ | i+k=j+l, where i, j, k, l≥0} (B)…
Language A (i + k = j + l) can be accepted by a pushdown automaton that counts the w's and y's against the x's and z's, and B (i = j and k = l) is two independent matched…
Choose your answer
Which of the following are context free language ? (A) {wⁱxʲyᵏzˡ | i+k=j+l, where i, j, k, l≥0} (B) {wⁱxʲyᵏzˡ | i=j and 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} Choose the correct answer from the options given below :
Answer and explanation
Correct answer A
Language A (i + k = j + l) can be accepted by a pushdown automaton that counts the w's and y's against the x's and z's, and B (i = j and k = l) is two independent matched blocks, so both are context-free. C needs i = j = k, three equal counts, which a single stack cannot check. D with l = 0 reduces to i = j = k, and E forces i = j = l, again three equal counts, so C, D and E are not context-free and only A and B qualify.
Practice for these exams
-
UGC NET Computer Science and Applications