{{{id=0|
import sage.combinat.finite_state_machine
sage.combinat.finite_state_machine.FSMOldProcessOutput = False
sage.combinat.finite_state_machine.FSMOldCodeTransducerCartesianProduct = False
///
}}}

<h1>Automata and Transducers in SageMath</h1>
<h2>Digit Expansions</h2>
<ul class="simple">
<li><strong>decimal system</strong>: base 10, digits 0, 1, ..., 9</li>
<li><strong>binary system</strong>: base 2, digits 0, 1</li>
<li>base 2, digits -1, 0, 1 --&gt; <em>redundancy</em></li>
</ul>
<h3>Non-adjacent Form (NAF)</h3>
<ul class="simple">
<li>no consequtive non-zero digits in expansion</li>
<li>examples</li>
<li>3 = 1 + 2 = (1 1)2 (standard binary) ... not a NAF</li>
<li>3 = -1 + 4 = (-1 0 1)2 ... a NAF</li>
</ul>

<h2>Creating a Transducer from Scatch</h2>

{{{id=2|
NAF1 = Transducer([('I', 0, 0, None), ('I', 1, 1, None),
                       (0, 0, 0, 0), (0, 1, 1, 0),
                       (1, 0, 0, 1), (1, 2, 1, -1),
                       (2, 1, 0, 0), (2, 2, 1, 0)], 
                      initial_states=['I'], final_states=[0], 
                      input_alphabet=[0, 1])
NAF = NAF1
NAF
///
}}}

{{{id=3|
view(NAF)
///
}}}

{{{id=4|
14.digits(base=2)
///
}}}

{{{id=5|
NAF(14.digits(base=2))
///
}}}

{{{id=6|
NAF.process(14.digits(base=2))
///
}}}

{{{id=7|
NAF(14.digits(base=2) + [0, 0, 0])
///
}}}

{{{id=8|
NAF = NAF.with_final_word_out(0)
///
}}}

{{{id=9|
NAF(14.digits(base=2))
///
}}}

<h2>Calculating the Non-adjacent Form with Less Thinking</h2>

{{{id=11|
def NAF_transition(state_from, read):
        if state_from == 'I':
            write = None
            state_to = read
            return (state_to, write)
        current = 2*read + state_from
        if current % 2 == 0:
            write = 0
        elif current % 4 == 1:
            write = 1
        else:
            write = -1
        state_to = (current - write) / 2
        return (state_to, write)
    
NAF2 = Transducer(NAF_transition,
                  initial_states=['I'],
                  final_states=[0],
                  input_alphabet=[0, 1]).with_final_word_out(0)
    
NAF == NAF2
///
}}}

<h2>A 3rd Construction of the Same Transducer</h2>
<ul class="simple">
<li>(NAF of 2n) = (binary of 3n) – (binary of n)</li>
</ul>

{{{id=13|
def f(state_from, read):
    current = 3*read + state_from
    write = current % 2
    state_to = (current - write) / 2
    return (state_to, write)
    
Triple = Transducer(f, input_alphabet=[0, 1],
                    initial_states=[0],
                    final_states=[0]).with_final_word_out(0)
Triple
///
}}}

{{{id=14|
Triple(4.digits(base=2))
///
}}}

{{{id=15|
Id = Transducer([(0, 0, 0, 0), (0, 0, 1, 1)],
                initial_states=[0], final_states=[0],
                input_alphabet=[0, 1])
///
}}}

{{{id=16|
prebuiltId = transducers.Identity([0, 1])
///
}}}

{{{id=17|
Combined_3n_n = Triple.cartesian_product(Id).relabeled()
Combined_3n_n
///
}}}

{{{id=18|
Combined_3n_n(4.digits(base=2))
///
}}}

{{{id=19|
def g(read0, read1):
        return ZZ(read0) - ZZ(read1)
    
Minus = transducers.operator(g, input_alphabet=[None, -1, 0, 1])
///
}}}

{{{id=20|
prebuiltMinus = transducers.sub([-1, 0, 1])
///
}}}

{{{id=21|
NAF3 = Minus(Combined_3n_n).relabeled()  # compositions of transducers
///
}}}

{{{id=22|
NAF3(14.digits(base=2))
///
}}}

