So I'm trying to do this sort of problem that says: Demonstrate that a language conformed by binary numbers of Fibonacci length, is not a regular language.
I really don't know how to approach it nor am I sure if I understand it.
The language of binary numbers whose lengths are Fibonacci numbers can be shown irregular by either the pumping lemma or the Myhill-Nerode theorem.
For the pumping lemma, take any string 0^p where p is the pumping length. No matter which substring of this you consider, you get a contradiction in fairly short order (for p > 1, it is never the case that p - a, p and p + a are all Fibonacci numbers. Proof of that fact is by reference to the definition of Fibonacci numbers.
For the Myhill-Nerode theorem proof, simply show that for any string x whose length is the nth Fibonacci number, the smallest non-empty strings that can be appended to get more strings in the language have lengths equal to the (n-1)th Fibonacci number. Therefore, there are infinitely many distinguishable strings and, therefore, the language is not regular (since a minimal DFA, which has one state per equivalence class under the indistinguishability relation, must have finitely many states).