Closure properties of regular languages

1. Which grammar shapes generate exactly the regular languages?
   Stuck? Peek at 2.3.2 Right-linear and left-linear grammars

   • Right-linear: A → wB | w. Left-linear: A → Bw | w. Regular grammar = one of the two (not mixed).
   • DFA → grammar: δ(A,a)=B ⇒ A → aB; A accepting ⇒ A → ε.
   • Grammar → NFA: A → aB is an arrow; A → a goes to a new accepting state.
   • Mixed linear can give aⁿbⁿ. Non-regular grammar does not imply non-regular language.

   Read lesson 2.3.2

2. Product construction: accepting set for L₁ − L₂?
   Stuck? Peek at 1.1.4 Product construction and complement

   • Product: states Q₁×Q₂, δ((p,q),a) = (δ₁(p,a), δ₂(q,a)), start (s₁,s₂).
   • ∩: F₁×F₂. ∪: F₁×Q₂ ∪ Q₁×F₂. −: F₁×(Q₂−F₂). ≤ |Q₁|·|Q₂| states.
   • Complement: complete the DFA (add dead state), swap F ↔ Q−F; same state count.
   • Regular languages closed under ∪, ∩, −, complement.

   Read lesson 1.1.4

3. Thompson: how is r* built?
   Stuck? Peek at 2.2.1 Regex → ε-NFA (Thompson construction)

   • Invariant: one start (no in-moves), one accept (no out-moves).
   • ∅, ε, a: 2 states. r+s: +2 states, 4 ε. rs: ε from accept(r) to start(s). r*: +2 states, 4 ε (enter, skip, loop back, exit).
   • States ≤ 2 × (symbols + operators). Regex → ε-NFA → DFA proves regex ⇒ regular.

   Read lesson 2.2.1

You know L₁ is regular and L₂ is regular. Is “strings in L₁ that are not in L₂, reversed” regular? Instead of designing a DFA each time, mathematicians proved once and for all which operations keep a language regular. In GATE, closure questions are free marks — if you know the table and the classic traps.

Each of L₁ = {aⁿbⁿ} and its complement are not regular. Can the union of two non-regular languages be regular?

Prediction check

Yes. {aⁿbⁿ} ∪ complement({aⁿbⁿ}) = Σ*, which is regular. Closure only promises: regular in ⇒ regular out. It says nothing when inputs are non-regular.

Closed: the full list

Homomorphism

Example: h(a) = 01, h(b) = ε. h(a*b) = (01)*. For L = (01)*, h⁻¹(L) = {w : h(w) ∈ (01)*} = all strings over {a, b} (every h(w) is (01)ᵏ).

Quotient and prefix

Example: L₁ = a*b, L₂ = b ⇒ L₁/L₂ = a*. If L₁ is regular, L₁/L₂ is regular for any L₂, even a non-regular one.

NOT guaranteed (classic traps)

• Infinite union: each {aⁿbⁿ} for a single n is finite (regular), but their union over all n is not regular.
• Subset: {aⁿbⁿ} ⊆ Σ*, yet Σ* is regular and the subset is not. A subset of a regular language need not be regular.
• Superset: similarly no guarantee.
• Infinite intersection: no guarantee.

Using closure to prove NON-regularity

If L were regular, then L ∩ R (R regular) would be regular. So if L ∩ R is known non-regular, L is non-regular. Example: L = { w : |w|ₐ = |w|_b }. L ∩ a*b* = { aⁿbⁿ } — not regular — so L is not regular.

Putting it together

• Regular languages are closed under every finite operation in the syllabus, including reversal, (inverse) homomorphism and quotient.
• No guarantee for infinite unions or subsets.
• Intersect with a regular “shape” to expose a non-regular core.

reversal of a DFA for "starts with ab"
 original:  →q0 —a→ q1 —b→ (q2) ⟲a,b
 reversed:  new start s —ε→ q2 ⟲a,b —b→ q1 —a→ (q0)       language: ends with ba ✓

closure cheat-grid for regular languages
 ∪ ∩ − ¬ · * ⁺ ᴿ  h  h⁻¹  /  prefix  suffix  substitution     ✔ all closed
 infinite ∪, infinite ∩, ⊆ (subset), ⊇ (superset)            ✘ no guarantee

Closure tells us when new languages stay regular. Next: what we can compute about a regular language given its DFA — is it empty? finite? equal to another one? Every one of these questions has an algorithm.

1. MSQ

   Regular languages are closed under:

   1. reversal
   2. inverse homomorphism
   3. infinite union
   4. quotient with an arbitrary language
2. MCQ

   L ∩ a*b* = {aⁿbⁿ}. What follows?

   1. L is regular
   2. L is not regular
   3. a*b* is not regular
   4. nothing
3. MCQ

   h(a) = 0, h(b) = 0. h({ aⁿbⁿ : n ≥ 0 }) is:

   1. {0ⁿ1ⁿ}
   2. (00)*
   3. 0*
   4. not regular
4. NAT

   L = a*b. How many strings of length 3 are in Prefix(L)?

   Write your answer before opening the key.

5. MCQ

   Which is NOT guaranteed to be regular when L is regular?

   1. Lᴿ
   2. L*
   3. a subset of L
   4. Σ* − L

• homomorphism h(L)
• inverse homomorphism h⁻¹(L)
• right quotient L₁/L₂
• Prefix(L), Suffix(L)
• substitution
• closure-based non-regularity argument

1. Is a subset of a regular language regular?
   Reveal answer

   Not necessarily ({aⁿbⁿ} ⊆ Σ*).
2. Regular L₁, arbitrary L₂: is L₁/L₂ regular?
   Reveal answer

   Yes, always.
3. Closed under infinite union?
   Reveal answer

   No.
4. How do you reverse a DFA?
   Reveal answer

   Reverse arrows, new start with ε to old accepting states, old start becomes accepting.

• To show L non-regular fast: intersect with a regular “shape” like a*b* to expose aⁿbⁿ.