Is it possible to divide a string, according to pumping lemma, from a language in a way that pumping a section would render the language -non regular

Question

I understand that pumping lemma can only be used to prove that a certain language is "non-regular", it cannot be used for proving regularity

But since, it's a property of regular language, we should be able to pick up a language that is regular, literally, and then see if this property exists in that language, which should def exist

Let's say our alphabet is { 0, 1 }

Our language L = { w | such that w ends in 11 } or in the form of regex it would be ( 0 + 1 )* 11 ~ basically any string that ends in 11 over the given alphabet

Now, since this is a regular language, if we were to pick up a string that is atleast as large as "number of states" (p) then we should be able to divide the string

Since, a string, atleast as long as 'p', in our mentioned language can be of different forms such as $0^p11$ or $1^p11$ or $(0 + 1)^p11$. Obviously, in the case of proving a language is non regular we just need to show that atleast 1 string fails to adhere to pumping lemma. But in here we are just trying to verify that a certain regular language has the pumping lemma, so in our case all the strings should be in language according to pumping lemma

Now, pumping lemma says that if the language is regular, in our case it is literally a regular language. Then, we should be able to divide a string that is atleast as large as p as follows:

1. $s = xy^iz, where \ i>=0$
2. $|y| > 0$
3. $|xy| <= p$

So, let's assume our string is as follows $s = (01)^{p-2}1$, which is atleast length $p$ and $s$ can be divided as follows: $x= empty \ string \\ y = (01)^{p-2} \\ z = 1$

We can see that the way divided the string in language agrees to condition 2 and 3 but fails to adhere to condition 1:

$s = (01)^{p-2}1 \\ s = xyz \\ s=((01)^{p-2})^{i}1 \\ Now \ we \ will \ try \ to \ pump \ the \ string \ and \ check \ if \ it \ satisfies \ condition \ 1 \\ Put \ i = 0, s = 1\\ $

Hence, s = 1, when we put i = 0, But according to pummping lemma if a languge is regular, which it literally is in our case, then we should just be able to pump the string any number of times even remove that section and still our string should belong to our language

So, if our original laugnage was regular, why did the division and pumping of string failed?

Or is it that i am dividing the string in a wrong way? Like since i do $(01)^{p-2}$ that implies our string has $p-2$ concatenations of $01$, so in order to atleast have a string that is as large as p ~ i need to have 2 more $01$?

In that case since we need to have we can divide the string as follows:

$x = empty \ string \\ y = (01)^{p-2} \\ z = 010111 \ ( because \ we \ need \ the \ prefix \ 11 \ too ) \\ \\ or \ we \ can \ divide \ as \ follows \\ x = 01 \\ y = (01)^{p-2} \\ z = 0111 \\ \\ or \ we \ can \ divide \ as \ follows: \\ x = 0101 \\ y = (01) ^{p-2} \\ z = 11$

And as we can see, in either case of division ~ we do end up having each string in our language. Hence, we can conclude that regular langauges does adhere to a property called "pumping lemma" ( because pumping lemma exists because of regular languages )

Which is it? Was I dividing the string wrong? or is my former logic of string dividing actually correct?

Answer 1

The pumping lemma states that THERE EXISTS a decomposition $s = xyz$ verifying the 3 conditions. Not that the 3 conditions holds for all decompositions $s = xyz$.

That means that you cannot choose the decomposition yourself, you just know that there exists one.

Answer 2

Look at how the pumping lemma is proven.

If L is regular then it has a state machine with k states for some k. If you process a string with k or more symbols, then after processing k symbols, you have visited the start state and k further states, k+1 in total. Since there are only k states, two of these must be the same. Do you have run in a cycle.

Instead of 1 cycle, you could repeat the corresponding symbols 0, 2, 3, 4 or more times, and loop through the cycle 0, 2, 3, 4 or more times. And no matter how often you repeat, you get a string in L.

So you can’t split just any way. You have to split s = xyz so that y is exactly the string going from the start of the cycle back to the start of the cycle.

Answer 3

There are two things that I think is wrong with your example, hence your argument. First the string $s = (01)^{p-1}1$ may not always produce a string from $L = \{ s | \text{ such that } s \text{ ends in 11} \}$ since in the statement for the pumping lemma, $p \ge 1$. So in your case if $p = 1$ then $s$ is just $1$.

Say we fix that and set $s=(01)^p1$. The second mistake that you have is to assign to $y = (01)^p$. Note that the length of $(01)^p$ is $2p$ and not $p$ thus the way you divide $s$ violates the condition that $|xy| \le p$. With this, please note no matter how you divide $s = (01)^p1$, substring $z$ will always have the form $(01)^q1$ where $\lceil p/2 \rceil \le q \le p - 1 $. Therefore, all possible division of $s$ that satisfies the 3 conditions of the pumping lemma will always produce a string that when pumped is in $L$.

If we did not fix your string such that $s$ is still $(01)^{p-1}1$, the argument I have on the preceding paragraph still holds, albeit you have to change the possible value of $q$.

However, as already stated in the previous answer, it is not required for all subdivision of a string that satisfies the 3 conditions to produce a string that when pumped is in $L$. But that does not mean that the language is not regular. Consider again your example regular language, but this time let $s = 1^p1$. Notice that you can now let $x=\varepsilon$, $y = 1^p$ and $z = 1$. Now if you pump it down, $xy^0z$, then the resulting string is just $1 \notin L$. But there exists a subdivision that will: $x=\varepsilon$, $y = 1^{p-1}$, $z = 11$. Every string in $L$ would be like this - there will be a way (not necessarily all way) to subdivide and pump that will generate a string that is in $L$, since $L$ is regular.

The way you use the lemma, as already pointed in the link you commented in the previous answer, to prove that a language $L'$ is not regular, is that you give a string $s \in L'$ and show that all subdivision of $s$ that follows the 3 conditions of the pumping lemma will result to as string not in $L'$.