# Pumping lemma for regular “pumped formal language”

Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. We define $$\verb+lmult+(L)=\left\{x^iu\;|\;x\in\Sigma,u\in\Sigma^*,i>0,xu\in L\right\}\cup\{\epsilon\}.$$ [...]

Show the following: Iff for all $x\in\Sigma,u\in\Sigma^*$ the implication $xu\in L\Rightarrow u\in L$ is true, then 1 is a regular pumping lemma number for $\verb+lmult+(L)$.

My thoughts so far:

Assume that the implication is valid for all combinations of $x\in\Sigma,u\in\Sigma^*$ then we can pick an arbitrary $y\in \verb+lmult+(L)$ which can be split up into $y=vxu$. Under the condition of the pumping lemma we know that $x\neq\epsilon$ and $|vx|\leq1$ implies $v\overset{!}{=}\epsilon$. We now have to proove that $\forall i:x^iu\in\verb+lmult+(L)$.

Here is the point I am not really sure about which needs some "polishing":

By definition of $\verb+lmult+(L)$ we know that $x^iu\in\verb+lmult+(L)$ (and therefore that $\verb+lmult+(L)$ has the regular pumping lemma number 1) iff $xu\in L$. We know nothing about $u\in\Sigma^*$ but neither we have any restrictions for that. The next step is to decompose $y=x^iu$ so that we can check whether $xu\in L$. With the very first implication we can write $$x^iu=x^{i-1}xu\in\verb+lmult+(L)\Rightarrow x^{i-1}u\in\verb+lmult+(L)\Rightarrow\ldots\Rightarrow xu\in\verb+lmult+(L)\Rightarrow xu\in L.$$

I would like to know whether my approach is correct and how you would solve/rewrite it.

-
You'll definitely get better answers if you ask on Computer Science. –  Gigili May 20 '12 at 17:56
@Gigili: I am not allowed to ask homework-related questions there. The FAQ doesn't allow it! –  Christian Ivicevic May 20 '12 at 18:00
What? I guess you are referring to another SE site, the one I suggested even has the (home-work) tag. –  Gigili May 20 '12 at 18:08
The site @Gigli refers to is Theoretical CS, which only allows research-level questions, and this is not such a question. The Plain CS site has a homework tag annotated with "Use this tag if you want to be given hints, not full answers". –  David Lewis May 20 '12 at 18:20
@DavidLewis: Should I repost this question or can i move it there? –  Christian Ivicevic May 20 '12 at 18:25

Lemma. Suppose that for all $x\in\Sigma$ and $u\in\Sigma^*$ we have $xu\in L\implies u\in L$. Then $L\subseteq\mathrm{lmult}(L)$.
Using the lemma, it’s not too hard to show that its hypothesis implies that $1$ is a regular pumping number for $\mathrm{lmult}(L)$. Let $w\in\mathrm{lmult}(L)$ be non-empty. By definition $w=x^iu$ for some $i>0$ and $x\in\Sigma$, $u\in\Sigma^*$ such that $xu\in L$, so we can write $w=xz$, where $z=x^{i-1}u$. Thus, $x^kz=x^{i-1+k}u$. If $k>0$, $i-1+k\ge i$, and it’s clear from the definition that $x^kz\in\mathrm{lmult}(L)$. Suppose, then, that $k=0$. If $i>1$, there’s still no problem: $z=x^{i-1}u\in\mathrm{lmult}(L)$ by definition, since $xu\in L$ and $i-1>0$. Finally, if $k=0$ and $i=1$, $x^kz=z=u\in L\subseteq\mathrm{lmult}(L)$ by the lemma.
To recapitulate, we’ve shown that for any non-zero $x^iu\in\mathrm{lmult}(L)$, the decomposition $w=\epsilon xz$ satisfies the conclusion of the pumping lemma with pumping number $1$.
The other direction isn’t quite true. Let $\Sigma=\{1\}$ and $L=\Sigma^+$. Then $\mathrm{lmult}(L)=\Sigma^*$, which has $1$ as a regular pumping number, but $L$ does not have the property that $xu\in L\implies u\in L$ for all $x\in\Sigma$ and $u\in\Sigma^*$: take $x=1$ and $u=\epsilon$.