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

Before anything: a DFA (deterministic finite automaton) is a robot that reads a string one symbol at a time, sits in exactly one state at each moment, and at the end says YES (accept) or NO (reject). An NFA (nondeterministic finite automaton) is the same robot but it may split into several guesses at once, and it says YES if any guess ends happy. We will lean on both. See Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA) if either word is fuzzy — this page assumes only that a machine reads symbols and says YES/NO.

We now clear every box. Alphabet is $\Sigma =\{0,1\}$ or $\{a,b\}$ as stated; $|w|$ means length of $w$, ${\#}_0(w)$ means "count of 0s in $w$."

---

The scenario matrix

Every closure problem lives in one of these boxes. The columns are what you must do; the rows are what the problem looks like.

#	Case class	What the problem hands you	Right tool	Example
C1	AND of two conditions	"words satisfying both X and Y"	Product Construction (intersection accept set)	(a)
C2	OR of two conditions	"words satisfying X or Y"	Product (union accept set) or $\epsilon$-NFA	(b)
C3	NOT a condition	"words that are not X"	Determinize then flip accept states	(c)
C4	Join / one-after-another	"an X-part followed by a Y-part"	$\epsilon$-glue concatenation	(d)
C5	Repeat any number of times	"zero or more copies of X"	$\epsilon$-glue Kleene star	(e)
C6	Degenerate / empty inputs	$\varnothing$, $\{\epsilon \}$, $A^0$, zero copies	check the $k=0$ / empty edge case	(f)
C7	Prove NON-regular via closure	"show L is not regular"	intersect with a regular set, hit Pumping Lemma for Regular Languages	(g)
C8	Real-world word problem	disguised as a story	translate to a language, then C1–C5	(h)
C9	Exam twist	complement of an intersection, De Morgan trap	De Morgan's Laws + right order of ops	(i)

---

(a) — Box C1: AND of two conditions

Forecast: guess now — how many states does the product machine have, and does $1011$ get accepted?

Steps.

1. Build the DFA for $A$. Two states: $E$ (seen an even count of 0s so far, start & accept) and $O$ (odd). Reading a $0$ flips $E\leftrightarrow O$; reading a $1$ stays put. Why this step? Parity of 0s only depends on how many 0s we've seen mod 2 — two states is all the memory you need.

2. Build the DFA for $B$. Two states: $N$ (last symbol was not 1 / nothing yet, start) and $Y$ (last symbol was 1, accept). Reading $1$ goes to $Y$; reading $0$ goes to $N$. Why this step? "Ends in 1" only cares about the very last symbol, so remember just that.

3. Form the product. States are pairs $(p,q)$ with $p\in \{E,O\}$, $q\in \{N,Y\}$ → $2\times 2=4$ states. Start $=(E,N)$. Transition runs both coordinates on the same input symbol. Accept set $=\{E\}\times \{Y\}=\{(E,Y)\}$. Why this step? Product Construction tracks both invariants at once inside one combined state, so nothing is lost. AND ⇒ accept only when both coordinates are happy.

4. Run $1011$. Track $(p,q)$ — this is exactly the trajectory drawn in Figure 1 below: start $(E,N)\stackrel{1}{\to }(E,Y)\stackrel{0}{\to }(O,N)\stackrel{1}{\to }(O,Y)\stackrel{1}{\to }(O,Y)$. End state $(O,Y)$ — first coordinate is $O$, not accept. Rejected. Why this step? $1011$ has one 0 (odd) so it fails $A$; the product correctly rejects.

In Figure 1, note the four combined states arranged as a grid: the horizontal axis is the parity coordinate ($E$/$O$) and the vertical axis is the last-symbol coordinate ($N$/$Y$). The single amber double-circle $(E,Y)$ at top-right is the only accept state — read a $1$ (cyan arrow) to move right along the last-symbol axis, read a $0$ (white arrow) to flip parity.

Verify: ${\#}_0(1011)=1$ (odd) so $1011\notin A$, hence $\notin A\cap B$ ✓. $001$: two 0s (even) ∈ $A$, ends in 1 ∈ $B$ → accepted. $\epsilon$: zero 0s is even (∈ $A$) but does not end in 1 → rejected. All three match the machine's verdicts.

---

(b) — Box C2: OR of two conditions

Forecast: a language defined by OR is usually huge — guess which few short strings are the only rejects.

Steps.

1. Build the DFA for $A$ ("$|w|\ge 2$"). Three states counting length capped at 2: $Q_A=\{a_0,a_1,a_2\}$, start $a_0$ (length 0), $a_0\to a_1$ (length 1) $\to a_2$ (length $\ge 2$, and $a_2$ self-loops on every symbol). Accept set $F_A=\{a_2\}$. Why this step? Length only needs to be tracked up to the threshold 2, then it saturates — three states suffice.

2. Build the DFA for $B$ ("contains an $a$"). Two states: $Q_B=\{b_0,b_1\}$, start $b_0$ (no $a$ yet), reading $a$ goes to $b_1$ (seen an $a$, self-loop forever), reading $b$ stays. Accept set $F_B=\{b_1\}$. Why this step? "Contains an $a$" is a one-way switch: once flipped, it never flips back — two states.

3. Form the product $Q_A\times Q_B$ ($3\times 2=6$ states) and use the union accept set $F_{\cup }=(F_A\times Q_B)\cup (Q_A\times F_B)=(\{a_2\}\times \{b_0,b_1\})\cup (\{a_0,a_1,a_2\}\times \{b_1\}).$ Now every $Q_A,F_A,Q_B,F_B$ is concrete (from steps 1–2). Why this step? A pair $(p,q)$ should accept when at least one coordinate is final — that is exactly "either machine is happy," which is OR.

4. Note the complement is easier to reason about: $\overline{A\cup B}=\overline{A}\cap \overline{B}$ by De Morgan's Laws. A string is rejected iff $|w|<2$ and $w$ has no $a$. In product terms that is a state with first coordinate $\in \{a_0,a_1\}$ and second $=b_0$ — none of which lie in $F_{\cup }$. Why this step? Rejects are rare, so describing the rejected set directly is faster than listing accepts.

5. Enumerate rejects: strings with length 0 or 1 and no $a$. Length 0: $\epsilon$. Length 1 with no $a$: $b$. That's it. Why this step? $|w|<2$ leaves only lengths 0 and 1; "no $a$" over $\{a,b\}$ forces every symbol to be $b$.

Verify: rejected set $=\{\epsilon ,b\}$, size $2$. Check $ab$: length 2 (∈$A$) → accepted ✓. Check $a$: length 1 (∉$A$) but contains $a$ (∈$B$) → accepted ✓. Check $b$: length 1, no $a$ → rejected ✓.

---

(c) — Box C3: NOT a condition (the NFA trap)

Forecast: if you swap accept states, do you get $\overline{A}$ — and does it matter whether you started from an NFA or a DFA?

Steps.

1. The natural machine is an NFA $N$ that guesses where the substring $ab$ begins. Concretely $N$ has states $\{n_0,n_1,n_2\}$: start $n_0$ self-loops on both $a$ and $b$ (waiting), $n_0\stackrel{a}{\to }{n}_1$ guesses "the $ab$ starts here," $n_1\stackrel{b}{\to }{n}_2$ confirms it, and $n_2$ (the only accept) self-loops on both symbols. It is nondeterministic because from $n_0$ on an $a$ there are two moves: stay at $n_0$ or jump to $n_1$. Why this step? We must actually see the NFA to understand why swapping its accepts is illegal.

2. Determinize $N$ by tracking the set of NFA states reachable so far. Start set $\{n_0\}$ =: $q_0$. On $a$: $\{n_0,n_1\}$ =: $q_1$ (stay + guess). On $b$ from $q_0$: $\{n_0\}=q_0$. From $q_1=\{n_0,n_1\}$ on $b$: $n_0\to n_0$, $n_1\to n_2$, giving $\{n_0,n_2\}$ =: $q_2$ (contains accept $n_2$). From $q_1$ on $a$: $\{n_0,n_1\}=q_1$. Once $q_2$ appears it self-loops (still contains $n_0$ and $n_2$). So the reachable subsets are exactly three: $q_0=\{n_0\}$, $q_1=\{n_0,n_1\}$, $q_2=\{n_0,n_2\}$, with $q_2$ the accept (any subset containing $n_2$). Why this step? Subset Construction (NFA to DFA) gives a DFA with "exactly one state per string," the guarantee that makes flipping valid; here the three surviving subsets become the three DFA states.

3. Flip: $\overline{A}$'s accept set $=\{q_0,q_1\}=Q\setminus \{q_2\}$ — accepting exactly the strings that never complete an $ab$. Why this step? In a total DFA, "not in $F$" is literally "not accepted by $A$" — that is the definition of complement.

4. Describe $\overline{A}$ in words: strings with no $ab$ substring = all $b$'s first then all $a$'s, i.e. matching $b^{\ast }{a}^{\ast }$. Why this step? Once an $a$ appears it must never be followed by $b$, forcing the $b^{\ast }{a}^{\ast }$ shape.

Figure 2 draws the determinized 3-state DFA. The amber double-circles $q_0,q_1$ are the accept states for $\overline{A}$ (after the flip); $q_2$ (cyan, the "saw $ab$" trap) is where $A$ accepts. Follow the cyan $a$ then $b$ arrows to reach $q_2$; the white self-loop labels remind you which symbol keeps you waiting.

Verify: $ba\in \overline{A}$? It matches $b^{\ast }{a}^{\ast }$ and contains no $ab$ ✓. $ab\in \overline{A}$? It contains $ab$ → in $A$, so not in $\overline{A}$ ✓. $\epsilon \in \overline{A}$? empty string has no $ab$ → in $\overline{A}$ ✓.

---

(d) — Box C4: Join / one-after-another

Forecast: where does the NFA hand control from the $a$-machine to the $b$-machine when reading $aabbb$?

Steps.

1. Write $L=\{a{\}}^{\ast }\cdot \{b{\}}^{\ast }$. Each factor is regular (single symbol under star). Why this step? Decomposing into known-regular pieces means Regular Expressions closure does the proof — no machine drawn from scratch.

2. Build NFA $M_A$ for $\{a{\}}^{\ast }$ (a single state looping on $a$, both start and accept) and $M_B$ for $\{b{\}}^{\ast }$ (a single state looping on $b$). Glue: add an $\epsilon$-transition from every accept state of $M_A$ to the start of $M_B$; new start $=$ start of $M_A$; new accepts $=$ accepts of $M_B$. Why this step? A word $xy\in AB$ splits into an $A$-prefix and a $B$-suffix but we don't know where — the $\epsilon$-jump lets the NFA guess the split point.

3. Trace $aabbb$. Stay in $M_A$ reading $a,a$; take the $\epsilon$-jump into $M_B$ (guessing the split is here); read $b,b,b$ in $M_B$; end in an accept state. Why this step? The correct split is "after the 2 $a$'s" — the NFA's guess lands exactly there and accepts.

Verify: $aabbb\in L$ since it is $a^2{b}^3$ with $n=2,m=3\ge 0$ ✓. $ba\in L$? It's $b$ then $a$ — no way to write as $a^n{b}^m$ (an $a$ after a $b$) → rejected. In the glued NFA there is no path reading $b$ before entering $M_B$ from $M_A$ without already having left $M_A$; so $ba$ is rejected ✓.

---

(e) — Box C5: Repeat any number of times

Forecast: which of those four strings are in $(ab{)}^{\ast }$? Guess before reading on.

Steps.

1. Build a small NFA for $A=\{ab\}$: $p_0\stackrel{a}{\to }{p}_1\stackrel{b}{\to }{p}_2$ with $p_2$ the only accept. Why this step? We need a base machine to loop; $\{ab\}$ is a 3-state chain.

2. Add a fresh start-and-accept state $s_0$ with $\epsilon \to p_0$. Add $\epsilon$ from every old accept ($p_2$) back to $p_0$. New accept set $=\{s_0\}\cup \{p_2\}$. Why this step? The fresh $s_0$ gives $\epsilon \in A^{\ast }$ (the $A^0$, i.e. $k=0$, copy) without wrongly marking $p_0$ accepting. If instead you just marked the old start $p_0$ accepting, then any word that merely passes through $p_0$ mid-run (via the loop-back) would be wrongly accepted even without completing a whole copy of $A$. Looping $p_2\to p_0$ restarts a new copy of $A$.

3. Test each string. $\epsilon$: sits in $s_0$ (accept). $ab$: $s_0\stackrel{\epsilon }{\to }{p}_0\stackrel{a}{\to }{p}_1\stackrel{b}{\to }{p}_2$ (accept). $abab$: after first $ab$ at $p_2$, loop $\epsilon \to p_0$, read second $ab$ to $p_2$ (accept). $aba$: ends mid-copy at $p_1$ after the loop — not accepting. Why this step? $A^{\ast }$ contains exactly whole-number repetitions of $ab$; $aba$ is $1.5$ copies, so it must be rejected.

Figure 3 shows the star construction: the amber $s_0$ on the far left is the fresh start-and-accept state, its amber $\epsilon$-arrow feeds into $p_0$, and the curved amber $\epsilon$-arrow from $p_2$ back to $p_0$ is the loop that "restarts a new copy of $ab$." Note $s_0$ is the only state reachable by the empty string, which is why $\epsilon$ is accepted.

Verify: membership: $\epsilon \in (ab{)}^{\ast }$ (k=0) ✓, $ab\in$ (k=1) ✓, $abab\in$ (k=2) ✓, $aba\notin$ (odd length, cannot be $2k$) ✓. Length rule: any $w\in (ab{)}^{\ast }$ has even length; $|aba|=3$ is odd → rejected ✓.

---

(f) — Box C6: Degenerate & empty inputs

Forecast: is ${\varnothing }^{\ast }$ empty? Is it $\{\epsilon \}$? Pick before reading.

Steps.

1. ${\varnothing }^{\ast }$. Using powers, $A^{\ast }=A^0\cup A^1\cup \cdots$ with $A^0=\{\epsilon \}$ always. With $A=\varnothing$, every term $A^1,A^2,\dots$ is empty, but $A^0$ still contributes $\epsilon$. So ${\varnothing }^{\ast }=\{\epsilon \}$. Why this step? Star always includes the empty string (the $A^0$, zero-copies term), even when the base language is empty. This is the whole point of the fresh accept state $s_0$.

2. $\{\epsilon {\}}^{\ast }$. Concatenating $\epsilon$ with itself any number of times still gives $\epsilon$: $\epsilon \epsilon \cdots \epsilon =\epsilon$. Every power is $\{\epsilon {\}}^k=\{\epsilon \}$, so the union $\{\epsilon {\}}^0\cup \{\epsilon {\}}^1\cup \cdots =\{\epsilon \}$. So $\{\epsilon {\}}^{\ast }=\{\epsilon \}$. Why this step? No new words can ever appear because gluing empty strings produces only the empty string.

3. $\varnothing \cdot A$. Concatenation $\varnothing A=\{xy:x\in \varnothing ,y\in A\}$. There is no $x\in \varnothing$, so no pair $(x,y)$ exists, and the resulting set is empty → $\varnothing A=\varnothing$. Why this step? Concatenation needs a prefix from the first set; if that set is empty, no product string can form. ($\varnothing$ annihilates under concatenation, just like multiplying by 0.)

Verify: ${\varnothing }^{\ast }=\{\epsilon \}$ has size $1$ ✓. $\{\epsilon {\}}^{\ast }=\{\epsilon \}$ has size $1$ ✓. $\varnothing \cdot A=\varnothing$ has size $0$ ✓. Contrast: $\{\epsilon \}\cdot A=A$ (identity), so $\{\epsilon \}$ and $\varnothing$ behave oppositely under concatenation.

---

(g) — Box C7: Prove NON-regularity via closure

Forecast: why is it easier to prove $\{a^n{b}^n\}$ non-regular than $L$ itself?

Steps.

1. Suppose, for contradiction, $L$ were regular. Why this step? Closure arguments transfer non-regularity backward: we assume regular and derive an impossible consequence.

2. $a^{\ast }{b}^{\ast }$ is regular (a regular expression). Regular languages are closed under intersection (Product Construction), so $L\cap a^{\ast }{b}^{\ast }$ would be regular. Why this step? Intersecting with the "clean shape" $a^{\ast }{b}^{\ast }$ strips away messy interleavings and isolates the hard core.

3. Compute the intersection: strings that are all $a$'s then all $b$'s and have equal counts $=\{a^n{b}^n:n\ge 0\}$. Why this step? The $a^{\ast }{b}^{\ast }$ shape forces ${\#}_a=n$ leading $a$'s and ${\#}_b=m$ trailing $b$'s; equality forces $n=m$.

4. Apply the pumping lemma to $\{a^n{b}^n\}$: it is a standard non-regular language (pumping the pumped $a$-block breaks the count balance). Contradiction with step 2. Why this step? We reduced our unknown language to a known non-regular one; the contradiction kills the assumption.

Figure 4 pictures the argument as two overlapping circles: the cyan circle is $L$ (${\#}_a={\#}_b$), the white circle is the regular language $a^{\ast }{b}^{\ast }$, and their amber overlap is exactly $a^n{b}^n$. The caption traces the logic — if the whole cyan set were regular, its intersection with the white set would be too, yet the pumping lemma forbids the amber overlap from being regular.

Conclusion: $L$ is not regular.

Verify: intersection identity — sample $aabb$: ${\#}_a=2={\#}_b$ (∈$L$) and matches $a^{\ast }{b}^{\ast }$ → in intersection, and it equals $a^2{b}^2$ ✓. Sample $abab$: ${\#}_a=2={\#}_b$ (∈$L$) but does not match $a^{\ast }{b}^{\ast }$ (a $b$ then an $a$) → excluded from the intersection, confirming the intersection is exactly $\{a^n{b}^n\}$ ✓. Since $\{a^n{b}^n\}$ is non-regular by the pumping lemma, step 2's "$L\cap a^{\ast }{b}^{\ast }$ is regular" is impossible, so the assumption "$L$ is regular" fails ✓.

---

(h) — Box C8: Real-world word problem

Forecast: which two closure operations does this story secretly ask for?

Steps.

1. Translate to languages over $\Sigma =\{n,d\}$. Condition X: total value $\equiv 0(\mathrm{mod}25)$. Condition Y: sequence ends in $d$. Why this step? A story becomes solvable only once it is a formal language; "vends" = "accepted."

2. X is regular: track the running total mod 25 — only values $\{0,5,10,15,20\}$ matter, a 5-state DFA. Reading $n$ adds 5 mod 25; reading $d$ adds 10 mod 25; accept when total $\equiv 0$. Why this step? Money grows unboundedly, but mod 25 it lives in a finite set — finite memory, so regular.

3. Y is regular: a 2-state DFA remembering the last symbol (accept iff last was $d$). Why this step? Only the final coin matters, so one bit of memory suffices.

4. The vending set is $X\cap Y$ — regular by intersection closure (Box C1), built as the Product Construction of the 5-state and 2-state DFAs (up to $10$ states). Why this step? "Multiple of 25 and ends in dime" is an AND of two regular conditions.

Verify: test $ddnnd$ = $10+10+5+5+10=40$¢, $40\mathrm{mod}25=15\ne 0$ → not vended (fails X). Test $ddn$ = $25$¢, $25\mathrm{mod}25=0$ but ends in $n$ → not vended (fails Y). Test $ndd$ = $5+10+10=25$¢, $\equiv 0$ and ends in $d$ → vended ✓. So the language is regular and non-empty.

---

(i) — Box C9: The exam twist (De Morgan trap)

Forecast: is "flip the intersection's accept set" the same as $\overline{A}\cup \overline{B}$?

Steps.

1. Correct construction A: build the product DFA (which is total and deterministic), give it the intersection accept set $F_A\times F_B$, then flip to $Q\setminus (F_A\times F_B)$. Why this step? Because the product is already a DFA (exactly one state per string), flipping its accept set is valid complement — no NFA hazard here (contrast the [!mistake] in Box C3).

2. Correct construction B (the check): De Morgan's Laws give $\overline{A\cap B}=\overline{A}\cup \overline{B}$. Complement each DFA (flip its own accepts), then take the union via product with accept set $F_{\cup }$. Why this step? This double-derivation confirms both routes land on the same language — a favourite exam sanity check.

3. Spot the trap: the two accept sets must agree. $Q\setminus (F_A\times F_B)$ = "not (both final)" = "at least one non-final" = $(\overline{F_A}\times Q_B)\cup (Q_A\times \overline{F_B})$, which is exactly the union-of-complements accept set. They match. Why this step? If a student instead flipped each coordinate to $\overline{F_A}\times \overline{F_B}$ (both non-final), that is $\overline{A}\cap \overline{B}=\overline{A\cup B}$ — the wrong language. The De Morgan structure is the guardrail.

Verify (concrete counts): let $Q_A=\{a_0,a_1\}$, $F_A=\{a_1\}$; $Q_B=\{b_0,b_1\}$, $F_B=\{b_1\}$. Product has $4$ states. $F_A\times F_B=\{(a_1,b_1)\}$ (size 1). $\overline{A\cap B}$ accept set $=4-1=3$ states. Union-of-complements set $(\overline{F_A}\times Q_B)\cup (Q_A\times \overline{F_B})$: pairs with first $=a_0$ or second $=b_0$ = all $4$ minus the single $(a_1,b_1)$ = $3$ states ✓. The wrong "both non-final" set $\overline{F_A}\times \overline{F_B}=\{(a_0,b_0)\}$ has size $1\ne 3$ — clearly a different language.

---

Recall Quick self-test

Which box: "words with an even number of $a$'s that also start with $b$"? ::: C1 (AND → product / intersection) Is ${\varnothing }^{\ast }$ empty? ::: No — it is $\{\epsilon \}$; star always contributes the $A^0$ (k=0) copy. To complement an NFA, what must you do first? ::: Determinize it via subset construction, then flip accept states. Why glue with $\epsilon$-transitions for concatenation? ::: The NFA must guess the unknown split point between the $A$-part and the $B$-part. How does closure prove non-regularity? ::: Assume regular, intersect with a regular language to isolate a known non-regular language, hit a pumping-lemma contradiction.

Parent: Regular Languages — Closure Properties