= Single-symbol insertion into a regular language
{title2=$\{xay:xy\in L\}$}
For a fixed symbol $a$ and a <regular language> $L$, inserting exactly one $a$ at an arbitrary position preserves regularity. Make two copies of a recognizing <finite-state automaton>, one before and one after the insertion. Preserve its ordinary <automaton transitions> in each copy, and add a transition consuming $a$ from each before-state to its matching after-state. Accept only in the after-copy. Every accepting run makes exactly one of the additional moves.
Back to article page
