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.