= Solution
Let $A=(Q,\{0,1\},\delta,q_0,F)$ be a <deterministic finite automaton> recognizing $L$. Construct a <nondeterministic finite automaton> $B$ with <automaton state> <set> $Q\times\{0,1\}$. Its second coordinate records whether the extra zero has already been consumed. Start at $(q_0,0)$ and make exactly the <automaton states> in $F\times\{1\}$ accepting.
For each $q\in Q$, $i\in\{0,1\}$, and $a\in\{0,1\}$, include the ordinary <automaton transition>
$$
(q,i)\xrightarrow{a}(\delta(q,a),i).
$$
Also include the extra <automaton transition>
$$
\boxed{(q,0)\xrightarrow{0}(q,1)\qquad(q\in Q).}
$$
This consumes the inserted zero without changing the simulated <automaton state> of $A$. At a zero in layer zero, both the ordinary and extra choices are available. There are no <automaton transitions> from layer one back to layer zero.
If $xy\in L$, run $A$ on $x$ in layer zero, consume the extra zero by the displayed <automaton transition>, and run $A$ on $y$ in layer one. The resulting run accepts $x0y$ in $B$.
Conversely, every accepting run of $B$ starts in layer zero and finishes in layer one, so it uses exactly one extra <automaton transition>. Split its input as $x0y$ at that move. Removing that consumed zero leaves precisely a run of $A$ on $xy$, ending in $F$. Hence $xy\in L$. The construction also permits an insertion at either end, including insertion into the <empty word>.
Therefore $L(B)=L'$. Since $B$ has $2|Q|$ <automaton states>, \b[$L'$ is a <regular language>]. This is a <single-symbol insertion into a regular language>.
$$
\boxed{L'=L(B)\text{ is regular}.}
$$
Back to article page
