# Tag Info

## New answers tagged pumping-lemma

4

This answer is a simpler version of Colin McQuillan's answer to the same question. Suppose the language is regular. The pumping lemma gives strings $u,v,w$ such that every string $x_n=u v^n w$ is a power of $2$. Interpreting these strings as numbers and writing $d$ and $e$ for the lengths of $v$ and $w$ respectively, we have $$x_n = u 3^{dn+e} + v 3^{d(... 0 You can prove it by carefully picking w and a bit of counting. Let q be the first prime greater than or equal to p, and let w = d^{q} (the as and bs are really a bit of a red herring - here we're just choosing n=k=0 to get rid of them). Then by the rules of the pumping lemma, y = d^{t} for some 1 \leq t \leq p \leq q. We can then pump up ... 1 Helpful property of prime numbers: The gaps between consecutive prime numbers become arbitrarily large. That means for every r, there is a prime p such that none of the numbers p+1 to p+r are primes. That means a^nd^mb^k is not in the language for p+1 ≤ m ≤ p+r. That would generally work for "m is a member of an infinite set with arbitrarily large gaps ... 0 You could argue with a reasonably straight face that L is not well-defined, since it supposedly contains the word a^0ba^{-1}, so L wouldn't be a language at all, therefore not a regular language and not an irregular language either. If you change it slightly to$$ L = \{ w: w = a^k b a^{m-1} \mid k,m \in \mathbb{N} \}  then it is definitely regular; ...

Top 50 recent answers are included