How to show that if the language L is regular, then L' is regular?

Question

Let L be any regular language and a ∈ Σ. How to show that the language L'={uav | uv ∈ L} is regular too?

Wikipedia says a way to proove it is to lead it back to a regular language but I don't understand how to do that in this case. Hope somebody can help.

Answer 1

There are lots of ways to show this. I think an argument whereby we construct a DFA is particularly easy to visualize.

Imagine a DFA for your language L. Let's call it M. Imagine it sprawled out in diagram form on a table. Now, imagine making a copy of M and spreading it out next to M on the table. Call it M'.

Now - from M, add a new transition from state q of M to the corresponding state q' of M'. The transition is on the symbol a.

Now, consider the aggregate machine whose start state is the start state of M and whose accepting states are the accepting states of M'. This machine starts out accepting strings in L, then accepts an a somewhere in the middle, and then continues accepting strings in L from where it left off. This is the language we were going for and we have defined a perfectly reasonable NFA for it. Since any language accepted by an NFA is regular, our language is regular.