2
$\begingroup$
  1. $L=\{a^n b^m:n\neq m\}$

  2. $L=\{a^n b^l c^k :k\neq n+l\} $

Can we take in case 1 $w=0^{2p}1^p$?

But my resource says that, we need to take $w=0^{p}1^{p+p!}$

Similarly in case 2, I want to take $w=a^p b^p c^{3p}$

but my resource, item 23 as shown below says that we need to take something else. $w=a^{p!}b^{p!}c^{(p+1)!}$

enter image description here

I guess that $a^{(p+1)!}$ is for c.

I have the proof, so please don't bother doing the proof, I just want to know if we can choose different values like I said? I know we can't, but I don't know the reasoning behind it.

$\endgroup$
1
  • $\begingroup$ Your resource has never said the choice it made is the only valid/working one. For example, item 21 chooses $a^{p!}b^{p+1)!}$ instead of $0^{p}1^{p+p!}$ (imagine $a$ is $0$ and $b$ is $1$). "Let us choose" there sounds like a cordial suggestion instead of a must-follow requirement. $\endgroup$
    – John L.
    Apr 21, 2022 at 18:41

3 Answers 3

3
$\begingroup$

I have the proof, so please don't bother doing the proof, I just want to know if we can choose different values like I said? I know we can't, but I don't know the reasoning behind it.

Yes, we can.

The pumping lemma states that for every regular language $L$, there exists a pumping length $p$ such that every $s \in L$ with $|s| \geq p$ can be partitioned into $xyz$ such that $xy \leq p$, $|y| > 0$ and $xy^iz \in L$ for all non-negative integers $i$.

This means, on a principal level, you can start a pumping lemma proof of non-regularity with any string in $L$, as long as its length is at least $p$, so none of the strings in your question are obviously invalid. However, you might not be able to complete the proof with any given string.

For example, for the language $L = \{0^n 1^m : n \neq m\}$ you won't get far with $0^{2p}1^p$. We can simply set $x = \epsilon$, $y = 0$ and $z = 0^{2p-1}1^p$. This will only break the conditions of the lemma when $p = 1$, but this caveat changes little since it's just possible 1 isn't a valid pumping length for the language.

The factorial trick used in the source you cite ensures the number of $0$ and $1$ will align for large enough $i$ no matter the choice of otherwise-legal $xyz$, proving the three conditions cannot be satisfied. To illustrate, suppose we have some partition where $y = 0^n$ with $1 \leq n \leq p$. This means $xy^1z$ begins with $0^p$, $xy^2z$ begins with $0^{p+n}$, $xy^3z$ begins with $0^{p+2n}$ etc. More generally, the number of leading zeroes in $xy^iz$ is $p+(i-1)n$. Meanwhile, the number of trailing ones is $p + p!$. Subtract $p$ and divide by $n$: the equation will be satisfied when $i = 1 + \frac{p!}{n}$.

However, in general, the important take-away is that there is no particular "magic string" you must use. Any string that can be used to create the necessary contradiction works, some are just easier to use than others and some might not work at all.

$\endgroup$
3
$\begingroup$

The negation of "pumpable" as described in the pumping lemma states:

for all n
exists w in L with |w| > n
for all...
exists...
for which...

You can choose that w freely as long as it has at least length n as there often is more than one combination that satisfies this. Your resource can only demonstrate the solution for one specific instance.

$\endgroup$
0
$\begingroup$

Yes, you can choose different strings of length at least $p$ (where $p$ is the constant given in the pumping lemma) than the one given in the resource; however, not all strings will help you complete the proof. In particular, the string $0^{2p} 1^p$ in the first example, and the string $a^p b^p c^{3p}$ in the second example, will not work (i.e. will not push the proof through).

We need to start with a string in $L$, and then pump it to obtain a string not in $L$. But your choices of strings don’t achieve this objective. For the string $0^{2p}1^p=xyz$, $y$ is a string containing one or more $0$’s, and any pumped string such as $xyyz$ or $xyyyz$ would continue to have more $0$’s than $1$’s and hence belong to $L$. In the case of a string $S=a^p b^p c^{3p} \in L$, if $p=3$, then $S=a^3 b^3 c^9$, and if $y=aa$, then all pumped strings continue to belong to $L$ because $a^1 b^3 c^9, a^3 b^3 c^9, a^5 b^3 c^9, a^7 b^3 c^9 \in L$.

Recall that your adversary gets to choose the value of $p$. Your adversary also gets to choose the value of $|y|$. In the proof given in your resource, this length $|y|=m$ was not assumed to be a fixed value but could be any value between $1$ and $p$ (inclusive), and the proof still went through because it was shown that one of the pumped strings did not belong to $L$.

To understand this better, you can work out the proof of the pumping lemma from scratch, using the pigeonhole principle. Given a language $L$ (that you want to prove is nonregular), by way of contradiction, suppose there exists a DFA with $p$ states accepting $L$. Let $S$ be any input string of length at least $p$. Then, by the pigeonhole principle the first $p+1$ states that the DFA visits for this input string must have a repetition, and the first substring of $S$ that takes the machine from this repeated state to itself is the substring $y$. Any pumped version of the string would also take the machine to the same accepting state and hence must also be accepted by the machine. You need to prove that there exists a pumped version of the input string that is not in the given language. You don’t get to choose the length of $y$, you can only be sure that the part of the input up to and including $y$ has length at most $p$, and that $y$ has length at least $1$.

To summarize: given a language $L$ that you want to prove nonregular, your adversary gets to choose $p$, you get to choose $S$ (based on $p$) to be any string in $L$, your adversary can choose how to partition $S$ as $xyz$ (subject to the constraint $|xy| \le p, |y| = i\ge 1$), and you get to show that there exists an $i$ such that $xy^iz \notin L$. This proves that there does not exist a machine with $p$ states accepting $L$, for any arbitrary $p$. You showed that for every machine with $p$ states, there is some string $S$ that cannot be pumped.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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