Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 1 / c

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 transitionAlso include the extra automaton transitionThis 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^{\prime }$. Since $B$ has $2|Q|$ automaton states, $L^{\prime }$ is a regular language. This is a single-symbol insertion into a regular language.