Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

Since this is homework, I’ll leave some of the work to you. In particular, I’ll leave it to you to prove this

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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