# Fibonacci Kleene Star Project

For this project, you need to program a function to decide the language FIB$^*$ where $\text{FIB} = \{ w \in [0\text{-}9]^* \, : \, w \text{ is the decimal representation of a Fibonacci number}\}.$

To help write this program, you can use the Python or Javascript code below to decide whether a string is in FIB. Your job is to create a function that inputs a string of digits and determines whether or not the string is in FIB$^*$. I don’t recommend using C++ unless you know of a BigInt library that can handle arbitrarily long integers.

Python code

class Fibonacci:
def __init__(self):
self.sequence = [1,1]
def decider(self,w):
'''By wrapping the decider function for FIB in a class, you can keep track of
previously seen Fibonacci numbers in an attribute called sequence (so this is
a dynamic programming algorithm to decide FIB).'''

# First, convert the string w to an integer n.
n = int(w)

'''If n is larger that the largest previously calculated Fibonacci number,
then add more numbers to the sequence of known Fibonacci numbers until you
find one at least as big as n.'''
while n > self.sequence[-1]:
self.sequence.append(sum(self.sequence[-2:]))

# Then return whether or not n is a Fibonacci number.
return (n in self.sequence)

# To use the Fibonacci class, create a Fibonacci instance.
fib = Fibonacci()

# Then you can use it to decide if strings are in FIB.
print(fib.decider("34")) # True
print(fib.decider("40")) # False
print(fib.decider("40934782466626840596168752972961528246147")) # True

Javascript code

class Fibonacci {
constructor() {
this.sequence = [1n,1n] // Use BigInt type for your numbers.
}
decider(w) {
// By wrapping the decider function for FIB in a class, you can keep track of
// previously seen Fibonacci numbers in an attribute called sequence (so this is
// a dynamic programming algorithm to decide FIB).

// First, convert the string w to an integer n. Use BigInt type.
let n = BigInt(w);

// If n is larger that the largest previously calculated Fibonacci number,
// then add more numbers to the sequence of known Fibonacci numbers until you
// find one at least as big as n.
while (n > this.sequence.at(-1)) {
this.sequence.push(this.sequence.at(-2)+this.sequence.at(-1))
}
// Then return whether or not n is a Fibonacci number.
return (this.sequence.includes(n))
}
}

// To use the Fibonacci class, create a Fibonacci instance.
const fib = new Fibonacci();

// Then you can use it to decide if strings are in FIB.
console.log(fib.decider("34")); // true
console.log(fib.decider("40")); // false
console.log(fib.decider("40934782466626840596168752972961528246147")) // true

Once you have written your function to decide $\text{FIB}^*$, test it on the following input strings.

#### Test 1

“9273726921930789991761500520536206896083277242789322839997508245335957932520658356096176566517218909905236721430926723225558980150346454182850143257664354196444783398182331864069667454273644225850958407065116260306867075373”

#### Test 2

“68330027629092351019822533679447701408733222232244629420445529739893461909967206666939096499764990979600490343046356137747723758225621187571439538669”

#### Test 3

“7345448671578180932349089021104492964233519034304635613774772375822562118757143953866911111460156937785151929026842503960837766832936136661925625699143593954654340236599547388091245916808305705945300883541229581164851348244958539952120672849399056463095319772838289364792345825123228624”

#### Test 4

“4490343046356137747723758225621187571439538669503464541828501432576643541964447833981823357314784401381708410116808305705945300883541229581164851348244958539952120672849399056463095319772838289364792345825123228624”

#### Test 5

“9357314784401381708410186700073985079486580519211311512013440818953365343248661983924214061919432247806074196061300108214549634539075306671478294898814539736941653079531972969696974106192338266867260041627791953052057353082063289320596021103881042195729914708510518382775401680142036775841157140851842754637816784665852418614813344530098755078623770696554372451866815101694984845480039225387896643963981359579325206583560961765665172189099052367214309267232255589801”

#### Test 6

“45397369416530795319729696969741061923382645397369416530795319729696969741061923382635957932520658356096176566517218909905236721430926723225558980135957932520658356096176566517218909905236721430926723225558980157314784401381708410157314784401381708410157314784401381708410157314784401381708410135957932520658356096176566517218909905236721430926723225558980112776523572924732586037033894655031898659556447352249114059301025943970552219131151201344081895336534324866244006547798191185585064349218729154”

The results for the tests should be True, False, True, False, False, True, in that order.

Once you are satisfied with your code, you can e-mail me a copy for 6 points of extra credit on your homework grade (equivalent to 6 extra points or three free problems on any one homework assignment).

If you are having trouble creating the right algorithm, here is a hint.

Hint about algorithm to decide $L^*$

The algorithm to decide if $w \in L^*$ only needs to loop through substrings of $w$ that start at the beginning of $w$.

To decide if a substring that starts at the beginning of $w$ is in $L^*$, just check two things:

• First, is the substring in $L$?
• If not, then is the substring a combination $s+t$ where $s \in L^*$ and $t \in L$?