Fibonacci Kleene Star Project

For this project, you need to program a function to decide the language FIB*^* where FIB={w∈[0-9]*:w is the decimal representation of a Fibonacci number}.\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 FIB*\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*L^*

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

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