Single-symbol insertion into a regular language

ID: single-symbol-insertion-into-a-regular-language

For a fixed symbol and a regular language , inserting exactly one 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 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.

New to topics? Read the docs here!