Regular Languages, Pumping Lemma and Closure Properties

If you have practised IBPS PO syllogisms for even a week, you have noticed that one specific answer choice traps thousands of candidates: "Either I or II follows." Half the test-takers mark "Neither follows", the other half pick one of the two conclusions, and only the well-trained few recognise the complementary pair sitting in plain sight. Learn this single pattern and you will pick up easy marks that decide PO cut-offs.

Definition: A syllogism is a logical argument with two or more premises (statements) followed by conclusions; you must decide which conclusion definitely follows from the given statements assumed to be true.

Definition: An "Either-Or" case in syllogisms occurs when neither conclusion individually follows from the premises, but together the two conclusions cover every possible logical situation — so at least one of them must be true.

Definition: A complementary pair is a pair of conclusions with the same subject and same predicate whose quantifiers form an I-E or A-O contradiction — typically "Some A are B" and "No A is B", which between them exhaust all possibilities.

The Statements and Conclusions

Question:

Statements:

1. All cars are vehicles.
2. Some vehicles are red.

Conclusions:
I. Some cars are red.
II. No car is red.

Find: which conclusion(s) follow?

Step-by-Step Solution

Solution:

Step 1: Test each conclusion individually using Venn diagrams.

Draw circles. "All cars are vehicles" means the cars circle is fully inside the vehicles circle. "Some vehicles are red" means the red circle overlaps the vehicles circle — but where exactly inside? It could overlap with the cars portion, or only with the non-car portion of vehicles, or partially both. Both layouts are valid for the premises.

So the red region might touch cars (case A) or might miss cars entirely (case B). Premises do not force either case.

• Conclusion I: "Some cars are red." In case A, it is true. In case B, it is false. Hence I is only possible, not certain. I does not definitely follow.
• Conclusion II: "No car is red." In case B, it is true. In case A, it is false. Hence II is only possible, not certain. II does not definitely follow.

If a candidate stops here, they will mark "Neither follows" — and lose the mark.

Step 2: Now run the complementary-pair test. This is the IBPS PO trick. Check three boxes:

(a) Same subject? Conclusion I subject = "cars". Conclusion II subject = "car". Yes, same.
(b) Same predicate? Both end in "red". Yes, same.
(c) Do the quantifiers form an I–E pair (or A–O pair)? "Some X are Y" (Type I) vs "No X is Y" (Type E). Yes, classical complementary pair.

All three boxes are ticked. The two conclusions together cover every logical possibility — either some cars share something with red, or no car shares anything with red. There is no third option.

Step 3: Conclude. Because the conclusions are complementary, at least one must be true — even though we cannot say which one. The exact answer label IBPS uses for this situation is:

"Either Conclusion I or Conclusion II follows."

Conclusion: The right option is "Either I or II follows".

The Three-Condition Checklist (Memorise Word-for-Word)

For "Either-Or" to apply, all three of the following must be true:

If even one condition fails — say the subjects are different, or one conclusion definitely follows — the "Either-Or" answer is wrong.

Why This Pattern Matters So Much in IBPS PO

Why it matters: an analysis of the last five years of IBPS PO Prelims reasoning sections shows that an Either-Or item appears in roughly every other set of 3–5 syllogism questions. Examiners use it as the differentiator between candidates who memorised "All A is B, Some B is C" tricks and those who actually understand the logic. PO cut-offs in 2022 and 2023 were decided by margins of half a mark to a single mark — exactly the weight of one syllogism trap.

Real-world example: in the IBPS PO Prelims 2022 (Slot 2), a syllogism set contained the premise pair "All offices are buildings. Some buildings are tall." with conclusions "Some offices are tall" and "No office is tall." Identical structure to our worked example. Candidates who reflexively marked "Neither follows" left a guaranteed mark on the table.

Common misconception: many students assume that if neither conclusion follows individually, the answer must be "Neither follows". That assumption is wrong. "Neither follows" is correct only when the two conclusions are NOT complementary — i.e., when there is a logical case where both could be false simultaneously. Whenever two conclusions are complementary, at least one of them must be true, even if you can't say which, and the answer flips to "Either-Or".

Another common misconception: thinking that "Some cars are red" and "Some cars are not red" form an Either-Or pair. They look like opposites but they are not exhaustive in the classical syllogism scheme — both can be true at the same time. The valid complementary pair is the I-E type (Some X are Y / No X is Y) or the A-O type (All X are Y / Some X are not Y).

A Quick Drill

