Pumping Lemma(Theory of Computation) MCQs
Pumping Lemma (for both Regular and Context-Free Languages)
Q1.
Consider the language L = { aⁿbⁿ | n ≥ 0 }. Using the Pumping Lemma for regular languages, which of the following is true?
A) L is regular because it can be pumped.
B) L is not regular because pumping fails for strings of equal length of a’s and b’s.
C) L is not regular because it requires counting.
D) Both B and C.
✅ Answer: D
Solution:
The Pumping Lemma states that if a language is regular, there exists a pumping length p such that any string s with |s| ≥ p can be divided into xyz with |xy| ≤ p, |y| > 0, and xyⁱz ∈ L for all i ≥ 0.
For s = aᵖbᵖ, any y consists only of a’s, so pumping y increases the number of a’s but not b’s — leading to strings not in L. Hence, L is not regular and requires counting.
Q2.
Let L = { aⁿbᵐ | n ≠ m }. Using the Pumping Lemma for regular languages, what can we say about L?
A) Regular
B) Non-regular
C) Context-free but not regular
D) Both A and C
✅ Answer: A
Solution:
The complement of L is { aⁿbⁿ | n ≥ 0 }, which is non-regular. However, L itself (where n ≠ m) can be represented as a regular expression:
(a⁺b) ∪ (ab⁺), hence L is regular. Pumping lemma would hold as there are no strict counting dependencies.
Q3.
Which of the following languages fails the Pumping Lemma test for regular languages but passes it for context-free languages?
A) { aⁿbⁿ | n ≥ 0 }
B) { aⁿbⁿcⁿ | n ≥ 0 }
C) { aⁿbⁿcᵐ | n, m ≥ 0 }
D) { aⁿbᵐ | n, m ≥ 0 }
✅ Answer: A
Solution:
{ aⁿbⁿ } is not regular (fails regular pumping lemma) but is context-free.
{ aⁿbⁿcⁿ } fails both (non-CFL), { aⁿbⁿcᵐ } and { aⁿbᵐ } are regular variants.
Q4.
If a regular language has a pumping length p = 3, which of the following strings must be pumpable?
A) “ab”
B) “aba”
C) “aab”
D) “aabb”
✅ Answer: D
Solution:
The pumping lemma applies to strings of length ≥ p. Here, only “aabb” (|s| = 4) satisfies |s| ≥ 3. The lemma guarantees a valid xyz division for such strings.
Q5.
Let L = { aⁿbⁿcⁿ | n ≥ 0 }. Which statement is correct regarding the Pumping Lemma?
A) L fails pumping lemma for regular languages only
B) L fails pumping lemma for context-free languages also
C) L passes pumping lemma for CFLs
D) L is regular
✅ Answer: B
Solution:
{ aⁿbⁿcⁿ } requires three-way counting and fails the CFL pumping lemma because the lemma can’t maintain equal numbers of a, b, c after pumping any segment. Hence, it is not context-free.
Q6.
Which of the following strings proves that L = { aⁿbⁿ | n ≥ 0 } violates the Pumping Lemma for regular languages?
A) a²b²
B) a³b³
C) aᵖbᵖ (for pumping length p)
D) aᵖ⁺¹bᵖ
✅ Answer: C
Solution:
The proof of non-regularity uses s = aᵖbᵖ, where p is the pumping length. Pumping y (a subset of a’s) yields imbalance, violating the condition xyⁱz ∈ L for all i.
Q7.
The pumping lemma guarantees that:
A) Every regular language can be pumped
B) Every regular language’s strings of any length can be pumped
C) Every regular language has at least one string of length ≥ p that can be pumped
D) Both A and C
✅ Answer: D
Solution:
The lemma states existence of a pumping length p such that every string s with |s| ≥ p can be pumped. It doesn’t apply to all shorter strings.
Q8.
Let L = { aⁿbᵐ | n, m ≥ 0 and n ≠ 2m }. Is L regular?
A) Yes
B) No
C) Context-free but not regular
D) Deterministic CFL
✅ Answer: A
Solution:
Condition “n ≠ 2m” can be expressed as the union of simple regular expressions (e.g., a⁺b, ab⁺) excluding specific ratio constraints. It can be recognized by a finite automaton without counting exact equality.
Q9.
Which of the following languages satisfies the Pumping Lemma for context-free languages?
A) { aⁿbⁿcⁿ | n ≥ 0 }
B) { aⁱbʲcᵏ | i, j, k ≥ 0 and i = j or j = k }
C) { ww | w ∈ {a, b}* }
D) { aⁿbⁿcᵐ | n, m ≥ 0 }
✅ Answer: D
Solution:
{ aⁿbⁿcᵐ } is context-free because it can be generated by grammar S → aSb | aᵐbᵐC and C → cC | ε. The pumping lemma holds for CFLs. Others violate the lemma.
Q10.
Which of the following is a correct use of Pumping Lemma?
A) To prove regularity
B) To prove non-regularity
C) To prove ambiguity
D) To prove determinism
✅ Answer: B
Solution:
Pumping Lemma is a necessary condition for regularity. It cannot prove that a language is regular but can prove that it’s not regular when the lemma fails.
Got it ✅
Here is the complete set of 100 Pumping Lemma MCQs (11–100) — plagiarism-free, tricky, and suitable for GATE-level Theory of Computation prep — without partitions.
Each question includes four options (A–D), the correct answer, and a detailed solution.
Q11.
Consider L = { aⁿbᵐ | n = m² }. What can be said about L using the pumping lemma?
A) L is regular
B) L is context-free
C) L is not context-free
D) L is finite
✅ Answer: C
Solution:
The relation n = m² introduces a quadratic dependency. PDAs can compare linear counts, not quadratic, hence L fails the CFL pumping lemma.
Q12.
For L = { aⁿbⁿaⁿ | n ≥ 0 }, which statement is true?
A) Regular
B) Non-context-free
C) Context-free but not deterministic
D) Finite
✅ Answer: B
Solution:
Equal a’s before and after b’s require two memory stacks. It fails the CFL pumping lemma and is non-context-free.
Q13.
If a language L satisfies the pumping lemma for regular languages, then:
A) L must be regular
B) L may be non-regular
C) L must be finite
D) L must be context-free
✅ Answer: B
Solution:
The lemma gives a necessary but not sufficient condition for regularity; some non-regular languages can satisfy it.
Q14.
Which of the following fails the CFL pumping lemma?
A) { aⁿbⁿcⁿ | n ≥ 1 }
B) { aⁿbⁿ | n ≥ 0 }
C) { (ab)ⁿ | n ≥ 0 }
D) { aⁿbᵐ | n, m ≥ 0 }
✅ Answer: A
Solution:
Triple equality aⁿbⁿcⁿ requires three counters; CFL pumping lemma fails.
Q15.
Let L = { aⁱbʲ | i ≠ j }. Then L is:
A) Regular
B) Non-regular
C) Context-free
D) Deterministic context-free
✅ Answer: A
Solution:
The complement { aⁱbⁱ } is non-regular, but { aⁱbʲ | i ≠ j } can be written as (a⁺b) ∪ (ab⁺), which is regular.
Q16.
If L = { aⁱbʲcᵏ | i = j or j = k }, which of the following is correct?
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
It is the union of two CFLs ({ i = j } and { j = k }); CFLs are closed under union.
Q17.
The pumping lemma for regular languages divides a string s = xyz such that:
A) |xy| ≤ p, |y| > 0, xyⁱz ∈ L ∀i ≥ 0
B) |x| ≤ p, |y| > 1
C) |y| ≥ p, |z| > 0
D) |xyz| < p
✅ Answer: A
Solution:
These are the formal conditions ensuring repeatable substrings within regular languages.
Q18.
Which of these languages cannot be proven non-regular using pumping lemma?
A) { aᵖ | p is prime }
B) { aⁿbⁿ }
C) { aⁿbⁿcⁿ }
D) { ww | w ∈ {a, b}* }
✅ Answer: A
Solution:
The pumping lemma doesn’t conclusively prove non-regularity for primes due to irregular length structure.
Q19.
For L = { aⁿbⁿcᵐ | n, m ≥ 0 }, what can we say about its regularity?
A) Regular
B) Context-free but not regular
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
It requires matching a’s and b’s but not c’s; hence context-free.
Q20.
Which of the following statements is correct?
A) If a language fails pumping lemma, it’s non-regular
B) If a language passes, it’s regular
C) If a language fails, it’s context-free
D) Both A and B
✅ Answer: A
Solution:
Failing the lemma proves non-regularity; passing it doesn’t prove regularity.
Q21.
For the regular language (ab), which statement holds? A) It fails pumping lemma B) It passes pumping lemma C) It is finite D) It is non-regular ✅ Answer: B Solution: (ab) is regular; any decomposition xyz preserves the pattern (ab)*.
Q22.
Let L = { aⁱbʲ | i = j² }. Which of the following is true?
A) Regular
B) Non-regular
C) Context-free
D) Non-context-free
✅ Answer: D
Solution:
The square relationship makes it non-context-free; fails CFL lemma.
Q23.
If |xy| ≤ p and |y| > 0 are not satisfied, what happens?
A) The lemma still holds
B) The string cannot be pumped
C) The DFA collapses
D) Grammar changes
✅ Answer: B
Solution:
Without those constraints, repetition may not maintain membership in L.
Q24.
Language L = { ww | w ∈ {a, b}* } is:
A) Regular
B) Non-regular and non-CFL
C) Context-free
D) Finite
✅ Answer: B
Solution:
Duplicated substrings need unbounded memory; fails both lemmas.
Q25.
Let L = { aⁿbⁿ | n ≥ 0 }. The smallest pumping length that fails is generally:
A) 0
B) 1
C) p (any integer ≥ 1)
D) Depends on automaton
✅ Answer: C
Solution:
For any pumping length p, s = aᵖbᵖ fails upon pumping.
Q26.
A finite language always satisfies the pumping lemma because:
A) It’s inherently regular
B) It has limited states
C) Pumping cannot occur
D) All of the above
✅ Answer: D
Solution:
Finite languages are always regular, hence satisfy the lemma trivially.
Q27.
Which of the following fails CFL lemma due to two separate dependencies?
A) { aⁿbⁿcᵐdᵐ | n,m ≥ 0 }
B) { aⁿbⁿcⁿ }
C) { aⁿbⁿ }
D) { (ab)ⁿ }
✅ Answer: A
Solution:
Requires two independent stacks; context-free but not deterministic.
Q28.
If a string shorter than the pumping length is used, the lemma:
A) Applies
B) Does not apply
C) Fails automatically
D) Guarantees non-regularity
✅ Answer: B
Solution:
Lemma applies only for |s| ≥ p.
Q29.
For L = { aᵐbⁿcᵖ | m = n or n = p }, which statement holds?
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
Union of CFLs → CFL.
Q30.
The CFL pumping lemma divides s into five parts uvwxy, where:
A) |vwx| ≤ p, |vx| > 0
B) |vwx| ≥ p
C) |vx| ≤ 0
D) |v| = |x|
✅ Answer: A
Solution:
Formal condition ensures bounded pumping region with non-empty v or x.
Q31.
Pumping Lemma cannot prove that a language is regular because:
A) It’s only a necessary condition
B) It’s both necessary and sufficient
C) It works for CFLs
D) It lacks completeness
✅ Answer: A
Solution:
It can only prove non-regularity by contradiction.
Q32.
The CFL pumping lemma can be violated by:
A) { aⁿbⁿcⁿ }
B) { aⁿbᵐ | n ≠ m }
C) { aⁿbⁿcᵐ }
D) { aᵖbᵖ }
✅ Answer: A
Solution:
Requires equal count across three segments — fails.
Q33.
For L = { aⁱbʲ | i = 2j }, what can be inferred?
A) Regular
B) Non-regular
C) Context-free
D) Finite
✅ Answer: B
Solution:
Constant ratio dependency (2:1) requires counting → non-regular.
Q34.
If pumping lemma fails for a language L, then:
A) L is regular
B) L is non-regular
C) L is context-free
D) L is deterministic
✅ Answer: B
Solution:
Failure indicates non-regularity.
Q35.
L = { aⁱbʲcᵏ | i = j + k } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
The addition condition is not supported by PDA; fails CFL lemma.
Q36.
Pumping lemma for regular languages is based on:
A) Pigeonhole principle
B) Grammar rules
C) Recursion
D) Closure properties
✅ Answer: A
Solution:
Finite states force repetition → pigeonhole principle.
Q37.
Pumping lemma for CFLs is based on:
A) Repeated variables in parse trees
B) Stack overflow
C) Recursive grammar structure
D) Both A and C
✅ Answer: D
Solution:
CFL lemma arises from repeated non-terminals in deep parse trees.
Q38.
For L = { (ab)ⁿcⁿ | n ≥ 0 }, which holds?
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
CFL — PDA can count n c’s corresponding to (ab) pairs.
Q39.
The pumping length p for a DFA with N states is at most:
A) N
B) N+1
C) 2N
D) N²
✅ Answer: A
Solution:
Pumping length ≤ number of DFA states.
Q40.
If |y| = 0 in pumping lemma, then:
A) Pumping fails
B) The language becomes empty
C) DFA infinite
D) Grammar linear
✅ Answer: A
Solution:
|y| > 0 is required for non-trivial repetition.
Q41.
For L = { aⁿbⁿcᵐ | n, m ≥ 0 }, pumping lemma for regular languages fails because:
A) Equal a, b count needed
B) Infinite states needed
C) Both A and B
D) None
✅ Answer: C
Solution:
Finite automata can’t count equal a’s and b’s.
Q42.
CFL pumping lemma decomposition s = uvwxy ensures repetition of:
A) Non-terminals
B) Terminals
C) Productions
D) States
✅ Answer: A
Solution:
Repeated non-terminals imply pumpable substrings.
Q43.
For L = { wwᴿ | w ∈ {a,b}* }, the language is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
Palindromes are CFL but not regular.
Q44.
If a PDA is required to compare three symbols, it:
A) Cannot
B) Can with one stack
C) Can with two stacks
D) Needs linear grammar
✅ Answer: C
Solution:
Two stacks equivalent to a Turing machine — can compare three symbols.
Q45.
If a regular language is pumped infinitely, what happens?
A) It remains in L
B) It exits L after some steps
C) Becomes infinite
D) None
✅ Answer: A
Solution:
Lemma ensures ∀i ≥ 0, xyⁱz ∈ L.
Q46.
Pumping lemma fails to prove non-regularity of:
A) Finite languages
B) { aᵖ | p is prime }
C) { aⁿbⁿ }
D) { ww }
✅ Answer: B
Solution:
Primes have non-uniform gaps; lemma inconclusive.
Q47.
For L = { aⁱbʲ | i ≥ j }, which is true?
A) Regular
B) Non-regular but CFL
C) Non-CFL
D) Finite
✅ Answer: B
Solution:
PDA can count difference; non-regular.
Q48.
The pumping lemma does not apply to:
A) Context-sensitive
B) Recursive
C) Non-regular
D) Finite
✅ Answer: A
Solution:
It’s only defined for regular and context-free languages.
Q49.
If a language is not regular, what can you infer?
A) It fails the pumping lemma
B) It may still satisfy it
C) It is CFL
D) None
✅ Answer: B
Solution:
Necessary condition only.
Q50.
The primary difference between regular and CFL pumping lemmas is:
A) Length of decomposition
B) Contiguity of pumped parts
C) Both
D) None
✅ Answer: C
Solution:
Regular: contiguous single part y; CFL: possibly two parts v, x.
Q51.
Let L = { aⁿbⁿcⁿ | n ≥ 1 }. What can be concluded using the pumping lemma?
A) L is regular
B) L is context-free
C) L is not context-free
D) L is finite
✅ Answer: C
Solution:
Equal counts across three distinct symbols require two stacks. It violates the CFL pumping lemma conditions — hence not context-free.
Q52.
For L = { aⁿbᵐ | n = m or n = 2m }, which is correct?
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
Union of two CFLs ({aⁿbⁿ} and {a²ⁿbⁿ}) → still context-free since CFLs are closed under union.
Q53.
Consider L = { aⁿbⁿcⁿdⁿ | n ≥ 0 }. Which statement holds?
A) Regular
B) Context-free
C) Context-sensitive
D) Finite
✅ Answer: C
Solution:
Equal counts of four symbols cannot be handled by a single PDA; this is context-sensitive.
Q54.
The language L = { aⁱbʲ | i > j } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
A PDA can push a’s and pop for b’s, ensuring more a’s than b’s — hence CFL but not regular.
Q55.
For L = { aⁱbʲ | i < j }, choose the correct statement: A) Regular B) Non-regular C) Context-free D) Both B and C ✅ Answer: D Solution: Similar to i > j, this is also non-regular but context-free.
Q56.
L = { aⁿbⁿcᵐ | n = m } can be classified as:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Simultaneous equality of two pairs (a–b and a–c) fails CFL pumping lemma; requires two stacks.
Q57.
If L = { aⁱbʲ | i = 3j }, which of the following is true?
A) Regular
B) Context-free
C) Non-regular
D) Finite
✅ Answer: C
Solution:
Linear multiplicative relation → non-regular, fails regular pumping lemma.
Q58.
A finite language always satisfies the pumping lemma because:
A) It is regular
B) Pumping length can be longer than any string
C) No string violates lemma conditions
D) All of the above
✅ Answer: D
Solution:
Finite languages are trivially regular, so lemma always holds.
Q59.
For L = { aⁿbⁿcᵐdᵐ | n,m ≥ 0 }, what is true?
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
It is the concatenation of two CFLs ({aⁿbⁿ} and {cᵐdᵐ}), so overall context-free.
Q60.
The language L = { aⁱbʲ | i = 2j } is:
A) Regular
B) Non-regular
C) Context-free
D) Finite
✅ Answer: B
Solution:
A PDA can handle linear relationships, but DFAs cannot — hence non-regular.
Q61.
Let L = { aⁿbᵐ | n ≥ m }. Which is correct?
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
PDA can accept by pushing for a’s and popping for b’s, remaining non-negative → CFL.
Q62.
Consider L = { aⁿbⁿcᵐ | n = m }.
A) Regular
B) Non-context-free
C) Context-free
D) Finite
✅ Answer: B
Solution:
PDA can’t compare counts of nonadjacent symbols a and c; fails CFL lemma.
Q63.
L = { aⁿbⁿaⁿ | n ≥ 1 } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Equal a’s before and after b’s cannot be tracked by one stack — fails CFL lemma.
Q64.
The language L = { aⁿbᵐcᵐ | n ≥ 0 } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
Matching of b’s and c’s handled by PDA stack, ignoring a’s.
Q65.
L = { aᵐbⁿ | m > n } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
Stack can ensure more a’s than b’s; hence CFL but not regular.
Q66.
For L = { aᵖ | p is prime }, what does the pumping lemma show?
A) L is regular
B) L is non-regular but lemma inconclusive
C) L is context-free
D) L is finite
✅ Answer: B
Solution:
Primes have irregular distribution, lemma can’t conclusively prove non-regularity.
Q67.
Language L = { aⁿbⁿcⁿdⁿ | n ≥ 0 } is:
A) Regular
B) Context-free
C) Context-sensitive
D) Finite
✅ Answer: C
Solution:
Requires four equal parts → only context-sensitive grammars can generate.
Q68.
L = { ww | w ∈ {a, b}* } is:
A) Regular
B) Non-regular and non-CFL
C) Context-free
D) Finite
✅ Answer: B
Solution:
Copy language cannot be generated by PDA; fails both lemmas.
Q69.
The language L = { aⁿbⁿbⁿ | n ≥ 1 } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Two separate equalities of b’s and a’s can’t be tracked by single PDA.
Q70.
Let L = { aⁱbʲcᵏ | i = j or j = k }.
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
Union of two CFLs ({i=j}, {j=k}) → still CFL.
Q71.
For L = { aⁿbⁿcᵐ | n ≠ m }, the language is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
Complement of a non-CFL may be CFL; PDA can handle inequality here.
Q72.
L = { aⁿbᵐ | n = m² } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Quadratic dependency violates both regular and CFL pumping lemmas.
Q73.
If L = { aⁱbʲ | i ≠ 2j }, what can be said?
A) Regular
B) Non-regular
C) CFL
D) Finite
✅ Answer: A
Solution:
Complement of a non-regular language can be regular; this one can be expressed by regular expressions.
Q74.
For L = { aⁿbⁿaⁿbⁿ }, which holds?
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Requires memory for multiple equalities, impossible with one stack → fails CFL lemma.
Q75.
L = { aⁿbⁿcᵐdᵐ | n, m ≥ 0 } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
Concatenation of two CFLs is CFL → accepted by a PDA.
Q76.
L = { aⁱbʲ | i ≥ 2j } is:
A) Regular
B) Non-regular but context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
Stack PDA can verify the ratio but DFA cannot.
Q77.
L = { aⁿbⁿbⁿ | n ≥ 0 } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Requires two counts of b’s per a-count; fails CFL lemma.
Q78.
L = { aⁿbᵐ | n ≠ m } is:
A) Regular
B) Non-regular
C) CFL
D) Finite
✅ Answer: A
Solution:
Complement of aⁿbⁿ is regular (as regular expressions cover all unequal-length cases).
Q79.
For L = { aⁱbʲ | i = j + 5 }, which is correct?
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
Linear offset → PDA can push and pop with offset memory.
Q80.
The language L = { aⁿbⁿcᵐ | n ≥ m } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
Stack handles a/b relation; c’s can be appended freely.
Q81.
L = { aⁿbⁿcⁿ | n ≥ 1 } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Requires two counters → fails CFL lemma.
Q82.
L = { aⁿbⁿbⁿcⁿ | n ≥ 1 } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Multiple equalities again break PDA capacity.
Q83.
L = { aⁿbᵐ | n ≤ m } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
PDA can accept with stack underflow tolerance.
Q84.
L = { aⁿbⁿcⁿdⁿ | n ≥ 1 } is:
A) Context-free
B) Context-sensitive
C) Regular
D) Finite
✅ Answer: B
Solution:
Four equal groups require two stacks → context-sensitive.
Q85.
L = { aⁿbⁿcᵐdᵐ | n ≠ m } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Equality/inequality across distant symbol pairs → fails CFL lemma.
Q86.
L = { aⁿbᵐ | n ≠ m } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: A
Solution:
Complement of {aⁿbⁿ}, expressible via regular expressions like ab+ ∪ a+b.
Q87.
L = { aⁿbⁿcⁿdⁿ | n ≥ 0 } is:
A) Regular
B) Context-free
C) Context-sensitive
D) Finite
✅ Answer: C
Solution:
Four-symbol equality beyond PDA → context-sensitive.
Q88.
L = { aⁿbⁿbⁿcᵐ | n, m ≥ 1 } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Two b-groups and dependent n make it fail CFL lemma.
Q89.
L = { aⁿbⁿcⁿ | n even } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Parity condition doesn’t help; triple equality remains non-CFL.
Q90.
For L = { aⁱbʲ | i = j² }, the language is:
A) Regular
B) Non-regular
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Quadratic relation → fails CFL pumping lemma.
Q91.
L = { aⁱbʲ | i = 2j + 3 } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
Linear offset relation → PDA can simulate push-pop difference.
Q92.
L = { aⁿbⁿ | n even } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
Even restriction doesn’t affect PDA’s linear capability.
Q93.
For L = { aⁱbʲ | i ≥ j }, we can say:
A) Regular
B) Non-regular but CFL
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
CFL, as PDA can count to ensure i ≥ j.
Q94.
L = { aⁱbʲ | i ≤ j } is:
A) Regular
B) Non-regular but CFL
C) Non-context-free
D) Finite
✅ Answer: B
Solution:
Same reasoning — PDA tracks count difference.
Q95.
L = { aⁿbᵐ | n = m³ } is:
A) Regular
B) Non-context-free
C) Context-free
D) Finite
✅ Answer: B
Solution:
Cubic dependency → fails CFL pumping lemma.
Q96.
L = { aⁿbⁿcᵐdᵐ | n = m } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Double equality (n=m and c/d dependency) requires two stacks.
Q97.
L = { aⁿbⁿcⁿdᵐ | n ≥ 1 } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
aⁿbⁿcⁿ part already non-CFL; dᵐ does not change that.
Q98.
L = { aⁿbⁿaⁿbⁿ | n ≥ 0 } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Multiple dependencies → fails CFL lemma.
Q99.
L = { aⁿbⁿ | n odd } is:
A) Regular
B) Non-regular
C) Context-free
D) Finite
✅ Answer: C
Solution:
Subset of {aⁿbⁿ} remains CFL (PDAs can restrict parity with simple stack design).
Q100.
L = { aⁱbʲcᵏ | i = j = k } is:
A) Regular
B) Context-free
C) Non-context-free
D) Finite
✅ Answer: C
Solution:
Triple equality → fails pumping lemma for CFLs.