gotchaMinor
Why does this Pumping Lemma example show irregularity?
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
3) Let the string
4)
5) But since condition 3 of the pumping lemma says that
How does step 5 justify
How does this make y only zeros?
Thanks!
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.
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.