1
$\begingroup$

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.

1 Answers 1

1

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