Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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}$.
