Berstel's DFA in Walnut format. Put this in the "Automata Library" directory under the name "berst.txt". {0,1} msd_fib 0 1 0 0 -> 0 0 1 -> 1 1 1 -> 3 1 0 1 0 -> 2 2 0 0 0 -> 1 1 1 -> 1 1 0 -> 0 3 1 0 0 -> 0 The Maple linear representation for Berstel's automaton can be obtained with this command: eval berm y "?msd_fib \$berst(x,y)": This produces the file "berm.mpl" in the "Result" directory. --- The automaton in Figure 3 can be produced with the command reg even1 {0,1} "0*(10*10*)*": def fibeve "?msd_fib \$two1(x) & \$berst(x,y)": and its linear representation by eval fibeven y "?msd_fib \$ber2(x,y)": --- The automaton and linear representation for 0 mod 3 can be obtained as follows: reg three1 {0,1} "0*(10*10*10*)*": def fib3 "?msd_fib \$three1(x) & \$berst(x,y)": eval fib3m y "?msd_fib \$fib3(x,y)": The linear representations for 1 mod 3 and 2 mod 3 can be obtained by modifying the rhs vector as follows: for 1 mod 3: put 1's in positions corresponding to final states 2 and 4 for 2 mod 3: put 1's in positions corresponding to final states 6 and 8 See fib3mm.mpl . Then it has to be minimized. --- The results for mod 4 can be obtained by: reg four1 {0,1} "0*(10*10*10*10*)*": def fib4 "?msd_fib \$four1(x) & \$berst(x,y)": eval fib4m y "?msd_fib \$fib4(x,y)": The linear representation for 2 mod 4 can be obtained by modifying the rhs vector as follows: Then it has to be minimized.