2
$\begingroup$

I have had some difficulties understanding proofs that a language is not regular using the Pumping Lemma, and now I need to prove that the following language

$$A = \{w \mid \text{ w has even length and the first half of w has more 0s than the second half of w} \}$$

is not regular.

I would start by assuming that $A$ is regular, and then I should pick a string in $A$ that for a certain $p$ (pumping length) would contradict the assumptions, i.e. $A$ is regular.

I think I first need to choose a string $s$, which of course must have even length, and the first part of that string must contain more $0$s than the second part. For example, $0001$ would be a string in $A$.

The length of $s$ must be greater or equal to $p$. Moreover, $s$ can be divided into three pieces, like $s = xyz$.

Now, how would I choose $s$? I saw that some proofs make $s$ depend on $p$. Is this strictly necessary, or is this just convenient, and why?

Could you please help me proceeding with the proof?

$\endgroup$
2
$\begingroup$

Defining $s$ partly in terms of $p$ is an easy way to ensure that $|s|\ge p$; this is necessary if we are to apply the pumping lemma. It also gives us some control over what the part $xy$ of the $xyz$ decomposition will look like.

Here I would start with an $s$ that just barely satisfies the condition putting it in $A$: $s=0^p10^{p-1}$. If $A$ were regular, there would be a decomposition $s=xyz$ such that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in A$ for each $k\ge 0$. Since $|xy|\le p$, we know that $xy$ is a string of zeroes: it’s part of the initial substring $0^p$ of $s$. Thus, there are $i,j$ such that $x=0^i$, $y=0^j$, $i+j\le p$, $i\ge 0$, and $j\ge 1$. (We know that $j\ge 1$, because $j=|y|\ge 1$.) This means that $z=0^{p-(i+j)}10^{p-1}$, and our decomposition is

$$s=x\color{red}y\color{blue}z=0^i\color{red}{0^j}\color{blue}{0^{p-(i+j)}10^{p-1}}\;.$$

Now what does $xy^kz$ look like for $k\ge 0$? It’s

$$xy^kz=0^i(0^j)^k0^{p-(i+j)}10^{p-1}=0^{i+kj+p-i-j}10^{p-1}=0^{p+(k-1)j}10^{p-1}\;.$$

In particular, when $k=0$ it’s $xz=0^{p-j}10^{p-1}$, where $j\ge 1$. Can you see why this word cannot be in $A$?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Well, $0^{p - j}$ will have the same or less number $0$s than $0^{p - 1}$ (but it should have more). I don't know how you came out with this proof, but it is amazing. Does it take you much time to write this kind of proofs (just for curiosity)? I know I am quite new to these kind of things, but your reasonings are so superb. $\endgroup$ – nbro Nov 15 '15 at 22:24
  • 1
    $\begingroup$ @nbro: Part of it is experience: I know what sorts of things to look for. Here I see that $A$ requires the first half of the word to have lots of zeroes, and I know that the pumping lemma will let me alter the first half of the word, so my first thought is to try to use it to make the number of zeroes in the first half too small. This will be easiest if the number of zeroes in the first half is only just barely large enough, so I started with a word in which that was the case. (Beginners often forget about the $k=0$ case, which lets you shrink the front end of the word.) $\endgroup$ – Brian M. Scott Nov 15 '15 at 22:28
  • $\begingroup$ I forgot also to mention that, e.g., if $j = 1$, then $0^{p - j} 1 0^{p - 1}$ has odd length... $\endgroup$ – nbro Nov 15 '15 at 22:56
  • $\begingroup$ @nbro: True, though that just means that if $A$ were regular, there would always be an acceptable decomposition with $j$ even. Thus, you can’t count on destroying the evenness of the length, but you can count on making the first half of the word have too few zeroes. $\endgroup$ – Brian M. Scott Nov 15 '15 at 23:02
1
$\begingroup$

Yes this can language can be proven not regular using the pumping lemma. The strongest statement of the pumping lemma will work: if $L$ is regular, then there is a $p$ (equal to the number of states in a DFA accepting $L$), such that for any string $s\in L$, any substring $r$ of $s$ of length $\ge p$ has substrings that can be pumped. The proof is the same: given any substring $r$ of $s$ with $\lvert r\rvert\ge p$, the states that the DFA must traverse when "processing" $r$ are $p+1$ in number, so there must be repetition.)

If the $L$ in question were regular, let $p$ be the length given by the pumping lemma, and consider $s=0^{p+1}1^p$. Then $s\in L$. But some substring of the $1$s can be pumped, and the resulting strings will be in $L$. But clearly that's not true: the "pumped-up$ strings won't satisfy the definition of the language.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.