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

True — a 1-state DFA that accepts nothing (no accept states) gives $\varnothing$; make that one state accepting and you get ${\Sigma }^{\ast }$. Both are finite machines, so both are regular.

False — closure says the complement is still regular, not that it differs. Complementing ${\Sigma }^{\ast }$ gives $\varnothing$, but complementing a language equal to its own complement is impossible over a fixed $\Sigma$; still, "closed" only promises "stays regular."

True — write $A\setminus B=A\cap \overline{B}$. Complement of $B$ is regular, intersection of two regulars is regular (Product Construction), so the difference is regular.

False — closure runs one direction only. Take $A=\{a^n{b}^n\}$ (non-regular) and $B=\overline{A}$; their union is ${\Sigma }^{\ast }$ (regular), yet neither piece is regular.

False — closure is proved only for two (hence any finite number by induction), and the proof does not extend to infinitely many. It happens to often stay regular, but there is no theorem guaranteeing it, so "always" is unjustified; the finite-case machine construction simply gives no machine for an infinite intersection.

True — by definition $A^{\ast }$ collects concatenations of $k$ strings from $A$ for every $k\ge 0$, and the $k=0$ case (zero copies) is the empty concatenation, which equals $\epsilon$ — regardless of what $A$ is (even $A=\varnothing$ gives ${\varnothing }^{\ast }=\{\epsilon \}$).

False — concatenation glues strings in order ($AB=\{xy:x\in A,y\in B\}$). With $A=\{a\}$, $B=\{b\}$, $AB=\{ab\}\ne \{ba\}=BA$. It's still regular either way, but not commutative.

True — flip every transition arrow, swap start and accept roles (via an $\epsilon$-start), and you get an NFA for $A^R$. It's a standard closure result even though it isn't in the "big five."

Error: an NFA can reach both an accepting and a non-accepting state on the same input via parallel paths, so swapping accepts strings the original also accepted. Fix: run Subset Construction (NFA to DFA) to get a DFA first, then swap.

Error: if $a_0$ has incoming loop-back arrows, a string can pass through $a_0$ mid-word without completing a copy of $A$ and get wrongly accepted. Fix: add a fresh start/accept state $s_0$ with $\epsilon \to a_0$, and loop back to $a_0$, not into $s_0$.

Error: the prefix $x\in A$ could finish at any accept state of $M_A$, so a single arrow misses valid splits. Fix: add the $\epsilon$-arrow from every accept state of $M_A$ (every state in $F_A$) to the start of $M_B$.

Error: the De Morgan identity (see De Morgan's Laws) is just a second proof of union closure — a cross-check. Union also has direct constructions (product with accept set $F_A\times Q_B\cup Q_A\times F_B$, or an $\epsilon$-NFA guessing which machine).

Error: the product tracks both current states as a pair $(p,q)$, so it has $|Q_A|\times |Q_B|$ states — a product, not a sum. That's the whole point of running the machines in parallel.

Error: intersection with $a^{\ast }{b}^{\ast }$ only produces a non-regular result when the other input is already non-regular. Closure never fails for two regulars; the argument instead proves the other language is non-regular by contradiction (see Pumping Lemma for Regular Languages).

Error: you simply take the alphabet to be the union ${\Sigma }_A\cup {\Sigma }_B$; both machines then read over the common alphabet (missing transitions go to a dead state). Alphabet mismatch is a bookkeeping step, not a wall.

Because a DFA lands in exactly one state per input, so "accept vs reject" is a clean flip. An NFA's "accept if some path succeeds" has no clean opposite — negating "some path" needs "all paths," which determinization supplies.

The product tracks the full pair of states $(p,q)$, which is all the information either machine has. Intersection and union differ only in which pairs you call accepting ($F_A\times F_B$ for AND, the larger set $F_A\times Q_B\cup Q_A\times F_B$ for OR), not in the machine itself.

Both need to guess something a DFA can't: concatenation guesses where to split $xy$, and star guesses when one copy of $A$ ends. Nondeterminism plus $\epsilon$-jumps encode "try every split/restart point at once."

We do get it free three ways — product directly, or via $A\cap B=\overline{\overline{A}\cup \overline{B}}$ (De Morgan), or from complement+union. The point is that any one closure proof plus De Morgan bootstraps the others; none is truly independent.

Because "regular" is defined as "accepted by some finite automaton" (equivalently, described by a regular expression). Exhibiting a machine is exactly meeting the definition — no separate argument needed.

Closure guarantees that if the pieces are regular and you only combine them with the five operations, the whole stays regular. The construction exists even if we never write it out — existence is all the definition asks.

$\{\epsilon \}$ — the only way to build a string from zero copies (the $k=0$ case) of a language with no strings is the empty concatenation, which yields $\epsilon$. So ${\varnothing }^{\ast }$ is not empty.

Still $\{\epsilon \}$ — concatenating $\epsilon$ with itself any number of times just gives $\epsilon$ again. Star can't manufacture new strings from $\epsilon$ alone.

Yes — the star construction (fresh $s_0$, loop-back $\epsilon$-arrows) works for any regular $A$, finite or infinite. Regularity of $A^{\ast }$ depends only on $A$ being regular, not on $A$ being finite.

Yes, trivially — running two copies of the same machine in parallel gives a product DFA, and the accept set $F_A\times F_A$ recovers $A$. It's a valid (if redundant) instance of closure.

$\varnothing$ — since there is no $y\in \varnothing$ to append, no string $xy$ can be formed. The $\epsilon$-glue construction dead-ends because $M_B$ for $\varnothing$ has no accept state. It's regular (empty is regular).

It can be — but if $\overline{A}$ were regular, then $A=\overline{\overline{A}}$ would be regular too (complement closure). So $A$ non-regular forces $\overline{A}$ non-regular; a regular complement is impossible for a non-regular $A$.