# How to prove that if $L$ is a regular language then $L'$ which is composed of words in $L$ with substrings as also words in $L$ is regular as well?

Let $$L$$ be a regular language.

Let $$L'=\{\sigma_1...\sigma_n|n\ge 1, \forall 1\le i\le n, \sigma \in \sum. \exists i: 1\le i\le n \quad\land\quad \exists u\in L: \sigma_1...\sigma_{i-1}u\sigma_{i+1}...\sigma_n\in L\}$$.

Prove that $$L'$$ is regular.

First of all, as far as I understand if for example $$L=\{abcxyzdef, xyz\}$$ then a possible word in $$L'$$ is $$abckdef$$ if $$\sum=\{a,b,c,d,e,f,k,x,y,z\}$$.

The proof is:

Because $$L$$ is regular then exists a DFA that receives it: $$A=\{\sum,Q,q_0,F,\delta \}$$. We can build a DFA $$B$$ which will receive $$L'$$ as follows: $$B=\bigg\{\sum, Q\times\{1,2\}\cup Q\times Q, (q_0, 1), F\times\{2\}, \mu \bigg\}$$

1) Because we need to keep track of two states: one progress of transitions within a word in $$L'$$ and also progress in $$u$$ we can use flags $$1$$ to signify when we're not inside $$u$$ and $$2$$ when inside. I don't understand why we need the union with $$Q\times Q$$. Why not a union with just $$Q$$ so it's a $$3$$-tuple, where the first two coordinates define that state from the beginning of the word and the third coordinate defines the state of $$u$$.

Transition function $$\mu$$ before reading $$u$$: $$\mu((q,1),\sigma)=\{(\delta(q,\sigma),1), (q,q_0)\}\bigg| \sigma\in \sum, q\in Q$$

Either we read some letter before $$u$$ ($$abc$$ in my example) or we're at index $$i$$ (reading $$k$$ in my example in the case of $$(q,q_0)$$)

$$\mu$$ when reading $$u$$: $$\mu((q,p), \epsilon)\supseteq\{(\delta(q,\sigma),\delta(p, \sigma))\}\bigg|\sigma \in \sum, q,p \in Q$$

2) We can't read $$u$$ directly from the input so we need $$\epsilon$$ to "connect" to $$u$$. Do we need $$\delta(q,\sigma)$$ to continue reading the original word ($$def$$ in my example) while $$\delta(p, \sigma)$$ is to start reading $$u$$ ($$xyz$$ in my example)?

reading the end of $$u$$: $$\mu((q,p),\epsilon)\supseteq\{(q,2)\}\bigg| q\in Q, p\in F$$

3) Does this transition mean that we arrive to the end of $$u$$? So $$(q,2)$$ to signify the end of $$u$$?

continuation from reading $$u$$: $$\mu((q,2),\sigma)=\{\delta(q,\sigma),2)\}\bigg|\sigma \in \sum, q\in Q$$

4) does this mean that we read the last letter of $$u$$ and eventually get to the last letter of the original word? It would be $$def$$ letters from my example. But why reading each of those letters would be an accepting state? Shouldn't reading only $$f$$ lead to the accepting state?