Consider the languages L1, L2, and L3 as given below.
L1 = {0^p 1^q | p, q in N and p = q}
L2 = {0^p 1^q 0^r | p, q, r in N and p = q}
L3 = {0^p 1^q 0^r | p, q, r in N and p = q = r}
Which of the following statements is NOT TRUE?
A. Push Down Automata (PDA) can be used to recognize L1 and L2.
B. L2 is a regular language.
C. All the three languages are context free.
D. Turing machines can be used to recognize all the languages.
GATE 2011 · Theory of Computation · Identify Class Language · medium
Answer: Statement B ('L2 is a regular language') is NOT TRUE. L2 requires counting and is CFL but not regular. Answer: B
Check option A: PDA can recognize L1 and L2: L1 = {0^p 1^p} — PDA: push 0s, pop for 1s. TRUE. L2 = {0^p 1^p 0^r} — PDA: push 0s while reading 0s, then pop for each 1 (verifying p=q), then accept any trailing 0s. TRUE. So A is TRUE.
Check option B: L2 is regular: L2 requires p = q (equal number of leading 0s and 1s). A DFA cannot count unboundedly, so L2 cannot be regular. Proof: take 0^n 1^n 0 in L2 for any n. By pumping lemma, if L2 were regular, we could pump the leading 0s: 0^(n+k) 1^n 0 would be in L2, but n+k != n, contradiction. So B ('L2 is regular') is FALSE.
Check option C: All three languages are context free: L3 = {0^p 1^q 0^r | p=q=r}: requires matching p=q AND p=r simultaneously. A PDA has one stack and cannot verify two independent equalities with different symbols. By the pumping lemma for CFLs, L3 is not CFL (similar to a^n b^n c^n). So C is also FALSE.
Check option D: Turing machines recognize all three: All three languages are decidable (recursive). A TM can count each segment and verify the conditions. So D is TRUE.