Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
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
1  
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

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.