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.
Articles by others on the same topic
There are currently no matching articles.