Use the Pumping Lemma to prove that the following language on $\Sigma = \left \{ 0,1 \right \}$ is not regular.
$L = \left \{ w \, | \, w \mbox{ has the same numbers of 0 and 1} \right \}$
not in any particular order.
I post here two developments, my own one, and another taken from my book where I don't understand some part. I hope you can help me.
. First development. – This is my own development:
1) Assume $L$ regular;
2) Let $N$ a constant for the $PL$;
3) We consider a string $z$ long enough with $\left | z \right | \ge N$;
4) We try to find a counter-example:
I have considered this string as included in the $L$.
$z = 0^N1^N \in L$
5) Assume that $z$ can be break up in:
$z = uvw$,
so the following restrictions are applicable on $z$:
$(i) \left | uv \right | \le N \\ (ii) \left | v \right | \ge 1$
Considering our string $z = 0^N1^N$, $0^N$ is just the string $uv$, since its length is at most $N$, and $0^N$ has a length equal to $N$. Also $v$ consists of $0$s with a length of at least 1.
i.e.:
$u = 0^i \quad v = 0^j \\ uv = 0^{i+j} \quad \mbox{with } \quad i+j \le N, \quad i \ge 1, \quad j \ge 0$
but, here in our string $i+j$ is just equal to $N$. So, $i+j = N$;
6) Now we take a pumping with $k \ne 1$. We consider $k = 2$:
$\begin{array}{lcl} z & = & uv^2w \\ & = & uvvw \\ & = & (0^{i+j})vw \\ & = & (0^{i+j})0^jw \\ & = & 0^{i+j+j} \\ & = & 0^{N + j}w \\ & = & 0^{N+j}1^N \end{array}$
here $uv^2w$ contains the first $N+j$ concatenation of the symbol $0$, while the remaining $1$ symbols remain $N$.
It follows that $uv^2w$ can't be in $L$, and $L$ it is not regular.
This is my own development but, the way I described the language, seems that it contains only strings as $\left \{ \epsilon, 01, 0011, 000111, \ldots \right \}$, and not strings as $\left \{ \epsilon, 01, 10, 0011, 1001, 1010, 1100, 000111, \ldots \right \}$. Or is it the same reasoning for both languages?
. Second development. – The example is taken from the book I use (the book is: Hopcroft – Introduction to Automata Theory Languages and Computation 2nd ed. – Example 4.2, page 128).
The first part that I think I have understand, I have written with my own words, instead, I will quote the second part, since it is the part I don't understand, so:
Suppose L regular and consider the constant $n$ of the Pumping Lemma;
We consider the string $w = 0^n1^n \in L$;
Considering the Pumping Lemma, we can break up the string as $w = xyz$, with
$y \ne \epsilon \\ \left | xy \right | \le n$
$\left | xy \right | \le n $, i.e. the length of $xy$ must be at most $n$, but, then, $xy$ is the part of the string that it is on the beginning of $w$, in fact we know that $x$ and $y$ are formed by only $0$;
The PL tells us that $xz \in L$, if $L$ is regular, and this is the case with $k = 0$:
$\begin{array}{lcl}w & = & xy^0z \\ & = & xz \end{array}$
i.e. there are $n$ concatenations of the symbol $1$ in $z$, but, there will be less symbols $0$ (the concatenations of the symbol $0$ will be not equal to $n$), because, thay are contained all within $xy$, but now we have $y^0 = \epsilon$
I think that so far I have done well, however, this is the part, the fina part, of the example of the book I don't understand, I quote it:
Since $y \ne \epsilon$ we know that there can be no more than $n-1$
$0$'s among $x$ and $z$. Thus after assuming $L$ is a regular language
we have proved a fact known to be false, that $xz$ is in $L$. We have
a proof by contradiction of the fact that $L$ is not regular.
Please, can you tell me what do you think about my developments? And also, can you help me to understand the part quoted from the book? Many thanks for your great patience!
Best Answer
Assume that $L$ is regular and take $w = 0^n1^n \in L$. By the Pumping Lemma, we can write $w = xyz$ where $y \not = \epsilon$, $|xy| \leq n$, and $xy^iz \in L$ for all $i \geq 0$. Now, because $|xy| \leq n$, we must have $xy = 0^k$ for some $k \leq n$, and because $y \not = \epsilon$, this implies that $y = 0^j$ for some $0 < j \leq k$, or in other words, $y$ consists only of $0$'s.
Now we "pump down" by seeing what happens when $i = 0$. $xy^0z = xz$, and since $y = 0^j$, we must have $xz = 0^{n - j}1^n$, with $n - j < n$. But then there are less $0$'s than $1$'s in $xz$, so $xy^0z \notin L$, which contradicts the fact that $xy^iz \in L$ for all $i \geq 0$. Hence we conclude that $L$ is not regular.