Consider the languages L1, L2 and L3 as given below. \(L_1=\{0^p1^q \mid…

PYQ GATE 2011

Consider the languages L1, L2 and L3 as given below.

L1={0p1q∣p,q∈N},L_1=\{0^p1^q \mid p,q\in N\},

L2={0p1q∣p,q∈N and p=q}L_2=\{0^p1^q \mid p,q\in N\text{ and }p=q\} and

L3={0p1q0r∣p,q,r∈N and p=q=r}.L_3=\{0^p1^q0^r \mid p,q,r\in N\text{ and }p=q=r\}. Which of the following statements is NOT TRUE?

  1. A.

    Push Down Automata (PDA) can be used to recognize L1L_1 and L2L_2

  2. B.

    L1L_1 is a regular language

  3. C.

    All the three languages are context free

  4. D.

    Turing machines can be used to recognize all the languages

Attempted by 203 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…