GATE Papers >> CSE >> 2011 >> Question No 26

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

L1= {0^p 1^q |  p , q ∈ N },

L2= {0  ^p   1  ^q   |   p  ,  q  ∈ N  and  p  = q} and 

L3 = {0^p 1^q 0^r |   p  ,  q , r   ∈ N and   p   =  q  = r}. W h ich of the following statements is NOT TRUE?

• (A)  Push Down Automata (PDA) can be used to recognize L1 and L2   
• (B)  L1 is a regular language   
• (C)  All the three languages are context free   
• (D)  Turing machines can be used to recognize all the languages