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

All five. Union, intersection, complement, concatenation, and Kleene star each have an explicit machine construction, so the result always has a machine, so it is regular by definition. Answer: 5 of 5.

You swap accept and non-accept states. New machine $\overline{M}=(Q,\Sigma ,\delta ,q_0,Q\setminus F)$. Why this works (one line): a DFA lands in exactly one state on any string, so "not accepted" and "accepted-by-the-flipped-set" are the same event. New accept set $=Q\setminus F$.

Accept set $=F_A\times F_B$ (both coordinates final). Transition: $\delta ((p,q),x)=({\delta }_A(p,x),{\delta }_B(q,x))$ — feed the same letter $x$ to both robots at once. See Product Construction.

A product DFA has $|Q_A|\times |Q_B|$ states — one for every combination of "where robot A is" and "where robot B is." Here $2\times 2=\boxed{4}$ states. Label A's states $E$ (even $0$s, accepting) and $O$ (odd). Label B's states $y$ (last letter was $1$, accepting) and $n$ (not). The four product states are $(E,y),(E,n),(O,y),(O,n)$. Accept = both final: only $(E,y)$. See the picture below — the two axes are the two robots, the one accepting corner is highlighted.

Union = accept if at least one coordinate is final. So $F_{\cup }=(F_A\times Q_B)\cup (Q_A\times F_B)$. $F_A\times Q_B=\{(E,y),(E,n)\}$ (A happy, B anything). $Q_A\times F_B=\{(E,y),(O,y)\}$ (B happy). Union of those: $\boxed{\{(E,y),(E,n),(O,y)\}}$ — three accepting states. The only rejecting state is $(O,n)$: odd $0$s and doesn't end in $1$, so neither condition holds.

An $\epsilon$-transition is a "free jump" the robot may take without reading a letter. A string in $AB$ splits as $x$ (in $A$) then $y$ (in $B$), and we don't know where — so we let the machine guess by jumping to $B$ the instant $A$ could finish. Add one $\epsilon$-transition from each accept state of $A$ to $b_0$: from $f_1$ and from $f_2$, so $\boxed{2}$ transitions. New accepts $=F_B$ only. $M_A$'s old accept states stop being final (finishing $A$ is no longer "done" — you still owe a $y$ from $B$).

Take $A=\{ab\}$ (exactly the two-letter string $ab$). A minimal machine: $a_0\stackrel{a}{\to }{q}_1\stackrel{b}{\to }f$ with $f$ accepting. For $A^{\ast }$ we loop back from $f$ to $a_0$. If we also mark $a_0$ accepting, watch the input $aba$: read $a$: $a_0\to q_1$; read $b$: $q_1\to f$; loop $\epsilon$: $f\to a_0$; read $a$: $a_0\to q_1$. String ends in $q_1$ — not accepting, good. But consider $aba?$... the real failure: any string that passes through $a_0$ mid-word (after a completed copy and one more letter that returns to start) can be wrongly accepted when $a_0$ is final. Cleanest counterexample: if $a_0$ has an incoming letter-transition (common after minimization), a partial word that lands back on $a_0$ without completing a copy of $A$ gets accepted. Fix (as in the parent): use a fresh state $s_0$ as new start and the sole $\epsilon$-acceptor, loop back to $a_0$ (never into $s_0$). Then $\epsilon$ is accepted via $s_0$ and no mid-word position is falsely final.

Nondeterminism means: the string is accepted iff some guess works, and rejected iff no guess works. A wrong split (jumping to $B$ too early or late) simply leads to a branch that fails to reach an accept state — it costs nothing. The string is accepted only when there exists a split $w=xy$ with $x\in A$ and $y\in B$, which is exactly the definition of $AB$. So guessing can never accept a string outside $AB$: a fake accept would require a real split, contradiction.

$\varnothing$ = the language accepting no strings; its DFA is a single non-accepting sink ($F=\varnothing$). Flipping: $Q\setminus F=Q$, so every state accepts $\Rightarrow$ accepts everything $\Rightarrow \overline{\varnothing }={\Sigma }^{\ast }$. ✓ ${\Sigma }^{\ast }$ = accepts all strings; DFA is a single accepting state ($F=Q$). Flipping: $Q\setminus F=\varnothing$, accepts nothing $\Rightarrow \overline{{\Sigma }^{\ast }}=\varnothing$. ✓ Both results are regular (each is a one-state DFA), confirming complement stays inside the club even in degenerate cases.

$\{a{\}}^{\ast }$ = "any number of $a$s (including zero)" is regular (single-letter Kleene star). Likewise $\{b{\}}^{\ast }$. $\{a^n{b}^m\}=\{a{\}}^{\ast }\cdot \{b{\}}^{\ast }$ — a block of $a$s concatenated with a block of $b$s. Concatenation of two regular languages is regular. Therefore $\{a^n{b}^m\}$ is regular. ∎ Why this is the point: we proved regularity purely by closure algebra, never designing states. Equivalently it is the regular expression $a^{\ast }{b}^{\ast }$.

