let $L\subseteq\Sigma^*$ be a regular language.
for $\sigma \in \Sigma$ prove that $L'=\{w_1\sigma w_2:w_1w_2\in L\}$ is a regular languge.
I tried induction on the length of the regular expression of L.
there are 3 cases in the induction:
$r=r_1\cup r_2, r =r_1\cdot r_2 , r=(r_1)^*$.
the first one is pretty easy but now I stuck on the 2nd and the 3rd.
in the 2nd case:
$w_1\sigma w_2\in L' \leftrightarrow w_1w_2\in L=L(r)=L(r_1\cdot r_2 )=L(r_1)\cdot L(r_2 )$
but at this point I stuck cause I can't say that $w_1\in L(r_1)$ or something like that.
in the 3rd case:
$w_1\sigma w_2\in L' \leftrightarrow w_1w_2\in L=L(r)=L((r_1)^*)=L(r_1)^* \leftrightarrow w_1 w_2=\epsilon$ or $w_1w_2=w_1\cdot w_2…w_k, k>0, \forall i =1…k, w_i \in L(r_1)$
and I have no idea how to finish that case.
Best Answer
The problem can be solved using automata, but your suggested approach is very interesting. However, you have to be very careful since there is nothing like "the regular expression of $L$" (a regular language admits infinitely many regular expressions that represent it). To avoid this potential problem, you can argue directly on regular languages as follows.
Let $a$ be a fixed letter of the alphabet $A$. For each language $L$ of $A^*$, let $$ L' = \{uav \mid u,v \in A^*,\ uv \in L\} $$ Let $\mathcal{C}$ be the class of all regular languages $L$ of $A^*$ such that $L'$ is regular. Our aim is to show that $\mathcal{C}$ contains all regular languages.
Step 1. The class $\mathcal{C}$ contains the empty language, the language $\{1\}$ and the languages $\{b\}$ for each letter $b$. Trivial (actually you could say directly that any finite language belongs to $\mathcal{C}$).
Step 2. The class $\mathcal{C}$ is closed under finite union. This follows from the formula $(L_1 \cup L_2)' = L_1' \cup L_2'$, which you already observed.
Step 3. The class $\mathcal{C}$ is closed under product. This follows from the formula $(L_1L_2)' = L_1L_2' \cup L_1'L_2$, which essentially says that if you want to insert an $a$ in $L_1L_2$, you have to insert it either in a word of $L_1$ or in a word of $L_2$.
Step 4. The class $\mathcal{C}$ is closed under star. This follows from the formula $(L^*)' = L^*L'L^* \cup \{a\}$ that I let you verify.
Thus $\mathcal{C}$ contains the finite languages and is closed under union, product and star: thus it contains all regular languages.