HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMinor

Why does this Pumping Lemma example show irregularity?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thisshowwhyirregularityexamplepumpinglemmadoes

Problem

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!

Solution

$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.

Context

StackExchange Computer Science Q#64021, answer score: 4

Revisions (0)

No revisions yet.