1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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$ $\endgroup$ – Thinking Nov 8 '18 at 20:37
1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.