## Attachment 'Automata and Transducers in SageMath.rst'

import sage.combinat.finite_state_machine
sage.combinat.finite_state_machine.FSMOldProcessOutput = False
sage.combinat.finite_state_machine.FSMOldCodeTransducerCartesianProduct = False

System Message: WARNING/2 (<string>, line 7)

Explicit markup ends without a blank line; unexpected unindent.

### Automata and Transducers in SageMath

#### Digit Expansions

• decimal system: base 10, digits 0, 1, ..., 9
• binary system: base 2, digits 0, 1
• base 2, digits -1, 0, 1 --> redundancy
• no consequtive non-zero digits in expansion
• examples
• 3 = 1 + 2 = (1 1)2 (standard binary) ... not a NAF
• 3 = -1 + 4 = (-1 0 1)2 ... a NAF

#### Creating a Transducer from Scatch

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
view(NAF)
14.digits(base=2)
NAF(14.digits(base=2))
NAF.process(14.digits(base=2))
NAF(14.digits(base=2) + [0, 0, 0])
NAF = NAF.with_final_word_out(0)
NAF(14.digits(base=2))

System Message: WARNING/2 (<string>, line 59)

Explicit markup ends without a blank line; unexpected unindent.

#### Calculating the Non-adjacent Form with Less Thinking

def NAF_transition(state_from, read):
if state_from == 'I':
write = None
return (state_to, write)
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
NAF2(14.digits(base=2))

System Message: WARNING/2 (<string>, line 88)

Explicit markup ends without a blank line; unexpected unindent.

#### A 3rd Construction of the Same Transducer

• (NAF of 2n) = (binary of 3n) – (binary of n)
def f(state_from, read):
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
Triple(4.digits(base=2))
Id = Transducer([(0, 0, 0, 0), (0, 0, 1, 1)],
initial_states=[0], final_states=[0],
input_alphabet=[0, 1])
prebuiltId = transducers.Identity([0, 1])
Combined_3n_n = Triple.cartesian_product(Id).relabeled()
Combined_3n_n
Combined_3n_n(4.digits(base=2))
def g(read0, read1):

Minus = transducers.operator(g, input_alphabet=[None, -1, 0, 1])
prebuiltMinus = transducers.sub([-1, 0, 1])
NAF3 = Minus(Combined_3n_n).relabeled()  # compositions of transducers
NAF3(14.digits(base=2))

System Message: WARNING/2 (<string>, line 138)

Explicit markup ends without a blank line; unexpected unindent.

#### An Automaton detecting NAFs

view(NAF)
A = NAF.output_projection()
A
A([0])
A([0, -1, 1])
A([1, 0, 1])
view(A)
A = A.split_transitions()
A
A.is_deterministic()
A.determine_alphabets()
A = A.minimization().relabeled()
A
A.is_deterministic()

System Message: WARNING/2 (<string>, line 175)

Explicit markup ends without a blank line; unexpected unindent.

#### Combining Small Transducers to a Larger One: The 3/2-1/2-NAF

NAF = NAF3
NAF3n = NAF(Triple)  # composition
Combined_NAF_3n_n = NAF3n.cartesian_product(NAF).relabeled()
T = Minus(Combined_NAF_3n_n).relabeled()  # composition
T
T(14.digits(base=2))
def value(digits):
return sum(d * 2^(e-2) for e, d in enumerate(digits))
value(T(14.digits(base=2)))

System Message: WARNING/2 (<string>, line 193)

Explicit markup ends without a blank line; unexpected unindent.

#### Again an Alternative Construction

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

System Message: WARNING/2 (<string>, line 214)

Explicit markup ends without a blank line; unexpected unindent.

#### Getting a Picture

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)

System Message: WARNING/2 (<string>, line 246)

Explicit markup ends without a blank line; unexpected unindent.

#### Weights

def weight(state_from, read):
return (0, write)

Weight = Transducer(weight, input_alphabet=srange(-2, 2+1),
initial_states=[0], final_states=[0])
Weight
prebuiltWeight = transducers.weight(srange(-2, 2+1))
NAF = NAF2  # reset since modified above
W_binary = Weight(Id)
W_NAF = Weight(NAF)
W_T = Weight(T)
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))

System Message: WARNING/2 (<string>, line 274)

Explicit markup ends without a blank line; unexpected unindent.

var('y')
def am_entry(trans):
W_T.adjacency_matrix(entry=am_entry)

System Message: WARNING/2 (<string>, line 283)

Explicit markup ends without a blank line; unexpected unindent.

#### Asymptotic Analysis

var('k')
W_binary.asymptotic_moments(k)
W_NAF.asymptotic_moments(k)
W_T.asymptotic_moments(k)

## Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.
• [get | view] (2015-03-31 18:16:36, 14.4 KB) [[attachment:Automata and Transducers in SageMath.ipynb]]
• [get | view] (2015-03-31 18:16:32, 125.8 KB) [[attachment:Automata and Transducers in SageMath.pdf]]
• [get | view] (2015-03-31 18:16:27, 7.1 KB) [[attachment:Automata and Transducers in SageMath.rst]]
• [get | view] (2015-03-31 18:16:20, 3.0 KB) [[attachment:Automata and Transducers in SageMath.sws]]
• [get | view] (2015-04-03 10:14:45, 233.9 KB) [[attachment:Catch and prevent bugs in computer algebra systems.pdf]]
• [get | view] (2015-04-02 09:25:45, 1.1 KB) [[attachment:Channels.sws]]
• [get | view] (2015-04-01 07:52:08, 4.9 KB) [[attachment:Cython part 1.sws]]
• [get | view] (2015-04-02 07:39:44, 30.6 KB) [[attachment:Cython part 2.sws]]
• [get | view] (2015-04-02 09:25:50, 1.3 KB) [[attachment:Encoders_Decoders.sws]]
• [get | view] (2015-04-02 09:25:55, 0.7 KB) [[attachment:Linear_codes.sws]]
• [get | view] (2015-04-02 09:26:05, 0.9 KB) [[attachment:Reed-Solomon.sws]]
• [get | view] (2015-04-13 08:49:02, 1426.0 KB) [[attachment:SD66_pernet.pdf]]
• [get | view] (2015-04-02 09:25:29, 359.6 KB) [[attachment:coding_theory_in_sage.pdf]]
• [get | view] (2015-03-31 14:06:27, 70.5 KB) [[attachment:git and trac.pdf]]
• [get | view] (2015-03-30 11:02:52, 274.2 KB) [[attachment:intro.pdf]]
• [get | view] (2015-03-30 11:03:00, 8.8 KB) [[attachment:intro.rst]]
• [get | view] (2015-03-30 20:47:36, 3.3 KB) [[attachment:parent_element.rst]]
All files | Selected Files: delete move to page copy to page