Noesis
4.6.6Theory of Computation

Regular languages — closed under union, intersection, complement, concatenation, Kleene star

2,149 words10 min readdifficulty · medium5 backlinks
🇮🇳 Yeh note Hinglish mein padho →

WHAT is closure (and WHY we care)

WHY care? Closure lets you prove a language is regular without designing a machine from scratch — you decompose it into known-regular pieces. It also powers proof-by-contradiction: if combining regular languages would give a known non-regular language, the original couldn't be regular.

The master tool: build a machine

Every proof has the same skeleton: assume DFAs/NFAs for the inputs exist, construct a new machine for the result. Two construction techniques do all the work:

  1. Product construction (run two DFAs in parallel) → union, intersection.
  2. Epsilon-glue construction (wire NFAs together with ε\varepsilon-transitions) → concatenation, star, and easy union.
Figure — Regular languages — closed under union, intersection, complement, concatenation, Kleene star

1. Complement — flip the accept states

Derivation (HOW): For any string ww, the DFA's run δ^(q0,w)\hat\delta(q_0,w) ends in a unique state ss.

  • w∈A  ⟺  s∈Fw\in A \iff s\in F.
  • In M‾\overline M, ww is accepted   ⟺  s∈Q∖F  ⟺  s∉F  ⟺  w∉A\iff s\in Q\setminus F \iff s\notin F \iff w\notin A. Hence L(M‾)=A‾L(\overline M)=\overline A. ∎

2. Intersection — product construction

Derivation (HOW): By induction on ∣w∣|w|, δ^((a0,b0),w)=(δ^A(a0,w),δ^B(b0,w))\hat\delta((a_0,b_0),w)=(\hat\delta_A(a_0,w),\hat\delta_B(b_0,w)). The pair is accepting   ⟺  \iff first coord ∈FA\in F_A and second ∈FB\in F_B   ⟺  w∈A\iff w\in A and w∈Bw\in B. ∎

3. Union — two clean ways

4. Concatenation — glue end-to-start

Why every accept state of MAM_A? Because the prefix xx could end at any of them; each is a valid place to "finish AA and begin BB."

5. Kleene star — loop back, accept empty

Worked examples

Recall Feynman: explain to a 12-year-old

Imagine each "machine" is a little robot reading a string letter by letter and saying YES or NO at the end. Complement: keep the same robot but swap its YES and NO buttons. AND / OR: glue two robots side by side and let them read the same letters together; a referee says YES if both (or either) are happy. Concatenation: robot A reads the first part, then secretly hands the rest to robot B — but it has to guess where to hand over. Star (repeat): when robot A finishes one copy, it teleports back to its start to read another copy, as many times as it likes (zero times = empty string is fine). Because we can always build a robot for the result, the result is still a "regular" thing.

Flashcards

What does "regular languages are closed under union" mean?
If A,BA,B are regular then A∪BA\cup B is regular (combining them keeps you inside the class).
Construction for intersection of two DFAs?
Product construction: states QA×QBQ_A\times Q_B, transition componentwise, accept = FA×FBF_A\times F_B.
Accept set for union via the product machine?
(FA×QB)∪(QA×FB)(F_A\times Q_B)\cup(Q_A\times F_B) — accept if at least one coordinate is final.
How to complement a regular language?
Take a DFA (determinize first if NFA), then swap accept and non-accept states: F→Q∖FF\to Q\setminus F.
Why can't you complement an NFA by just swapping accept states?
An NFA may have both accepting and non-accepting runs on one input; swapping breaks correctness. Must determinize first.
Construction for concatenation ABAB?
Add ε\varepsilon-transitions from every accept state of MAM_A to the start of MBM_B; new accepts = FBF_B.
Construction for Kleene star A∗A^*?
New start/accept state s0s_0 with ε→a0\varepsilon\to a_0; ε\varepsilon from each old accept back to a0a_0; accept = {s0}∪FA\{s_0\}\cup F_A.
Why a fresh start state for star instead of marking old start accepting?
Loop-back edges into a0a_0 could wrongly accept mid-words; a fresh s0s_0 cleanly handles only ε\varepsilon and restarts.
Derive union closure from complement+intersection.
A∪B=A‾∩B‾‾A\cup B=\overline{\overline A\cap\overline B} (De Morgan), so closure under complement+intersection gives union.
How is closure used to PROVE a language non-regular?
Intersect/complement with a regular language to reduce it to a known non-regular language (e.g. anbna^nb^n); contradiction via pumping lemma.
Why does the product DFA correctly track both machines?
Induction: δ^((a0,b0),w)=(δ^A(a0,w),δ^B(b0,w))\hat\delta((a_0,b_0),w)=(\hat\delta_A(a_0,w),\hat\delta_B(b_0,w)), so the pair mirrors both runs exactly.