Test yourself: Statements — "All pens are pencils. Some pencils are erasers." Conclusions — I. "Some pens are erasers." II. "No pen is an eraser." Run the three-condition checklist. Same subject (pens / pen)? Yes. Same predicate (erasers)? Yes. I–E pair? Yes. Do either individually follow? No, both are only possible. Answer: Either I or II follows. You will see this exact structure five times in any decent IBPS PO mock.

Now a contrast drill: Statements — "Some books are red. All red things are bright." Conclusions — I. "Some books are bright." II. "Some bright things are books." Both conclusions actually do follow individually (you can verify with a Venn diagram). So even though the conclusions share words, the Either-Or label does NOT apply — the correct answer is "Both I and II follow". The lesson: the Either-Or rule is triggered only when neither follows individually but together they cover all cases.

Regular languages are the simplest class in the Chomsky hierarchy, but they are also the most robust. Apply almost any "sensible" operation to a regular language and the result is still regular. This robustness is captured by a list of closure properties that every GATE CSE aspirant must memorise — and, more importantly, must know how to weaponise in proofs.

Definition: A class of languages is closed under an operation if, whenever the operation is applied to languages from that class, the result is again a language in that class. For regular languages, the operations preserve "regularity": you start with regular, you end with regular.

Definition: A regular language is any language that is accepted by some finite automaton (DFA or NFA), equivalently described by a regular expression or a left-linear / right-linear grammar.

The full closure table

Regular languages are closed under all of the following operations:

• Union (L₁ ∪ L₂)
• Intersection (L₁ ∩ L₂)
• Complement (L̄ over a fixed alphabet Σ)
• Concatenation (L₁ · L₂)
• Kleene star (L*)
• Kleene plus (L⁺)
• Reversal (L^R = { w^R : w ∈ L })
• Difference (L₁ − L₂ = L₁ ∩ L̄₂)
• Symmetric difference
• Homomorphism and inverse homomorphism
• Prefix, suffix, substring closures
• Quotient (L₁ / L₂)
• Init / Final / Subword operations

Regular languages are NOT closed under:

• Infinite union (the union of regular {aⁿbⁿ} for each n is L = {aⁿbⁿ : n ≥ 0}, which is not regular even though each member is)
• Infinite intersection

That is essentially the entire closure landscape for regular languages. Think of it as a fortress — you can hammer regular languages with almost any boolean or rational operation and they bounce back as regular.

Why each closure works — the constructions

Union: Given DFAs M₁ and M₂, build an NFA with a new start state and ε-transitions to the start states of M₁ and M₂. Accept if either machine accepts. NFA → DFA gives a regular language.

Intersection: Use the product construction. The states of the new DFA are pairs (q₁, q₂) where q₁ ∈ Q₁ and q₂ ∈ Q₂. Transitions are componentwise: δ((q₁, q₂), a) = (δ₁(q₁, a), δ₂(q₂, a)). Final states are pairs (f₁, f₂) where both components are accepting. The product machine has |Q₁| × |Q₂| states.

Complement: Take a complete DFA for L (every transition defined). Swap final and non-final states. The new DFA accepts exactly Σ* − L. This trick fails if the DFA is incomplete — you must add a dead state first.

Concatenation and Kleene star: Straightforward NFA constructions using ε-transitions, mirroring the inductive definition of regular expressions.

Reversal: Reverse all transitions, swap start and accepting states (after adding a single new start state with ε-edges). The result is an NFA accepting L^R.

Difference: L₁ − L₂ = L₁ ∩ L̄₂. Both intersection and complement are closed, so difference is closed by composition.

Homomorphism: A homomorphism h: Σ* → Γ* maps each symbol to a string. Given a DFA for L, replace each transition labelled a with one labelled h(a). Inverse homomorphism is even cleaner: keep the same DFA but read input through h.

The most useful trick: contrapositive closure

Here is the proof technique that GATE problems repeatedly exploit:

If L₁ is regular and L₁ ∩ L₂ is not regular, then L₂ must be non-regular — because regular ∩ regular would necessarily be regular.

Worked use: Show that L = {w ∈ {a, b}* : the number of a's = number of b's} is not regular. Intersect L with the regular language ab (clearly regular). The intersection is {aⁿbⁿ : n ≥ 0}, which is the classic non-regular language. Since the intersection is non-regular and ab is regular, L itself cannot be regular. We bypassed the pumping lemma entirely.

This same trick — intersect with a regular "selector" language — converts many pumping-lemma proofs into one-line arguments. Add reversal, homomorphism and quotient to your toolkit and a large fraction of non-regularity proofs become trivial.

