# How to use product automaton and intermediate state to prove existence of regular language?

Let $$L$$ be a regular language over alphabet $$\Sigma$$.

Let $$\frac{1}{2}L$$ be the following language: $$\{w\in\Sigma^* \mid \exists y\in \Sigma^*: |y|=|w|, wy\in L \}$$. For example if $$L=\{\epsilon, aba, aaba, babb\}$$ then $$\frac{1}{2}L=\{\epsilon, aa,ba\}$$. Prove that $$\frac{1}{2}L$$ is a regular language.

An example of proof that I saw uses definition of product automaton:

Because $$L$$ is a regular language a DFA exists $$A=\big( \Sigma, Q,q_0, F,\delta \big)$$ which receives $$L$$. Let $$p\in Q$$ and we can define a language $$L_p$$: $$L_p=\bigl\{ w\in \Sigma^*\mid \exists y\in \Sigma^*:\delta(q_0,w)=p, \delta(p,y)\in F \bigr\}$$ We can define a finite automaton which receives $$L_p$$: $$A_p=\bigl(\Sigma, Q\times Q, (q_0,p), \{p\} \times F, \delta_p \bigr)$$ Let us define $$\delta_p$$ for all $$q_1, q_2 \in Q$$, $$\sigma\in \Sigma$$: $$\delta_p((q_1, q_2), \sigma) = \bigl\{ (\delta(q_1, \sigma), \delta(q_2, \sigma')) \mid \sigma'\in \Sigma \bigr\}$$ Therefore: $$\frac{1}{2}L=\bigcup_{p\in Q} L_p$$ and because regular languages are closed under finite union then $$\frac{1}{2}L$$ is a regular language.

I understand that $$p$$ is some kind of an intermediate state between two halves of a word in $$L$$. I understand that the set of accepting states $$\{p\}\times F$$ means that we take some intermediate state $$p$$ with an accepting state in $$L$$ and for this there must be a total of $$Q\times Q$$ available states.

I don't understand why in $$\bigl\{ (\delta(q_1, \sigma), \delta(q_2, \sigma')) \mid \sigma'\in \Sigma \bigr\}$$ we need to use $$\sigma$$ and $$\sigma'$$. For example, if there's a word $$aaaa$$ ($$aa\in \frac{1}{2}L$$) in $$L$$ then $$\sigma=a$$ and $$\sigma'=a$$ so why do they need to be different.

Also I don't understand why we need this union: $$\frac{1}{2}L=\bigcup_{p\in Q} L_p$$. Are there many different languages $$L_p$$? Didn't we define a single one?

• This proof is just wrong. We clearly don't have : $\frac{1}{2}L = \cup_{p \in Q} L_p$ since $L_p$ can be essentially defined as : "all words such that there is path from $q_0$ to $p$ that can be encode with this word". If there there is no word that allows from $p$ to go on a final state then $L_p = \emptyset$. With this mind the union is not equal to $\frac{1}{2}L$ – Thinking Nov 8 '18 at 20:37

## 1 Answer

Hint. There is a missing condition in the definion of $$L_p$$, which should be $$L_p = \bigl\{ w\in \Sigma^*\mid \exists y\in \Sigma^*,\ |y| = |w|,\ \delta(q_0,w)=p \text{ and } \delta(p,y)\in F \bigr\}$$ The formula $$\frac{1}{2}L=\bigcup_{p\in Q} L_p$$ is now correct. Do you understand the other steps?