Connections

Concept Map

accepted by

described by

keeps result

runs DFAs in parallel

runs DFAs in parallel

wires NFAs

loops back

new start

swap accept states

needs

proves regular via

proves regular via

Regular language

DFA or NFA

Regular expression

Closure property

Product construction

Epsilon-glue construction

Union

Intersection

Complement

Concatenation

Kleene star

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, regular language matlab koi bhi language jise ek finite automaton (DFA/NFA) ya regular expression accept kar sakta hai. Closure property ka sawaal simple hai: agar do regular languages ko union, intersection, complement, concatenation ya star se combine karein, to kya result bhi regular rahega? Jawab — haan, paanchon operations ke liye! Aur iska magic reason ek hi hai: har operation ke liye hum purani machines se nayi machine bana sakte hain. Machine ban gayi, to definition se hi language regular ho gayi.

Trick yaad rakho do hisson mein. AND/OR/NOT ke liye DFA approach: complement ke liye DFA ke accept aur non-accept states ko flip kar do (lekin pehle NFA ko DFA banao via subset construction, warna galat answer milega). Intersection/union ke liye product construction — dono DFA ko ek saath chalao, state ban jaati hai pair (p,q)(p,q); intersection mein dono final, union mein koi ek final. Concatenation aur star ke liye NFA ka epsilon-glue: concatenation mein A ke har accept state se B ke start tak ek ε\varepsilon taar jod do (machine khud guess karegi kahan se B shuru karna hai); star mein ek naya start-cum-accept state banao (jisse ε\varepsilon accept ho, yaani zero copies) aur har purane accept se wapas start par ε\varepsilon loop laga do.

Yeh kyun important hai? Kyunki ab kisi language ko regular prove karne ke liye scratch se machine banane ki zaroorat nahi — usko regular tukdon mein tod do, jaise a∗b∗a^*b^* ko concatenation se. Aur ulta bhi: agar combine karke koi non-regular language (jaise anbna^nb^n) ban jaaye, to original bhi regular nahi ho sakti — yeh proof-by-contradiction ka powerful weapon hai, pumping lemma ke saath. Mantra rakho: "Product for AND/OR, Flip for NOT, Epsilon-glue for join and loop."

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 2,014 wordsD2Visual walkthroughThe derivation in pictures · 2,000 wordsD3Worked examplesEvery scenario covered · 3,901 wordsD4ExercisesGraded, full solutions · 2,692 wordsD5Question bankConcept traps, quick reveals · 1,814 words

Test yourself — Theory of Computation

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

Finite automata — DFA - formal definition (5-tuple), state diagramsCoding · 4.6.2Regular expressions — re module, patterns, groups, findall, subCoding · 1.3.11Pumping lemma for regular languages — proof and using to show non-regularityCoding · 4.6.7De Morgan's theoremsHardware · 3.1.8Alphabet, string, language — formal definitionsCoding · 4.6.1NFA — formal definition, epsilon transitionsCoding · 4.6.3NFA to DFA conversion — subset constructionCoding · 4.6.4Regular expressions — equivalence with finite automataCoding · 4.6.5Pumping lemma for regular languages — proof and using to show non-regularityCoding · 4.6.7