New answers tagged pumping-lemma
4
How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?
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 $a$s and $b$s 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
