CFL Identification MCQs: 12 Solved Questions with Explanations

CFL-identification questions rarely name the theorem you need. Separate finite-state patterns from one-stack dependencies, then watch for copying, crossing counts and three-way equality. One unbounded count is a stack's job; a count that has to agree with two other blocks at once, or a block that has to be reproduced left to right rather than reversed, is beyond one stack. Before you look at the options, label each language regular, DCFL, CFL but not regular, or not CFL.

A five-check method for identifying a CFL

1. Simplify the parameters. Substitute one variable wherever two of them always move together: a^(n+m) b^(n+m) a^(n+m) is just a^k b^k a^k, and the classification follows at once.

2. Test finite memory. If a fixed number of states can track everything the language constrains, it is regular and no stack is needed.

3. Map each unbounded dependency to LIFO order. A count that is pushed on the way in and popped on the way out is a stack's job. A count that must still be available after it has already been matched against another block is not.

4. Check the three traps. Copying (ωω), crossing counts (a^m b^n a^m b^n) and three-way equality (a^n b^n c^n) each demand a count that one stack has already spent.

5. Use closure only when both operands are known. Complement, and intersection with a regular language, keep a DCFL. The intersection of two context-free languages need not be context-free.

Review the one-stack test in Context-Free Grammars and Pushdown Automata and the finite-state boundary in Regular Expressions and the Pumping Lemma.

For L_A = {a^m b^n c^(m+n)}, m=2,n=3 gives aabbbccccc: push five markers across aabbb, then pop across ccccc. For L_B = {a^n b^n c^n}, n=2 gives aabbcc. Matching a with b consumes the count still needed for c; this three-way equality is not CFL.

CFL identification MCQs 1-3: PDA scope, a deterministic separator and the copy-language trap

Question 1: language accepted by a PDA

The language accepted by Push Down Automaton:

• A. Recursive Language

• B. Context free language

• C. Linearly Bounded language

• D. All of the mentioned

Correct answer: B. Context free language.

A nondeterministic PDA recognises exactly the CFLs. Recursive and context-sensitive families are broader; deterministic PDAs recognise the DCFL subset.

Question 2: deterministic separator

The language L = { 0ⁱ 2 1ⁱ | i ≥ 0 } over the alphabet {0,1,2} is

• A. not recursive

• B. is recursive and is a deterministic CFL

• C. is a regular language

• D. is not a deterministic CFL but a CFL

Correct answer: B. is recursive and is a deterministic CFL.

Push per 0; the unique 2 switches deterministically to popping per 1. Accept at simultaneous input and stack end, including 2 when i=0. Unbounded equality is not regular.

Question 3: reversal versus copying

Find the non-context free language among the following.

• A. L = {ωω^R | ω ∈ {0,1}*}

• B. L = {p^n q^n | n ≥ 0}

• C. L = {ωω | ω ∈ {0,1}*}

• D. L = {p^n q^m r^m s^n | n,m ≥ 0}

Correct answer: C. L = {ωω | ω ∈ {0,1}*}.

A stack matches ω with ω^R and the nested counts in p^n q^m r^m s^n, but cannot reproduce arbitrary ω left-to-right. For ω=01, copying needs 0101; stack reversal gives 0110.

CFL identification MCQs 4-6: adding counts and spotting a reused dependency

Question 4: one summed count

The language {a^m b^n c^(m+n) | m,n ≥ 1} is

• A. Regular

• B. Context-free but not regular

• C. Context sensitive but not context free

• D. Type-0 but not context sensitive

Correct answer: B. Context-free but not regular.

For m=2,n=3, aabbbccccc needs five pushes across aabbb and five pops across ccccc; finite memory cannot store unbounded m+n. Grammar S -> aSc | aTc, T -> bTc | bc generates exactly m+n trailing c symbols.

Question 5: reusing the same count

Consider the following two languages over the alphabet {a, b, c}, where m and n are natural numbers. L_1 = {a^m b^m c^(m+n) | m,n ≥ 1} and L_2 = {a^m b^n c^(m+n) | m,n ≥ 1}. Which ONE of the following statements is CORRECT?

• A. Both L_1 and L_2 are context-free languages.

• B. L_1 is a context-free language but L_2 is not a context-free language.

• C. L_1 is not a context-free language but L_2 is a context-free language.

• D. Neither L_1 nor L_2 are context-free languages.

Correct answer: C. L_1 is not a context-free language but L_2 is a context-free language.

For L_2, push m+n times across a^m b^n, then pop across c^(m+n). In L_1, one m must enforce both |a|=|b| and |c|>|a|; matching a^m b^m consumes that stack count. Pumping or Ogden's lemma formalises the non-CFL result.

Question 6: simplify n+m first

Consider the following languages: L_1 = {a^(n+m) b^n a^m | n,m ≥ 0} and L_2 = {a^(n+m) b^(n+m) a^(n+m) | n,m ≥ 0}. Which of the following is correct?

• A. Only L_1 is context free language

• B. Only L_2 is context free language

• C. Both L_1 and L_2 are context free languages

• D. Both L_1 and L_2 are not context free languages

Correct answer: A. Only L_1 is context free language.

For L_1, push across the first block and pop across b^n a^m; at n=2,m=1, aaabba has three symbols on each side. Setting k=n+m reduces L_2 to non-CFL {a^k b^k a^k}.

