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

We keep ONE concrete pair of tiny machines the whole way, so nothing is abstract.

Step 0 — What is a machine that reads a string?

Our two robots for the whole page:

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

Robot $A$ (left, blue): accepts strings over ${0, 1}$ with an even number of $0$ s. State $E$ = "so far even", state $O$ = "so far odd". Reading a $0$ flips $E \leftrightarrow O$ ; reading a $1$ changes nothing. Start = $E$ , happy = $E$ (double circle).
Robot $B$ (right, pink): accepts strings that end in $1$ . State $N$ = "last letter was not $1$ (or nothing read yet)", state $Y$ = "last letter was $1$ ". Reading a $1$ jumps to $Y$ ; reading a $0$ jumps to $N$ . Start = $N$ , happy = $Y$ .

Every symbol we use below is one of these circles and arrows. Nothing else exists yet.

Step 1 — The question we want a machine to answer

We need a single machine that watches both facts at once.

Step 2 — The idea: run both robots in parallel

Because $A$ has $2$ circles ${E, O}$ and $B$ has $2$ circles ${N, Y}$ , the number of possible pairs is $2 \times 2 = 4$ . Here they are as a grid:

Step 3 — How the combined machine moves

Let us actually draw an arrow. Start at $(E, N)$ and read a $1$ :

$A$ : reading $1$ at $E$ keeps it at $E$ (a $1$ never changes $0$ -parity).
$B$ : reading $1$ at $N$ jumps to $Y$ (last letter is now $1$ ).
So $(E, N) 1 (E, Y)$ .

Repeat this for every box and both letters and you get the full product machine — every circle has exactly one $0$ -arrow and one $1$ -arrow, so it is still a proper deterministic robot.

Step 5 — Who says YES? (the ONLY place AND vs OR differ)

Step 6 — Trace a real string end to end

Step 7 — Edge and degenerate cases (never leave a gap)

Picture two little reading-robots side by side. You read the same string out loud, one letter at a time, and both robots step forward together on every letter. To keep score you just note where each robot is standing — a pair of positions, like "(robot A on E, robot B on Y)". That pair is the state of one big combined robot; there are (A's spots) × (B's spots) of them. The combined robot's move rule is nothing new: each half of the pair just obeys its own old robot. It starts at "(A's start, B's start)". The only decision left is when to shout YES: if you want both conditions, shout only when both halves are on a happy spot; if you want either condition, shout when at least one half is happy. Same wiring, different YES-lights. Because we literally built this machine out of the two given ones, the result is still something a finite robot accepts — so it is still a regular language. That is the whole proof, and you drew every piece of it.

Recall Quick self-test

How many states does the product of an $m$ -state DFA and an $n$ -state DFA have? ::: Exactly $m \times n$ (one per pair). For intersection, which pairs accept? ::: Only pairs where both coordinates are accepting: $F_{A} \times F_{B}$ . For union, which pairs accept? ::: Pairs where at least one coordinate accepts: $(F_{A} \times Q_{B}) \cup (Q_{A} \times F_{B})$ . Does the transition wiring differ between AND and OR? ::: No — only the set of accepting states differs.

Related: Deterministic Finite Automata (DFA) · Regular Expressions · Product Construction · De Morgan's Laws · Pumping Lemma for Regular Languages · back to the parent topic.

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