Let $\Sigma =\{0,1\}$.

• $C$ = "contains $01$" $={\Sigma }^{\ast }01{\Sigma }^{\ast }$: concatenation of the regular pieces ${\Sigma }^{\ast }$, the constant string $01$, and ${\Sigma }^{\ast }$. Regular (concatenation + star).
• $E$ = "even length" $=(\Sigma \Sigma {)}^{\ast }$: take pairs of letters and star them. Regular (concatenation + star).
• The target is $C\cup E$, union of two regular languages ⇒ regular. ∎ As a regex: $\left({\Sigma }^{\ast }01{\Sigma }^{\ast }\right)+((\Sigma \Sigma {)}^{\ast })$.

De Morgan (sets): $\overline{X\cap Y}=\overline{X}\cup \overline{Y}$. Put $X=\overline{A},Y=\overline{B}$: $\overline{\overline{A}\cap \overline{B}}=\overline{\overline{A}}\cup \overline{\overline{B}}=A\cup B$ (double complement cancels). ✓ identity holds. Why it re-proves closure: we already know regular languages are closed under complement (flip) and intersection (product). The identity writes $A\cup B$ using only those two operations. So if $A,B$ are regular, so is $A\cup B$ — no new machine needed. This is a second, independent proof besides the direct product-union construction.

Strategy: if $L$ were regular, closure would force a language we know is non-regular to be regular — contradiction.

1. Suppose, for contradiction, $L$ is regular.
2. $a^{\ast }{b}^{\ast }$ (any $a$s then any $b$s) is regular.
3. Regular languages are closed under intersection, so $L\cap a^{\ast }{b}^{\ast }$ would be regular.
4. Compute it: a string in $a^{\ast }{b}^{\ast }$ has the form $a^n{b}^m$; it lies in $L$ iff ${\#}_a={\#}_b$, i.e. $n=m$. So $L\cap a^{\ast }{b}^{\ast }=\{a^n{b}^n:n\ge 0\}$.
5. But $\{a^n{b}^n\}$ is not regular (pumping lemma). Contradiction.
6. Therefore $L$ is not regular. ∎ Why this step-by-step works: closure runs backward — it transfers non-regularity from the known-bad language up to $L$. The intersection with $a^{\ast }{b}^{\ast }$ is the "filter" that isolates the troublesome equal-count strings.

Base NFA for $A=\{0,00\}$: start $a_0$, $a_0\stackrel{0}{\to }{f}_1$ (accept, the string $0$), $f_1\stackrel{0}{\to }{f}_2$ (accept, the string $00$). Accepts $\{f_1,f_2\}$. Star build: add fresh $s_0$ (new start, accepting). $\epsilon$-jumps: $s_0\stackrel{\epsilon }{\to }{a}_0$ (enter one copy) and from each old accept $f_1,f_2$ back to $a_0$ (restart). New accept set $=\{s_0,f_1,f_2\}$.

Checks:

• $\epsilon$: stay on $s_0$ (accepting). ✓ (this is the $k=0$ case).
• $0$: $s_0\stackrel{\epsilon }{\to }{a}_0\stackrel{0}{\to }{f}_1$ (accepting). ✓
• $000$: $s_0\to a_0\stackrel{0}{\to }{f}_1\stackrel{\epsilon }{\to }{a}_0\stackrel{0}{\to }{f}_1\stackrel{\epsilon }{\to }{a}_0\stackrel{0}{\to }{f}_1$ — reading $0+0+0$ as three copies of "$0$" — ends on $f_1$. ✓ (Also reachable as $00\cdot 0$.)
• Nothing false: every accepting path either sits on $s_0$ (read nothing) or ends on $f_1/f_2$ immediately after reading a full copy of $A$; loop-backs go to $a_0$, never into $s_0$, so no mid-copy position is accepting.

No. ${\bigcup }_{i\ge 0}\{a^i{b}^i\}=\{a^n{b}^n:n\ge 0\}$, which is not regular. The subtle point: closure guarantees regularity only for finitely many applications of the operations. Union closure says $A\cup B$ is regular for two (and by induction any fixed finite number of) regular inputs. It says nothing about combining infinitely many. Each finite union $A_0\cup \cdots \cup A_k$ is regular; the limit need not be. Closure is a finite-composition promise, not an infinite one.

Complement ::: flip accept/non-accept on a DFA (determinize an NFA first). Intersection ::: product DFA, accept $F_A\times F_B$. Union ::: product with accept $(F_A\times Q_B)\cup (Q_A\times F_B)$, or an $\epsilon$-NFA guessing a machine, or De Morgan. Concatenation ::: $\epsilon$-jump from every accept of $A$ to start of $B$; accepts $=F_B$. Kleene star ::: fresh accepting start $s_0$, $\epsilon \to a_0$, loop each old accept back to $a_0$; accepts $=\{s_0\}\cup F_A$. Non-regularity trick ::: intersect the suspect language with a simple regular language to expose a known non-regular one.