<h2>An Automaton detecting NAFs</h2>

{{{id=24|
view(NAF)
///
}}}

{{{id=25|
A = NAF.output_projection()
A
///
}}}

{{{id=26|
A([0])
///
}}}

{{{id=27|
A([0, -1, 1])
///
}}}

{{{id=28|
A([1, 0, 1])
///
}}}

{{{id=29|
view(A)
///
}}}

{{{id=30|
A = A.split_transitions()
A
///
}}}

{{{id=31|
A.is_deterministic()
///
}}}

{{{id=32|
A.determine_alphabets()
A = A.minimization().relabeled()
A
///
}}}

{{{id=33|
A.is_deterministic()
///
}}}

<h2>Combining Small Transducers to a Larger One: The 3/2-1/2-NAF</h2>

{{{id=35|
NAF = NAF3
NAF3n = NAF(Triple)  # composition
Combined_NAF_3n_n = NAF3n.cartesian_product(NAF).relabeled()
T = Minus(Combined_NAF_3n_n).relabeled()  # composition
T
///
}}}

{{{id=36|
T(14.digits(base=2))
///
}}}

{{{id=37|
def value(digits):
        return sum(d * 2^(e-2) for e, d in enumerate(digits))
value(T(14.digits(base=2)))
///
}}}

<h2>Again an Alternative Construction</h2>

{{{id=39|
def minus(trans1, trans2):
        if trans1.word_in == trans2.word_in:
            return (trans1.word_in, 
                    trans1.word_out[0] - trans2.word_out[0])
        else:
            raise LookupError
    
from itertools import izip_longest
def final_minus(state1, state2):
    return [x - y for x, y in 
        izip_longest(state1.final_word_out, state2.final_word_out, fillvalue=0)]
    
Talternative = NAF3n.product_FiniteStateMachine(
                           NAF, minus,
                           final_function=final_minus).relabeled()
Talternative == T
///
}}}

<h2>Getting a Picture</h2>

{{{id=41|
sage.combinat.finite_state_machine.setup_latex_preamble()
latex.mathjax_avoid_list('tikzpicture')
T.set_coordinates({
        0: (-2, 0.75),
        1: (0, -1),
        2: (-6, -1),
        3: (6, -1),
        4: (-4, 2.5),
        5: (-6, 5),
        6: (6, 5),
        7: (4, 2.5),
        8: (2, 0.75)})
T.latex_options(format_letter=T.format_letter_negative,
                    accepting_where={
                      0: 'right',
                      1: 'below',
                      2: 'below',
                      3: 'below',
                      4: 60,
                      5: 'above',
                      6: 'above',
                      7: 120,
                      8: 'left'},
                    accepting_show_empty=True)
    
view(latex(T))
latex(T)
///
}}}

<h2>Weights</h2>

{{{id=43|
def weight(state_from, read):
        write = ZZ(read != 0)
        return (0, write)
    
Weight = Transducer(weight, input_alphabet=srange(-2, 2+1),
                    initial_states=[0], final_states=[0])
Weight.add_transition((0, 0, None, None))
Weight
///
}}}

{{{id=44|
prebuiltWeight = transducers.weight(srange(-2, 2+1))
///
}}}

{{{id=45|
NAF = NAF2  # reset since modified above
W_binary = Weight(Id)
W_NAF = Weight(NAF)
W_T = Weight(T)
///
}}}

{{{id=46|
expansion = 14.digits(base=2)
print "binary" , Id(expansion), W_binary(expansion), sum(W_binary(expansion))
print "NAF", NAF(expansion), W_NAF(expansion), sum(W_NAF(expansion))
print "T", T(expansion), W_T(expansion), sum(W_T(expansion))
///
}}}

<h2>Also Possible: Adjacency Matrices</h2>

{{{id=48|
var('y')
def am_entry(trans):
    return y^add(trans.word_out) / 2
W_T.adjacency_matrix(entry=am_entry)
///
}}}

<h2>Asymptotic Analysis</h2>

{{{id=50|
var('k')
W_binary.asymptotic_moments(k)
///
}}}

{{{id=51|
W_NAF.asymptotic_moments(k)
///
}}}

{{{id=52|
W_T.asymptotic_moments(k)
///
}}}