Search code examples
regular-languageproofautomata

Regular language closure under insertion

Suppose I have a regular language L under alphabet Σ. How do I show that the language L' is still a regular language when I insert a symbol in the middle?

For example, L includes a string w which consists of two substrings u and v (w = uv) I want to show that a regular language L' includes a string uxv where x is the inserted symbol.

Note that u and v doesn't have to have the same length, and x is also in the same alphabet Σ.

Thank you!

Solution

  • Since L is regular, there exists a finite automaton A that accepts it. Make two copies (A1 and A2) of A. In A2 make the start state not initial. For every state p in A1 add a transition p --x--> p to the corresponding state in A2.

    Using your example's notation, now A1 reads u, the new transition reads x and A2 reads v.