# proof that a language is a regular according to another language

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.

• Can you create a finite state machine for $L^\prime$? You already know you can create a FSM for $L$, and you can use that as a starting point. – Larry B. Nov 1 '18 at 17:01
• @FabioSomenzi any clue? – UltimateMath Nov 1 '18 at 18:52
• Sorry for the misleading comment. I misread the definition of $L'$. I put a comma between $w_1$ and $w_2$, which made the problem trivial to solve with regular expressions. The actual problem is better tackled with automata as suggested by Larry B.. – Fabio Somenzi Nov 1 '18 at 22:07

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.