[Solved]: Factorial usage within proof using the pumping lemma

Problem Detail: 

We are going over the pumping lemma in class and we recently went over the following example:

1. Let $$ L = \{ w \mid w \text{ has a different number of 0s and 1s} \} $$
2. Consider $$ s = 0^P1^\left(P+P!\right) $$
3. $ s $ can be divided into $ s = xyz $
4. Consider $$ y = 0^m; 0 \leq m \leq P $$
5. Let $ i = \frac{P!}{m} + 1 $
6. $$ xyz = 0^\left(P + \left(i - 1\right)m\right)1^\left(P + P!\right) \notin L $$

Forgive me if the example is not put together well. This example didn't quite get finished in class. Feel free to expand on this if need be.

However, my question is how does one know to use a factorial in the first place when approaching this proof?

Asked By : Bryan Roth

Answered By : frafl

Let's choose a different word in step 2, say $s' = 0^a1^b$, where $a$ and $b$ depend on $P$ and $a \geq P$ (to force an $y$ that has the form $y=0^m$).

It's important to show that for any length $m, 1\leq m \leq P$ there is no valid division $s' = xyz, y = 0^m$ (valid means it fulfils the conditions of the pumping lemma).

So for every such $m$, we need an $i$ such that: $xy^iz = x0^{im}z = 0^{a-m+im}1^b = 0^{a+(i-1)m}1^b {! \atop =} 0^b1^b$. This means that $m$ must divide $b-a$ for every $m$. One number $b-a$ that fulfils this, is $P!$, so e.g. $a=P$, $b=P+P!$, the least common multiple of $1,\dots,m$ is another possible choice for $b-a$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9958