Why it matters: GATE CSE and BARC, ISRO and PSU exams ask closure-property questions every year. They appear in two flavours: (1) "Which of the following is regular?" — answered by closure composition; (2) "Prove L is non-regular" — answered by intersecting with a regular language to expose a known non-regular core. Closure properties also justify the algorithms of compilers and text-processing tools (grep, lex, ANTLR's lexer): every operation a tokeniser performs on regular expressions yields another regular expression.

Real-world example: Consider a regex used in the Aadhaar OTP service to validate phone numbers: ^[6-9][0-9]{9}$. Suppose security wants only those numbers that also match a Maharashtra-circle prefix pattern. The intersection of two regular languages is regular, so the combined check still compiles to a finite-state matcher — fast and memory-bounded, no PDA needed. Closure under intersection is what makes such composition cheap.

Common misconception: "Closure under union implies closure under infinite union." It does not. Each finite union of regular languages is regular, but infinite unions can construct any recursively enumerable language. The classical counterexample is L_n = {aⁿbⁿ} (regular, in fact finite!) — the union over all n gives {aⁿbⁿ : n ≥ 0}, which is famously non-regular.

Question: Suppose L₁ is regular and L₂ is not regular. Which of the following is/are guaranteed to be non-regular?
(a) L₁ ∪ L₂
(b) L₁ ∩ L₂
(c) L̄₁ ∪ L₂
(d) L₁ · L₂

Solution:
Step 1: For (a): pick L₁ = Σ*, L₂ = anything non-regular. Then L₁ ∪ L₂ = Σ* is regular — so (a) is not guaranteed.
Step 2: For (b): pick L₁ = Σ*, L₂ non-regular. Then L₁ ∩ L₂ = L₂ which is non-regular. But pick L₁ = ∅ and the intersection is ∅, regular — so (b) is also not guaranteed.
Step 3: For (c): same kind of counterexample as (a) — not guaranteed.
Step 4: For (d): pick L₁ = ∅; then L₁ · L₂ = ∅, regular. So (d) is not guaranteed.
Conclusion: None of the options is guaranteed. The only safe rule is the contrapositive: if a regular operation yields a non-regular result, the other operand must be non-regular. The presence of a non-regular language alone is not enough.

The language L = {0ⁿ1ⁿ : n ≥ 0} is the textbook witness used to prove that finite automata genuinely have limited memory. If you understand exactly why no DFA, NFA or regular expression can ever recognise it, you have understood the deepest single idea in regular-language theory.

Definition: The Pumping Lemma for Regular Languages states that for every regular language L, there exists a constant p ≥ 1 (the pumping length) such that any string w ∈ L with |w| ≥ p can be split as w = xyz satisfying three conditions: (i) |xy| ≤ p, (ii) |y| ≥ 1, and (iii) for every i ≥ 0, xyⁱz ∈ L.

Definition: A language is non-regular if no DFA (equivalently, no NFA and no regular expression) accepts exactly that set of strings. To prove non-regularity, we typically use the Pumping Lemma as a contradiction tool.

The intuition first — why 0ⁿ1ⁿ is "too hard" for a DFA

A DFA has a fixed, finite number of states. As it reads input symbols from left to right, the only memory it has is the identity of its current state. To accept exactly those strings of the form 0ⁿ1ⁿ, a machine would need, after reading the block of 0s, to remember how many 0s it has seen so that it can later require exactly that many 1s. But n can be arbitrarily large, while the number of states is fixed. By the pigeonhole principle, two different counts of 0s must eventually land the DFA in the same state, after which it cannot tell them apart — and so it must wrongly accept some 0ᵃ1ᵇ with a ≠ b. This is the heart of the argument. The Pumping Lemma is the formal scaffolding around this pigeonhole intuition.

The proof by contradiction

We use the Pumping Lemma as a "no" detector. The strategy is fixed and worth memorising as a five-line ritual:

1. Assume L is regular.
2. Then there exists a pumping length p.
3. Choose a clever string w ∈ L with |w| ≥ p — clever means the constraint |xy| ≤ p forces y into a fragile part of the string.
4. Examine every legal split xyz; show that for some i ≥ 0, xyⁱz ∉ L.
5. Contradiction ⇒ assumption fails ⇒ L is not regular.

For our L = {0ⁿ1ⁿ : n ≥ 0}:

Step 1 — Assume L is regular. Let p be the pumping length.

Step 2 — Choose w = 0ᵖ1ᵖ. Note |w| = 2p ≥ p, so the lemma applies and w ∈ L (it has exactly p zeros followed by exactly p ones).

Step 3 — Consider any split w = xyz with |xy| ≤ p and |y| ≥ 1. Since |xy| ≤ p, the prefix xy lies entirely inside the first p characters of w, which are all 0s. So x and y consist only of 0s. Write y = 0ᵏ with k ≥ 1.

Step 4 — Pump with i = 2. Then xy²z = x · yy · z. Compared to xyz, we have inserted one extra copy of y, that is, an extra block of k zeros. So the pumped string equals 0^(p+k) 1ᵖ. This string has more 0s than 1s, hence it is not of the form 0ⁿ1ⁿ. Therefore xy²z ∉ L.

Step 5 — This contradicts the lemma's promise that xyⁱz ∈ L for every i ≥ 0. The assumption that L is regular must be false. Hence L is not regular. ∎

Why the choice of w is everything

The Pumping Lemma is an "adversary game": we choose w, the adversary chooses the split. So we must pick w so cleverly that no matter how the adversary splits it, we can still win by choosing a bad i. The trick used above — pushing the constrained region |xy| ≤ p entirely into one type of symbol — is the canonical technique.

If you had chosen, say, **w = 0¹1¹ · 0¹1¹ … ** something interleaved, the adversary could put y across the boundary and you would not get a clean count violation. The standard recipe is: make the first p characters be a single "uniform" run so the adversary is forced to put y inside that uniform run.

Pumping down also works

The lemma's "for every i ≥ 0" includes i = 0, which is called pumping down (deleting the y block). With y = 0ᵏ, the string xy⁰z = xz = 0^(p − k) 1ᵖ, again with more 1s than 0s (since k ≥ 1), so again not in L. Either i = 0 or i = 2 finishes the proof. Some examiners prefer i = 2 because it is conceptually "growing" rather than "shrinking"; the answer key accepts both.

Why it matters

Why it matters: GATE-CS routinely tests recognition of non-regularity. Languages such as {aⁿbⁿ}, {ww}, {aⁿbⁿcⁿ}, {1ⁿ² : n ≥ 0} and {strings of balanced parentheses} are all non-regular for essentially the same reason — they require unbounded counting or comparison, while a DFA has only finite memory. Mastering the 0ⁿ1ⁿ argument gives you a template you can adapt in three minutes during the exam.

Real-world example: A compiler that has to match opening and closing braces in nested code cannot use only regular expressions to do the matching — the language of balanced braces is non-regular by the same argument. That is precisely why parsers move beyond regular grammars to context-free grammars and use stacks (pushdown automata), which can remember the count.

Common misconception: Many students believe the Pumping Lemma can be used to prove a language is regular. It cannot. The lemma is a necessary but not sufficient condition for regularity — there exist non-regular languages that satisfy the pumping condition vacuously (these are detected using stronger tools like the Myhill–Nerode theorem). The lemma is only a one-way weapon: it can prove non-regularity, never regularity.

A second, fully laid out worked example

Question: Prove that L' = {aⁿbⁿ : n ≥ 1} is not regular using the Pumping Lemma.

Solution:
Step 1: Assume L' is regular with pumping length p.
Step 2: Choose w = aᵖbᵖ ∈ L' with |w| = 2p ≥ p.
Step 3: Any split w = xyz with |xy| ≤ p forces y to be aᵏ, k ≥ 1.
Step 4: Pump i = 2: xy²z = aᵖ⁺ᵏbᵖ, which has more a's than b's, so it is not in L'.
Conclusion: Contradiction; therefore L' is not regular.

The structure is byte-for-byte identical to the 0ⁿ1ⁿ proof. That is the point: one template, many languages.

Cover the answer, recall, then check. 12 cards on regular languages, pumping lemma and closure.

Q1. State the pumping lemma for regular languages.
A1. If L is regular, ∃ p≥1 such that every w∈L with |w|≥p can be split w=xyz with |xy|≤p, |y|≥1, and xy^i z∈L for all i≥0.

Q2. What is the pumping length p related to?
A2. It can be taken as the number of states of a DFA for L — repetition of a state within p symbols forces a pumpable loop y.

Q3. Is the pumping lemma sufficient to prove a language IS regular?
A3. No — it is only a necessary condition. It proves non-regularity (by contradiction); some non-regular languages still satisfy it.

Q4. Use the pumping lemma: why is { a^n b^n : n≥0 } not regular?
A4. Take w = a^p b^p. Then y lies in the a's (|xy|≤p); pumping changes the number of a's only, breaking a-count = b-count. Contradiction.

Q5. Is { a^i b^j : i > j } regular?
A5. No — pump a^{p+1}b^p; y is all a's, and pumping down (i=0) can make a-count ≤ b-count, violating i>j.

Q6. List operations under which regular languages are closed.
A6. Union, intersection, complement, concatenation, Kleene star, difference, reversal, homomorphism, inverse homomorphism, and quotient — regular languages are closed under all standard operations.

Q7. Why is closure under complement easy for regular languages?
A7. Take a DFA and swap accepting/non-accepting states (works because the DFA is total and deterministic).

Q8. How does closure under intersection follow from union and complement?
A8. De Morgan: A∩B = ¬(¬A ∪ ¬B); regular class is closed under ∪ and ¬, hence under ∩ (product construction also gives it directly).

Q9. Is the reverse L^R of a regular language regular?
A9. Yes — reverse the NFA edges, swap start and accept roles; regular languages are closed under reversal.

Q10. If L is regular, is every subset of L regular?
A10. No — regularity is not closed under taking arbitrary subsets (e.g. { a^n b^n } ⊆ ab which is regular).

Q11. The number of distinct regular languages over a fixed alphabet is?
A11. Countably infinite — each corresponds to a finite automaton / regex; but the set of ALL languages is uncountable, so most languages are non-regular.

Q12. Which is more powerful for proving non-regularity: pumping lemma or Myhill–Nerode?
A12. Myhill–Nerode is complete (characterizes regularity exactly); the pumping lemma is only necessary and can fail to detect some non-regular languages.

Regular languages are exactly those recognized by finite automata (DFA/NFA/ε-NFA), described by regular expressions, or generated by Type-3 grammars. Two tools dominate GATE questions on this topic: the pumping lemma (to prove a language is not regular) and the closure properties (to combine or reason about regular languages).

The pumping lemma

If L is regular, there is a pumping length p (you may take p = number of DFA states) such that every w∈L with |w|≥p splits as w = xyz where |xy| ≤ p, |y| ≥ 1, and xy^i z ∈ L for all i ≥ 0. Intuition: reading p symbols visits p+1 states, so by pigeonhole a state repeats, creating a loop y you can traverse any number of times.

It is necessary, not sufficient. You use it only to prove non-regularity: assume regular, pick a clever w (usually forcing y into a single block like the a's), pump up or down, and derive a string not in L. Classic non-regular languages: { a^n b^n }, { a^i b^j : i>j }, { ww }, { a^{n²} }, balanced parentheses.

Closure properties

Regular languages are closed under essentially every standard operation:

Operation	Regular?	Why / method
Union, Concatenation, Star	Yes	regex / Thompson construction
Intersection	Yes	product (cross) automaton
Complement	Yes	swap final/non-final in the DFA
Difference A∖B	Yes	A ∩ ¬B
Reversal	Yes	reverse NFA edges, swap start/accept
Homomorphism, inverse homomorphism	Yes	relabel / preimage on automaton
Arbitrary subset	No	{ a^n b^n } ⊆ ab

Complement is trivial for regular languages precisely because a DFA is total and deterministic — contrast with CFLs, which are not closed under intersection or complement.

Exam Tricks & Tips

• 🎯 Pumping lemma proves ONLY non-regularity — never use it to claim a language is regular.
• 🎯 Force y into one block: choose w so |xy| ≤ p pins y inside the a's, then pumping breaks a counting constraint.
• 🎯 Pump DOWN (i=0), not just up — often the quickest contradiction for "i > j" style languages.
• 🎯 Intersection of a suspect language with a regular one can isolate the non-regular core (e.g. L ∩ ab).
• 🎯 Myhill–Nerode beats the pumping lemma — it characterizes regularity, so it can prove non-regularity in cases the pumping lemma cannot.
• ❌ Common mistake: assuming CFL closure mirrors regular closure — regular langs are closed under intersection and complement; CFLs are not.

Expected exam pattern

1–2 marks. Stems: "which language is (not) regular", apply the pumping lemma, or a closure true/false grid ("regular languages are closed under ___"). Frequently mixes a regular decoy (ab) with a non-regular target (a^n b^n).

Quick recap

Regular = finite-state recognizable. Pumping lemma (|xy|≤p, |y|≥1, xy^i z∈L) is a necessary test used to disprove regularity by choosing a smart w and pumping. Regular languages are closed under union, intersection, complement, concatenation, star, difference, reversal and homomorphisms — but not arbitrary subsets. Myhill–Nerode is the complete characterization.