CFL identification MCQs 7-9: complements, finite exceptions and intersection

Question 7: classify three languages separately

Which of the following are context free?

A = {a^n b^n a^m b^m | m,n ≥ 0}

B = {a^m b^n a^m b^n | m,n ≥ 0}

C = {a^m b^n | m ≠ 2n, m,n ≥ 0}

• A. A and B only

• B. A and C only

• C. B and C only

• D. C only

Correct answer: B. A and C only.

A concatenates two equal-count CFLs. B repeats two counts in the same order, a non-CFL copy pattern. For C, {a^m b^n | m=2n} is DCFL; complementing it within regular a*b* makes m≠2n DCFL. Thus a^5b^2 belongs, while a^4b^2 does not.

Question 8: a finite exception and equal counts

Given the following two languages: L_1 = {a^n b^n | n ≥ 0, n ≠ 100} and L_2 = {w ∈ {a,b,c}* | n_a(w) = n_b(w) = n_c(w)}. Which of the following options is correct?

• A. Both L_1 and L_2 are not context free language

• B. Both L_1 and L_2 are context free language.

• C. L_1 is context free language, L_2 is not context free language.

• D. L_1 is not context free language, L_2 is context free language.

Correct answer: C. L_1 is context free language, L_2 is not context free language.

Removing singleton a^100b^100 from {a^n b^n} preserves context-freeness. If L_2 were CFL, intersecting it with regular a*b*c* would produce non-CFL {a^n b^n c^n}, a contradiction.

Question 9: compute the intersection

Consider L = L_1 ∩ L_2 where L_1 = {0^m 1^m 2 0^n 1^n | m,n ≥ 0} and L_2 = {0^m 1^n 2^k | m,n,k ≥ 0}. Then, the language L is

• A. Recursively enumerable but not context free

• B. Regular

• C. Context free but not regular

• D. Not recursive

Correct answer: C. Context free but not regular.

L_2 permits no 0 or 1 after 2, so L_1 must have n=0. Therefore L={0^m1^m2 | m>=0}, one unbounded equality plus a fixed symbol: CFL but not regular. At m=2, 00112 is in both languages.

CFL identification MCQs 10-12: several constraints in one question

Question 10: linear and nonlinear constraints

Consider the following languages: I. {a^m b^n c^p d^q | m+p = n+q, m,n,p,q ≥ 0}; II. {a^m b^n c^p d^q | m=n and p=q, m,n,p,q ≥ 0}; III. {a^m b^n c^p d^q | m=n=p and p ≠ q, m,n,p,q ≥ 0}; IV. {a^m b^n c^p d^q | mn = p+q, m,n,p,q ≥ 0}. Which of the languages above are context-free?

• A. I and IV only

• B. I and II only

• C. II and III only

• D. II and IV only

Correct answer: B. I and II only.

I tracks signed balance +m-n+p-q; aabd gives 2+0=1+1. II concatenates two equal-count CFLs. Restricting III to q=0,r>0 gives non-CFL {a^r b^r c^r}. IV's multiplication constraint is non-semilinear, hence not CFL.

Question 11: exploit existential choices

Consider the following languages: L_1 = {a^n w a^n | w ∈ {a,b}*} and L_2 = {w x w^R | w,x ∈ {a,b}*, |w|,|x| > 0}. Note that w^R is the reversal of the string w. Which of the following is/are TRUE?

• A. L_1 and L_2 are regular.

• B. L_1 and L_2 are context-free.

• C. L_1 is regular and L_2 is context-free.

• D. L_1 and L_2 are context-free but not regular.

Correct answers: A, B and C.

Choosing n=0 gives L_1={a,b}*. In L_2, |w|=1 shows it is exactly the length-at-least-three strings with matching endpoints: a(a|b)+a ∪ b(a|b)+b. For w=a,x=bba, this gives abbaa. Both are regular and therefore CFL, making A, B and C true.

Question 12: unary, doubled and shared counts

Consider the following languages: L_1 = {a^p | p is a prime number}, L_2 = {a^n b^m c^(2m) | n ≥ 0, m ≥ 0}, L_3 = {a^n b^n c^(2n) | n ≥ 0} and L_4 = {a^n b^n | n ≥ 1}. Which of the following are CORRECT? I. L_1 is context free but not regular; II. L_2 is not context free; III. L_3 is not context free but recursive; IV. L_4 is deterministic context free.

• A. I, II and IV only

• B. II and III only

• C. I and IV only

• D. III and IV only

Correct answer: D. III and IV only.

Every unary CFL is regular, so prime-length L_1 is not CFL. For L_2, ignore a^n, push twice per b, then pop per c. L_3 shares one count across three blocks: not CFL but recursive. L_4 has a deterministic push-then-pop PDA. Thus III and IV hold.

The trap map after scoring

Revisit reversal versus copying in Q3, the summed count that stays context-free in Q4 against the reused count that does not in Q5, the k=n+m reduction in Q6, the finite exception in Q8, the intersection in Q9, and linear versus multiplicative constraints in Q10. An example can refute a classification, never prove one. For more practice, use Context-Free Grammar MCQs: 11 Solved GATE Questions.

Short version and the next practice step

Simplify parameters, map dependencies to stack order, and name every closure operand. Retry missed questions before viewing options. Continue with GATE Guidance by Sanchit Sir or NTA-UGC-NET Paper - 2, then classify all 12 again.