1
$\begingroup$

I just learned pumping lemma this week and got confused on this question.

B={$a^{fn}$ | $f_n$ is a Fibonacci number} for $a \in Σ$.

Hint: the sequence of Fibonacci numbers get increasingly further apart.

I am trying to prove this is not regular using pumping lemma, but 'Fibonacci numbers get increasingly further apart' seems really tricky when I try to pump up to prove it's not $\notin$ B.

$\endgroup$
1
$\begingroup$

Suppose that $B$ were regular. According to the pumping lemma, there exists an integer $p \geq 1$ such that every word $w \in B$ of length at least $p$ has a decomposition $w = xyz$, with $|xy| \leq p$ and $y \neq \epsilon$, such that $xy^tz \in B$ for all $t \geq 0$.

Pick some Fibonacci number $F_n$ such that (1) $F_n \geq p$ and (2) $F_{n+1} - F_n > p$. Then $1^{F_n} \in B$ has length at least $p$, and so it can be decomposed as $1^{F_n} = xyz$, where $|xy| \leq p$ and $y \neq \epsilon$, and $xy^2z \in B$. But $xy^2z = 1^m$, where $F_n < m \leq F_n + p < F_{n+1}$.

| cite | improve this answer | |
$\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.