Why does this Pumping Lemma example show irregularity?

Question

the first 4 steps of these are my own work - however the following steps are from my book, and I don't understand what it's saying, and I have not found any resources. Could someone clarify this?

Show C = {w|w has an equal number of 0s and 1s} is not regular. Show by contradiction.

1) Assume C is regular, and thus the Pumping Lemma conditions hold.

2) Assume a pumping length of p.

3) Let the string s = $0^p$$1^p$.

4) s = xyz and let x and z be the empty string. Therefor for i > 0, x$y^i$z always has an equal number of 0s and 1s, so it seems like it can be pumped.

5) But since condition 3 of the pumping lemma says that |xy| <= p, then y must consist of only 0s.

How does step 5 justify y consisting of only zeros? If we said ealrier that x and z are the empty strings, then doesn't that imply that s = y = $0^p$ $1^p$?

How does this make y only zeros?

Thanks!

Answer 1

$s$ consists of $p$ zeroes followed by, well, it doesn't matter what. $xy$ is the start of $s$ and consists of at most the first $p$ characters of $s$. All of those $p$ characters are zeroes so, in particular, $y$ is all zeros.

Step 4 of your proof is invalid because you can't choose what $x$ and $z$ are. The pumping lemma tells you that, if $C$ is regular, there is some way of writing every appropriate $s\in C$ as $s=xyz$ such that blah, blah, blah. It doesn't tell you that writing $s=\varepsilon y\varepsilon$ will work.

Answer 2

You cannot proceed in this way. The Pumping Lemma for regular languages tells us that if a language $L$ is regular, then there exists a $p \geq 0$ such that every $s \in L$ such that $\lvert s \rvert \ge p$ can be partitioned as $s = xyz$ in such a way that

1. $|y| > 0$
2. $|xy| \leq p$
3. $xy^iz \in L$ for all $i \geq 0$

To show that a language $L$ fails to be regular, we must show that for any choice of $p$ we can find an $s \in L$ such that every possible partition of $s$ will violate one or more of the above three conditions.

In your attempted solution, your candidate string has length $2p$. Condition 2 tells us that $y$ must occur within the first $p$ symbols and must therefore consist of $0$s only.

If condition 1 is to also hold, $y$ must be non-empty. But then $xy^2z \notin L$, as this string will have more occurrences of $0$s than of $1$s. So condition 3 cannot hold, if we require conditions 1 and 2 to hold.

Your misunderstanding is one that students often make; they assume that the partition must be one that somehow "magically pairs off" the symbols according to its shape: If the candidate string has a part consisting of $0$s followed by a part consisting of $1$s, then the initial substring $x$ must somehow consist of all the $0$s. This is not the case. That you then also assume that $x$ is empty, shows an internal contradiction: At the same time you claim that $x$ must consist of all $0$s and that $x$ can be chosen to be any string whatsoever, in this case the empty string.

Answer 3

We cannot assume $x$ and $z$ to be empty strings. It can be understood as follows: If we try and construct the automaton there has to be some part of the string which leads it to the final state from the state which contains loops.

for further reference refer to this post: In context of pumping lemma for regular languages .

By taking proper assumptions we can see that $|xy| \leq p$ which implies $xy$ can contain only zeroes, so pumping $y$ will create a string which has more zeroes than ones.

Answer 4

I's easy to understand the pumping lemma if you see where it comes from.

Assume L is regular, so there is a finite state machine. Say that state machine has p-1 states. That's where the p comes from.

Now parse any string of length p or more that is in the language. Since there are only p-1 states, somewhere within parsing the first p characters of the string you must enter some state S twice.

Let x be the string that gets you to state S for the first time (x could be an empty string if S is the initial state). Let y be the string that gets you from S back to S (y has a length > 0, the length of x + y is less than p). z is the rest of the string starting with S. If you repeat y as often as you like, the FSM will take you back to S again and again every time you repeat S. So $x y^n z$ is an element of L for every n ≥ 0.

Answer 5

Suppose C is a regular language and let P be the 'pumping length'.Consider the string S = a^Pb^P. Note that S ε C and |S| = 2P ≥ P, so the pumping lemma will hold. Then as you stated we have to divide the string in to 3 parts xyz. The idea behind this is to split the whole string into parts in such a form that 'part' of it can be pumped or repeated more times and even then the language string will be regular(This is explained by the condition xyⁱz ε C for all i ≥ 0).

The automation requires an initial state and a final state to end(we consider acceptor and not transducer ). So we cannot simply assume x and z both as 0.

So here we have to take P in such a way that it satisfies the condition for pumping lemma and we can conclude that it contains only P characters which in turn contains only 0's here. Eg: take P = 3, then S = aaabbb, split S into xyz in such a way that |y| > 0 and |xy|≤ P. Since the first 3 symbols of S are all a's and z forms the rest of the string. say |x| = 1 and |y| = 2 then |z|= 3. After this if for xyⁱz, take i = 2, you will get the string 'aaaaabbb' which is not in string S and hence by contradiction its not a regular language.