3
$\begingroup$

I am trying to prove $L =$ {${a^k|k=2^n, n \ge 0}$} is not regular. So far I have identifed a string $s = a^{2^p}$, and I've divided $s$ into $xyz$ as follows:

$x = a^l$

$y = a^k$

*(where $k + l \le p$)

$z = a^{2^p-l-k}$

Now, when I start to look at pumping, I first select $i=0$:

$xy^iz = xy^0z = xz = a^la^{2^p-l-k}=a^{2^p-k}$, which is clearly not equivalent to $a^{2n}$. However, I know that there are mistakes in this proof and I have been told that my division of the string $s$ into $xyz$ does not account for all divisions. Could anyone please help?

$\endgroup$
4
$\begingroup$

For reference, the pumping lemma is (from Introduction to the Theory of Computation by Michael Sipser)

If $A$ is a regular language, then there is a number $p$ (the pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:

  1. for each $i ≥ 0, xy^i z \in A$,

  2. $|y| > 0$, and

  3. $|xy| \le p$.

When you want to prove that a language is not regular using the pumping lemma, you use a proof by contradiction. You first assume that the given language is regular.

As per the pumping lemma, given a regular language, there exists a number $p$ such that for all $s$ with length at least $p$, there exists a way to partition it in the form $x,y,z$ such that all the three conditions hold.

The contrapositive is

For all $p\ge1$, there exists a string $s$ with length at least $p$, such that for all ways to partition $s$ in the form $x,y,z$, at least one of the three conditions are false, implies that the language is not regular.

So, to show that $L$ is not regular, you need to show that the appropriate quantifier (existential or universal) for each entity is used correctly.

Initially, you have taken a value $p$, with no assumption. This is in accordance with for all $p$.

Then, you have chosen a string $s$ with length at least $p$. This is in accordance with there exists a string $s$, i.e., a single instance of a string satisfying the rest of the statement is sufficient.

Now, you need to consider all ways of partitioning $s$ in the form $x,y,z$, and show that always, at least one of the three statements of the lemma is false.

So, you have partitioned it into $x=a^l, y=a^k, z=a^{{2^p}-l-k}$. As of now, there are no assumptions on the values $l$ and $k$ can take, except that they are non negative, which is as required. To force a contradiction, you need to try to show that all the statements of the lemma do hold. Statement 2 states that $|y|\gt0$. So, if it were true, we must have $k\gt0$. Statement 3 states that $|yz|\le p$. If it were true, we must have $k+l\le p$.

Finally, Statement 1 must be true if $L$ is regular, so $xy^iz\in L$ for all $i\ge0$ must be true. It is sufficient thus to show that it is false for any one value of $i$. I choose $i=2$. So, we must have $a^la^{2k}a^{{2^p}-l-k}=a^{{2^p}+k}\in L$ for all possible values of $l$ and $k$ except as per the previously imposed restrictions.

Now, we have $$k\gt0\implies k\ge1$$ $$2^p+k\ge 2^p+1\gt 2^p\tag1$$

$$k+l\le p$$ But $l\ge 0$, so we have $$k\le p$$ $$2^p+k\le 2^p+p\tag2$$

But we have $$p\lt 2^p$$

for all $p\ge 1$, which is the set of all allowed values of $p$. So, $(2)$ becomes, $$2^p+k\le 2^p+p\lt 2^p+2^p=2^{p+1}\tag3$$

From $(1)$ and $(3)$,

$$2^p\lt 2^p+k \lt2^{p+1}$$

As $2^p+k$ lies strictly between consecutive powers of $2$, it cannot be a power of $2$ itself. So, $a^{2^p+k}\notin L$, and we have a contradiction as desired.

Thus, $L$ is not regular.


In your proof, the initial steps are all correct, all you need to do is to show why the string cannot lie in the language, using an appropriate value of $i$, as shown in this answer. Moreover, choosing $i=0$ is not straightforward. For $i=2$, I argued that $2^p\gt p$. For $i=0$, you will need to use $2^{p-1}\gt p$, which is not true if $p=1$.

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