{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import sage.combinat.finite_state_machine\n",
    "sage.combinat.finite_state_machine.FSMOldProcessOutput = False\n",
    "sage.combinat.finite_state_machine.FSMOldCodeTransducerCartesianProduct = False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Automata and Transducers in SageMath\n",
    "\n",
    "## Digit Expansions\n",
    "\n",
    "* **decimal system**: base 10, digits 0, 1, ..., 9\n",
    "* **binary system**: base 2, digits 0, 1\n",
    "* base 2, digits -1, 0, 1 --> *redundancy*\n",
    "\n",
    "### Non-adjacent Form (NAF)\n",
    "\n",
    "* no consequtive non-zero digits in expansion\n",
    "* examples\n",
    "  * 3 = 1 + 2 = (1 1)<sub>2</sub> (standard binary) ... not a NAF\n",
    "  * 3 = -1 + 4 = (-1 0 1)<sub>2</sub> ... a NAF"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating a Transducer from Scatch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "NAF1 = Transducer([('I', 0, 0, None), ('I', 1, 1, None),\n",
    "                   (0, 0, 0, 0), (0, 1, 1, 0),\n",
    "                   (1, 0, 0, 1), (1, 2, 1, -1),\n",
    "                   (2, 1, 0, 0), (2, 2, 1, 0)], \n",
    "                  initial_states=['I'], final_states=[0], \n",
    "                  input_alphabet=[0, 1])\n",
    "NAF = NAF1\n",
    "NAF"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "view(NAF)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "14.digits(base=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "NAF(14.digits(base=2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "NAF.process(14.digits(base=2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "NAF(14.digits(base=2) + [0, 0, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "NAF = NAF.with_final_word_out(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "NAF(14.digits(base=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Calculating the Non-adjacent Form with Less Thinking"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def NAF_transition(state_from, read):\n",
    "    if state_from == 'I':\n",
    "        write = None\n",
    "        state_to = read\n",
    "        return (state_to, write)\n",
    "    current = 2*read + state_from\n",
    "    if current % 2 == 0:\n",
    "        write = 0\n",
    "    elif current % 4 == 1:\n",
    "        write = 1\n",
    "    else:\n",
    "        write = -1\n",
    "    state_to = (current - write) / 2\n",
    "    return (state_to, write)\n",
    "\n",
    "NAF2 = Transducer(NAF_transition,\n",
    "                  initial_states=['I'],\n",
    "                  final_states=[0],\n",
    "                  input_alphabet=[0, 1]).with_final_word_out(0)\n",
    "\n",
    "NAF == NAF2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "NAF2(14.digits(base=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A 3rd Construction of the Same Transducer\n",
    "\n",
    "* (NAF of 2n) = (binary of 3n) &ndash; (binary of n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def f(state_from, read):\n",
    "    current = 3*read + state_from\n",
    "    write = current % 2\n",
    "    state_to = (current - write) / 2\n",
    "    return (state_to, write)\n",
    "\n",
    "Triple = Transducer(f, input_alphabet=[0, 1],\n",
    "                    initial_states=[0],\n",
    "                    final_states=[0]).with_final_word_out(0)\n",
    "Triple"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "Triple(4.digits(base=2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Id = Transducer([(0, 0, 0, 0), (0, 0, 1, 1)],\n",
    "                initial_states=[0], final_states=[0],\n",
    "                input_alphabet=[0, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "prebuiltId = transducers.Identity([0, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "Combined_3n_n = Triple.cartesian_product(Id).relabeled()\n",
    "Combined_3n_n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "Combined_3n_n(4.digits(base=2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def g(read0, read1):\n",
    "    return ZZ(read0) - ZZ(read1)\n",
    "\n",
    "Minus = transducers.operator(g, input_alphabet=[None, -1, 0, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "prebuiltMinus = transducers.sub([-1, 0, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "NAF3 = Minus(Combined_3n_n).relabeled()  # compositions of transducers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "NAF3(14.digits(base=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## An Automaton detecting NAFs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "view(NAF)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A = NAF.output_projection()\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A([0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A([0, -1, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A([1, 0, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "view(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A = A.split_transitions()\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A.is_deterministic()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A.determine_alphabets()\n",
    "A = A.minimization().relabeled()\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A.is_deterministic()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Combining Small Transducers to a Larger One: The 3/2-1/2-NAF\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "NAF = NAF3\n",
    "NAF3n = NAF(Triple)  # composition\n",
    "Combined_NAF_3n_n = NAF3n.cartesian_product(NAF).relabeled()\n",
    "T = Minus(Combined_NAF_3n_n).relabeled()  # composition\n",
    "T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "T(14.digits(base=2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def value(digits):\n",
    "    return sum(d * 2^(e-2) for e, d in enumerate(digits))\n",
    "value(T(14.digits(base=2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Again an Alternative Construction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def minus(trans1, trans2):\n",
    "    if trans1.word_in == trans2.word_in:\n",
    "        return (trans1.word_in, \n",
    "                trans1.word_out[0] - trans2.word_out[0])\n",
    "    else:\n",
    "        raise LookupError\n",
    "\n",
    "from itertools import izip_longest\n",
    "def final_minus(state1, state2):\n",
    "    return [x - y for x, y in \n",
    "        izip_longest(state1.final_word_out, state2.final_word_out, fillvalue=0)]\n",
    "\n",
    "Talternative = NAF3n.product_FiniteStateMachine(\n",
    "                           NAF, minus,\n",
    "                           final_function=final_minus).relabeled()\n",
    "Talternative == T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Getting a Picture"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "sage.combinat.finite_state_machine.setup_latex_preamble()\n",
    "latex.mathjax_avoid_list('tikzpicture')\n",
    "T.set_coordinates({\n",
    "    0: (-2, 0.75),\n",
    "    1: (0, -1),\n",
    "    2: (-6, -1),\n",
    "    3: (6, -1),\n",
    "    4: (-4, 2.5),\n",
    "    5: (-6, 5),\n",
    "    6: (6, 5),\n",
    "    7: (4, 2.5),\n",
    "    8: (2, 0.75)})\n",
    "T.latex_options(format_letter=T.format_letter_negative,\n",
    "                accepting_where={\n",
    "                  0: 'right',\n",
    "                  1: 'below',\n",
    "                  2: 'below',\n",
    "                  3: 'below',\n",
    "                  4: 60,\n",
    "                  5: 'above',\n",
    "                  6: 'above',\n",
    "                  7: 120,\n",
    "                  8: 'left'},\n",
    "                accepting_show_empty=True)\n",
    "\n",
    "view(latex(T))\n",
    "latex(T)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def weight(state_from, read):\n",
    "    write = ZZ(read != 0)\n",
    "    return (0, write)\n",
    "\n",
    "Weight = Transducer(weight, input_alphabet=srange(-2, 2+1),\n",
    "                    initial_states=[0], final_states=[0])\n",
    "Weight.add_transition((0, 0, None, None))\n",
    "Weight"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "prebuiltWeight = transducers.weight(srange(-2, 2+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "NAF = NAF2  # reset since modified above\n",
    "W_binary = Weight(Id)\n",
    "W_NAF = Weight(NAF)\n",
    "W_T = Weight(T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "expansion = 14.digits(base=2)\n",
    "print \"binary\" , Id(expansion), W_binary(expansion), sum(W_binary(expansion))\n",
    "print \"NAF\", NAF(expansion), W_NAF(expansion), sum(W_NAF(expansion))\n",
    "print \"T\", T(expansion), W_T(expansion), sum(W_T(expansion))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Also Possible: Adjacency Matrices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "var('y')\n",
    "def am_entry(trans):\n",
    "    return y^add(trans.word_out) / 2\n",
    "W_T.adjacency_matrix(entry=am_entry)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Asymptotic Analysis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "var('k')\n",
    "W_binary.asymptotic_moments(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "W_NAF.asymptotic_moments(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "W_T.asymptotic_moments(k)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Sage 6.6.rc1",
   "language": "",
   "name": "sage_6_6_rc1"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}