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.