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

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 Correct Answer III and IV only

Consider the options one by one:

Option 1:

L₁ = {a^p | p is a prime number}

Prime numbers do not have fixed pattern. So, it is not possible to solve it using pushdown

automaton. So, L₁ is not context free language.

Option 2:

L₂ = {aⁿb^mc^2m | n ≥ 0, m ≥ 0}

It can be solved easily using single stack.  Comparison is done between b and c. We can make a pushdown automaton for this. So, L₂ is context free language.

Option 3:

L₃ = {aⁿbⁿc²ⁿ | n ≥ 0}

First comparison is between a and b, then between b and c, therefore two stacks are required.

So, it is context sensitive language. L₃ is recursive language.

Option 4:

L₄ = { aⁿbⁿ | n ≥ 1}

First push a into a stack then pop a for each b from the stack. The given language is accepted by