1
$\begingroup$

I'm currently trying to show that the language $L_2=\{0^n \text{ } | \text{ } n=2^k, k\geq 0\}$ is not regular by using the Pumping Lemma (at least I think it is not regular, because I couldn't find any regular expressions or DFA for it). I know all the steps that I need to go through, but I am having a very hard time figuring out which specific $z\in L_2$ I need to use. I tried using $z=0^{2n}=0^{2^{k+1}}$ and $z^{2^n}$, but I had no luck.

Do you think I'm doing something wrong and using the wrong z's or are the above two okay to work with, but I'm just not comprehending it?

$\endgroup$

2 Answers 2

0
$\begingroup$

We want to show that the language $L_2 = \{0^n: n=2^k, k \ge 0\}$ is nonregular. By way of contradiction, suppose $L_2$ is regular. Let $p$ be the pumping length. Let $z = 0^{2^p}$. Then, $z \in L_2$ and $|z| \ge p$. Let $z=abc$ be a partition of $z$ such satisfying $|ab| \le p, |b| \ge 1$. Observe that $2^p < |abbc| \le 2^p + p < 2^p + 2^p = 2^{p+1}$, whence $abbc \notin L_2$, a contradiction.

$\endgroup$
1
  • $\begingroup$ Thank you for providing the answer. I did reach the same conclusion, as this was for material in my previous semester, so I'm glad to know I did it correctly. $\endgroup$
    – Tita
    May 30, 2022 at 22:20
0
$\begingroup$

If $n$ is the pumping length and $m = 2^{\left\lceil \log_2 n\right\rceil}$ ($m$ is the smallest power of $2$ greater than $n$), then $z = 0^m$ should do the trick. You need to show that if $z = uvw$ is the pumping decompositon, then one of $uw$ or $uv^2w$ is not in $L_2$.

$\endgroup$
3
  • $\begingroup$ I understand how you got m, but I'm having trouble understanding how that number can be the length of any z. Since we can only have integer lengths... This should stand for any $n\in \mathbb{N}$, so already for n=3 with m we already have a problem, since it is not an integer. How can I generalize for m, when it is not always int? Or does it not matter? $\endgroup$
    – Tita
    Dec 19, 2021 at 16:23
  • $\begingroup$ I am not sure I understood what your problem is… Since $\left\lceil \log_2 n\right\rceil$ is an integer, so is $m$. What do you want to generalize? For example, if $n = 3$, then $m$ is equal to 4. $\endgroup$
    – Nathaniel
    Dec 19, 2021 at 16:38
  • $\begingroup$ Oh, I didn't realize you used ceiling brackets! $\endgroup$
    – Tita
    Dec 19, 2021 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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