Consider the following languages. L1 = {ai bj ck | i = j, k ≥ 1} L2 = {ai bj |…

PYQ GATE 2008

Consider the following languages.

L1 = {ai bj ck | i = j, k ≥ 1}

L2 = {ai bj | j = 2i, i ≥ 0}

Which of the following is true?

  1. A.

    L1 is not a CFL but L2 is

  2. B.

    L1 ∩ L2 = ∅ and L1 is non-regular

  3. C.

    L1 ∪ L2 is not a CFL but L2 is

  4. D.

    There is a 4-state PDA that accepts L1, but there is no DPDA that accepts L2

Attempted by 89 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…