GATE | GATE-CS-2017 (Set 2) | Question 48

Consider the following languages.
L1 = {ap | p is a prime number}
L2 = {anbmc2m | n >= 0, m >= 0}
L3 = {anbnc2n | n >= 0}
L4 = {anbn | n >= 1}

Which of the following are CORRECT ?
I. L1 is context free but not regular.
II. L2 is not context free.
III. L3 is not context free but recursive.
IV. L4 is deterministic context free.
(A) I, II and IV only

(B) II and III only

(C) I and IV only

(D) III and IV only

Answer: (D)

L1 is neither regular nor context free but context sensitive language.

L2 is context free, push any number of a’s and then for each b, pop two c’s until all b’s are over and this can be done by using only one stack.

L3 is not context free because we are not sure when to pop b and push a, because it is comparison between three consecutive terminals.

Clearly L4 is deterministic context free because we are sure of pushing a into stack first and on seeing b we are sure of popping a.

Statement III and IV are correct, option (D) is true.

Quiz of this Question

My Personal Notes arrow_drop_up