CODEWITHSUNDEEP
fibonacciregular-languagefinite-automata
Weirdo
Weirdo

Reputation: 42

Demonstrating a language is regular

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.

Upvotes: 0

Views: 1356

Answers (1)

Patrick87
Patrick87

Reputation: 28302

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).

Upvotes: 2

Related Questions