New answers tagged

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