Created
October 17, 2012 23:15
-
-
Save vchahun/3908948 to your computer and use it in GitHub Desktop.
Edit distance FSTs
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "metadata": { | |
| "name": "pyfst-edit distance" | |
| }, | |
| "nbformat": 3, | |
| "nbformat_minor": 0, | |
| "worksheets": [ | |
| { | |
| "cells": [ | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": "execfile('/Users/vchahun/Sandbox/pyfst/env/bin/activate_this.py', {'__file__': '/Users/vchahun/Sandbox/pyfst/env/bin/activate_this.py'})\nimport os\nos.environ.update({'PATH':os.environ.get('PATH')+':/usr/local/bin'})", | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [], | |
| "prompt_number": 1 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": "import fst", | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [], | |
| "prompt_number": 2 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": "syms = fst.SymbolTable()", | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [], | |
| "prompt_number": 3 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": "sigma = set('actg')", | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [], | |
| "prompt_number": 10 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": "edit = fst.SimpleFst(syms, syms)\nedit[0].final = True\nfor letter1 in sigma:\n edit.add_arc(0, 0, letter1, u'\u03b5', 1)\n edit.add_arc(0, 0, u'\u03b5', letter1, 1)\n for letter2 in sigma:\n edit.add_arc(0, 0, letter1, letter2, (1 if letter1 != letter2 else 0))", | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [], | |
| "prompt_number": 17 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": "edit", | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "output_type": "pyout", | |
| "prompt_number": 18, | |
| "svg": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.28.0 (20111028.1807)\n -->\n<!-- Title: FST Pages: 1 -->\n<svg width=\"108pt\" height=\"792pt\"\n viewBox=\"0.00 0.00 108.04 792.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph1\" class=\"graph\" transform=\"scale(0.912442 0.912442) rotate(0) translate(4 864)\">\n<title>FST</title>\n<polygon fill=\"white\" stroke=\"white\" points=\"-4,5 -4,-864 115.406,-864 115.406,5 -4,5\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\"><title>0</title>\n<ellipse fill=\"none\" stroke=\"black\" stroke-width=\"2\" cx=\"55.1802\" cy=\"-22\" rx=\"18\" ry=\"18\"/>\n<ellipse fill=\"none\" stroke=\"black\" stroke-width=\"2\" cx=\"55.1802\" cy=\"-22\" rx=\"22\" ry=\"22\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-16.4\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge2\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M53.6982,-44.2124C53.5768,-53.7952 54.0708,-62 55.1802,-62 55.8562,-62 56.3038,-58.9533 56.5228,-54.4045\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"60.025,-54.2593 56.6623,-44.2124 53.0256,-54.1635 60.025,-54.2593\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-64.8\" font-family=\"Times,serif\" font-size=\"14.00\">a:\u03b5/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge4\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M39.6404,-37.7379C27.5245,-57.1024 32.7045,-80 55.1802,-80 74.1441,-80 80.7949,-63.6989 75.1326,-46.973\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"78.1893,-45.2519 70.7201,-37.7379 71.8732,-48.2698 78.1893,-45.2519\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-82.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:a/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge22\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M44.5158,-41.4058C8.29084,-118.409 11.8456,-242 55.1802,-242 96.822,-242 101.731,-127.876 69.9076,-50.6328\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"73.0779,-49.1473 65.8446,-41.4058 66.6715,-51.9684 73.0779,-49.1473\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-244.8\" font-family=\"Times,serif\" font-size=\"14.00\">c:t/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge24\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M44.7922,-41.4046C6.25868,-124.585 9.72137,-260 55.1802,-260 98.9965,-260 103.797,-134.194 69.5807,-50.617\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"72.7704,-49.1751 65.5683,-41.4046 66.3527,-51.9704 72.7704,-49.1751\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-262.8\" font-family=\"Times,serif\" font-size=\"14.00\">c:g/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge26\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M44.8809,-41.7403C4.2406,-131.109 7.67368,-278 55.1802,-278 101.063,-278 105.834,-140.979 69.4922,-51.0975\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"72.6375,-49.5514 65.4795,-41.7403 66.2041,-52.3103 72.6375,-49.5514\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-280.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:\u03b5/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge28\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M45.1492,-41.6231C2.21476,-137.121 5.55842,-296 55.1802,-296 103.203,-296 107.882,-147.196 69.2179,-51.0459\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"72.3452,-49.4561 65.2112,-41.6231 65.9034,-52.1953 72.3452,-49.4561\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-298.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:t/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge30\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M45.1934,-41.9552C0.202518,-143.618 3.53144,-314 55.1802,-314 105.265,-314 109.912,-153.778 69.1202,-51.3705\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"72.2654,-49.8204 65.167,-41.9552 65.8113,-52.5304 72.2654,-49.8204\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-316.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:a/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge32\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M45.4182,-41.8372C-1.81711,-149.602 1.43688,-332 55.1802,-332 107.402,-332 111.953,-159.787 68.8339,-51.1667\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"72.0223,-49.7189 64.9422,-41.8372 65.5618,-52.4139 72.0223,-49.7189\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-334.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:c/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge34\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M45.5358,-41.9246C-3.83027,-155.805 -0.615481,-350 55.1802,-350 109.45,-350 113.976,-166.28 68.7562,-51.4409\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"71.8778,-49.8304 64.8246,-41.9246 65.4082,-52.5033 71.8778,-49.8304\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-352.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:t</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge36\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M45.6876,-41.9001C-5.84377,-161.873 -2.67956,-368 55.1802,-368 111.571,-368 116.008,-172.207 68.4923,-51.2005\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"71.7094,-49.8208 64.6728,-41.9001 65.2342,-52.48 71.7094,-49.8208\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-370.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:g/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge38\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M45.708,-42.1542C-7.85105,-168.252 -4.69364,-386 55.1802,-386 113.592,-386 118.023,-178.755 68.4738,-51.5493\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"71.6623,-50.0986 64.6524,-42.1542 65.1781,-52.736 71.6623,-50.0986\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-388.8\" font-family=\"Times,serif\" font-size=\"14.00\">g:\u03b5/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge40\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M45.7508,-42.3335C-9.85867,-174.541 -6.71553,-404 55.1802,-404 115.625,-404 120.039,-185.171 68.4229,-51.7854\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"71.5969,-50.2978 64.6096,-42.3335 65.1052,-52.9167 71.5969,-50.2978\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-406.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:g/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge6\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M40.6905,-38.7983C25.1165,-64.8729 29.9464,-98 55.1802,-98 77.5555,-98 83.8878,-71.9532 74.1772,-47.8727\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"77.2531,-46.1974 69.6699,-38.7983 70.9838,-49.3114 77.2531,-46.1974\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-100.8\" font-family=\"Times,serif\" font-size=\"14.00\">a:a</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge42\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M45.994,-42.0127C-11.8729,-180.244 -8.81086,-422 55.1802,-422 117.734,-422 122.065,-190.982 68.1734,-51.4799\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"71.3447,-49.9848 64.3664,-42.0127 64.8501,-52.5965 71.3447,-49.9848\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-424.8\" font-family=\"Times,serif\" font-size=\"14.00\">g:a/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge44\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M45.9042,-42.4692C-13.8748,-186.846 -10.7827,-440 55.1802,-440 119.726,-440 124.073,-197.607 68.2221,-51.9217\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"71.4088,-50.4637 64.4562,-42.4692 64.9059,-53.0544 71.4088,-50.4637\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-442.8\" font-family=\"Times,serif\" font-size=\"14.00\">g:c/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge46\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M46.015,-42.4263C-15.8831,-192.861 -12.8281,-458 55.1802,-458 121.794,-458 126.091,-203.625 68.0716,-51.823\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"71.2852,-50.4319 64.3454,-42.4263 64.7781,-53.0123 71.2852,-50.4319\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-460.8\" font-family=\"Times,serif\" font-size=\"14.00\">g:t/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge48\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M46.1489,-42.31C-17.8917,-198.785 -14.8812,-476 55.1802,-476 123.873,-476 128.109,-209.508 67.8872,-51.6137\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"71.1412,-50.3245 64.2116,-42.31 64.6308,-52.8966 71.1412,-50.3245\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-478.8\" font-family=\"Times,serif\" font-size=\"14.00\">g:g</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge8\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M41.5176,-39.5369C22.867,-72.2091 27.4212,-116 55.1802,-116 80.4452,-116 86.4878,-79.7243 73.3078,-48.5725\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"76.4109,-46.9515 68.8428,-39.5369 70.1353,-50.0526 76.4109,-46.9515\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-118.8\" font-family=\"Times,serif\" font-size=\"14.00\">a:c/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge10\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M42.2681,-39.9209C20.6889,-79.1071 24.9929,-134 55.1802,-134 83.0091,-134 88.841,-87.3491 72.676,-49.3591\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"75.6093,-47.3872 68.0923,-39.9209 69.3126,-50.4453 75.6093,-47.3872\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-136.8\" font-family=\"Times,serif\" font-size=\"14.00\">a:t/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge12\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M42.8086,-40.3331C18.5728,-85.9417 22.6967,-152 55.1802,-152 85.57,-152 91.1382,-94.1826 71.8846,-49.3837\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"75.0268,-47.8415 67.5518,-40.3331 68.713,-50.8642 75.0268,-47.8415\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-154.8\" font-family=\"Times,serif\" font-size=\"14.00\">a:g/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge14\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M43.1881,-40.7935C16.4938,-92.7627 20.4912,-170 55.1802,-170 87.8367,-170 93.2928,-101.549 71.5486,-50.1684\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"74.5737,-48.3744 67.1723,-40.7935 68.2308,-51.3353 74.5737,-48.3744\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-172.8\" font-family=\"Times,serif\" font-size=\"14.00\">c:\u03b5/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge16\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M43.7082,-40.7782C14.4147,-99.0589 18.2387,-188 55.1802,-188 90.2457,-188 95.4719,-107.863 70.8587,-49.8785\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"74.0251,-48.3869 66.6523,-40.7782 67.6711,-51.324 74.0251,-48.3869\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-190.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:c/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge18\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M43.9623,-41.1334C12.3689,-105.689 16.1082,-206 55.1802,-206 92.4207,-206 97.5633,-114.873 70.6081,-50.4332\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"73.7107,-48.8 66.3981,-41.1334 67.3337,-51.6868 73.7107,-48.8\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-208.8\" font-family=\"Times,serif\" font-size=\"14.00\">c:a/1</text>\n</g>\n<!-- 0->0 -->\n<g id=\"edge20\" class=\"edge\"><title>0->0</title>\n<path fill=\"none\" stroke=\"black\" d=\"M44.308,-41.1772C10.3224,-111.965 13.9465,-224 55.1802,-224 94.6422,-224 99.6571,-121.386 70.225,-50.5185\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"73.3266,-48.8802 66.0524,-41.1772 66.9353,-51.7352 73.3266,-48.8802\"/>\n<text text-anchor=\"middle\" x=\"55.1802\" y=\"-226.8\" font-family=\"Times,serif\" font-size=\"14.00\">c:c</text>\n</g>\n</g>\n</svg>\n", | |
| "text": "<fst.SimpleFst at 0x1095efd88>" | |
| } | |
| ], | |
| "prompt_number": 18 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": "def make_input(word):\n inp = fst.Acceptor(syms)\n for i, c in enumerate(word):\n inp.add_arc(i, i+1, c)\n inp[i+1].final = True\n return inp", | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [], | |
| "prompt_number": 19 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": "make_input('input')", | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "output_type": "pyout", | |
| "prompt_number": 21, | |
| "svg": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.28.0 (20111028.1807)\n -->\n<!-- Title: FST Pages: 1 -->\n<svg width=\"460pt\" height=\"52pt\"\n viewBox=\"0.00 0.00 460.00 52.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph1\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 48)\">\n<title>FST</title>\n<polygon fill=\"white\" stroke=\"white\" points=\"-4,5 -4,-48 457,-48 457,5 -4,5\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\"><title>0</title>\n<ellipse fill=\"none\" stroke=\"black\" stroke-width=\"2\" cx=\"18\" cy=\"-22\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"18\" y=\"-16.4\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n</g>\n<!-- 1 -->\n<g id=\"node3\" class=\"node\"><title>1</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"96\" cy=\"-22\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"96\" y=\"-16.4\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n</g>\n<!-- 0->1 -->\n<g id=\"edge2\" class=\"edge\"><title>0->1</title>\n<path fill=\"none\" stroke=\"black\" d=\"M36.2456,-22C45.4768,-22 57.0652,-22 67.5054,-22\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"67.8227,-25.5001 77.8227,-22 67.8226,-18.5001 67.8227,-25.5001\"/>\n<text text-anchor=\"middle\" x=\"57\" y=\"-24.8\" font-family=\"Times,serif\" font-size=\"14.00\">i:i</text>\n</g>\n<!-- 2 -->\n<g id=\"node5\" class=\"node\"><title>2</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"180\" cy=\"-22\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"180\" y=\"-16.4\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n</g>\n<!-- 1->2 -->\n<g id=\"edge4\" class=\"edge\"><title>1->2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M114.39,-22C125.226,-22 139.399,-22 151.709,-22\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"151.916,-25.5001 161.916,-22 151.916,-18.5001 151.916,-25.5001\"/>\n<text text-anchor=\"middle\" x=\"138\" y=\"-24.8\" font-family=\"Times,serif\" font-size=\"14.00\">n:n</text>\n</g>\n<!-- 3 -->\n<g id=\"node7\" class=\"node\"><title>3</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"264\" cy=\"-22\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"264\" y=\"-16.4\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n</g>\n<!-- 2->3 -->\n<g id=\"edge6\" class=\"edge\"><title>2->3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M198.39,-22C209.226,-22 223.399,-22 235.709,-22\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"235.916,-25.5001 245.916,-22 235.916,-18.5001 235.916,-25.5001\"/>\n<text text-anchor=\"middle\" x=\"222\" y=\"-24.8\" font-family=\"Times,serif\" font-size=\"14.00\">p:p</text>\n</g>\n<!-- 4 -->\n<g id=\"node9\" class=\"node\"><title>4</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"348\" cy=\"-22\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"348\" y=\"-16.4\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n</g>\n<!-- 3->4 -->\n<g id=\"edge8\" class=\"edge\"><title>3->4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M282.39,-22C293.226,-22 307.399,-22 319.709,-22\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"319.916,-25.5001 329.916,-22 319.916,-18.5001 319.916,-25.5001\"/>\n<text text-anchor=\"middle\" x=\"306\" y=\"-24.8\" font-family=\"Times,serif\" font-size=\"14.00\">u:u</text>\n</g>\n<!-- 5 -->\n<g id=\"node11\" class=\"node\"><title>5</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"430\" cy=\"-22\" rx=\"18\" ry=\"18\"/>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"430\" cy=\"-22\" rx=\"22\" ry=\"22\"/>\n<text text-anchor=\"middle\" x=\"430\" y=\"-16.4\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n</g>\n<!-- 4->5 -->\n<g id=\"edge10\" class=\"edge\"><title>4->5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M366.359,-22C375.527,-22 387.061,-22 397.725,-22\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"397.979,-25.5001 407.979,-22 397.979,-18.5001 397.979,-25.5001\"/>\n<text text-anchor=\"middle\" x=\"387\" y=\"-24.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:t</text>\n</g>\n</g>\n</svg>\n", | |
| "text": "<fst.Acceptor at 0x109640fc8>" | |
| } | |
| ], | |
| "prompt_number": 21 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": "lattice = make_input('atc') >> edit >> make_input('act')\nlattice", | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "output_type": "pyout", | |
| "prompt_number": 30, | |
| "svg": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.28.0 (20111028.1807)\n -->\n<!-- Title: FST Pages: 1 -->\n<svg width=\"612pt\" height=\"373pt\"\n viewBox=\"0.00 0.00 612.00 372.75\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph1\" class=\"graph\" transform=\"scale(0.95625 0.95625) rotate(0) translate(4 385.8)\">\n<title>FST</title>\n<polygon fill=\"white\" stroke=\"white\" points=\"-4,5 -4,-385.8 637,-385.8 637,5 -4,5\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\"><title>0</title>\n<ellipse fill=\"none\" stroke=\"black\" stroke-width=\"2\" cx=\"18\" cy=\"-207\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"18\" y=\"-201.4\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n</g>\n<!-- 1 -->\n<g id=\"node3\" class=\"node\"><title>1</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"112\" cy=\"-266\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"112\" y=\"-260.4\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n</g>\n<!-- 0->1 -->\n<g id=\"edge2\" class=\"edge\"><title>0->1</title>\n<path fill=\"none\" stroke=\"black\" d=\"M33.7814,-216.479C48.3528,-225.824 70.8373,-240.244 87.793,-251.117\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"86.2514,-254.287 96.5586,-256.739 90.0303,-248.394 86.2514,-254.287\"/>\n<text text-anchor=\"middle\" x=\"65\" y=\"-248.8\" font-family=\"Times,serif\" font-size=\"14.00\">a:\u03b5/1</text>\n</g>\n<!-- 2 -->\n<g id=\"node5\" class=\"node\"><title>2</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"112\" cy=\"-148\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"112\" y=\"-142.4\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n</g>\n<!-- 0->2 -->\n<g id=\"edge4\" class=\"edge\"><title>0->2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M30.6327,-193.991C36.371,-188.071 43.632,-181.271 51,-176.2 61.5981,-168.905 74.3805,-162.605 85.4191,-157.82\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"87.0561,-160.931 94.9536,-153.868 84.3755,-154.464 87.0561,-160.931\"/>\n<text text-anchor=\"middle\" x=\"65\" y=\"-179.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:a/1</text>\n</g>\n<!-- 3 -->\n<g id=\"node7\" class=\"node\"><title>3</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"206\" cy=\"-207\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"206\" y=\"-201.4\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n</g>\n<!-- 0->3 -->\n<g id=\"edge6\" class=\"edge\"><title>0->3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M36.165,-207C68.5537,-207 138.913,-207 177.8,-207\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"177.876,-210.5 187.876,-207 177.876,-203.5 177.876,-210.5\"/>\n<text text-anchor=\"middle\" x=\"112\" y=\"-209.8\" font-family=\"Times,serif\" font-size=\"14.00\">a:a</text>\n</g>\n<!-- 1->3 -->\n<g id=\"edge8\" class=\"edge\"><title>1->3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M126.389,-254.944C132.005,-250.488 138.687,-245.415 145,-241.2 156.337,-233.63 169.439,-226.039 180.502,-219.938\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"182.484,-222.844 189.603,-214.998 179.144,-216.692 182.484,-222.844\"/>\n<text text-anchor=\"middle\" x=\"159\" y=\"-244.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:a/1</text>\n</g>\n<!-- 4 -->\n<g id=\"node10\" class=\"node\"><title>4</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"206\" cy=\"-335\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"206\" y=\"-329.4\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n</g>\n<!-- 1->4 -->\n<g id=\"edge10\" class=\"edge\"><title>1->4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M126.973,-276.48C141.784,-287.588 165.388,-305.291 182.76,-318.32\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"181.097,-321.448 191.197,-324.648 185.297,-315.848 181.097,-321.448\"/>\n<text text-anchor=\"middle\" x=\"159\" y=\"-313.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:\u03b5/1</text>\n</g>\n<!-- 5 -->\n<g id=\"node12\" class=\"node\"><title>5</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"303\" cy=\"-272\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"303\" y=\"-266.4\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n</g>\n<!-- 1->5 -->\n<g id=\"edge12\" class=\"edge\"><title>1->5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M130.106,-266.543C162.984,-267.587 235.239,-269.881 274.796,-271.136\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"274.691,-274.635 284.797,-271.454 274.913,-267.638 274.691,-274.635\"/>\n<text text-anchor=\"middle\" x=\"206\" y=\"-272.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:a/1</text>\n</g>\n<!-- 2->3 -->\n<g id=\"edge14\" class=\"edge\"><title>2->3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M129.046,-153.868C141.589,-158.84 159.158,-166.672 173,-176.2 177.49,-179.29 181.94,-183.022 186.03,-186.806\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"183.774,-189.495 193.367,-193.991 188.671,-184.494 183.774,-189.495\"/>\n<text text-anchor=\"middle\" x=\"159\" y=\"-179.8\" font-family=\"Times,serif\" font-size=\"14.00\">a:\u03b5/1</text>\n</g>\n<!-- 6 -->\n<g id=\"node15\" class=\"node\"><title>6</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"303\" cy=\"-142\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"303\" y=\"-136.4\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n</g>\n<!-- 2->6 -->\n<g id=\"edge16\" class=\"edge\"><title>2->6</title>\n<path fill=\"none\" stroke=\"black\" d=\"M130.106,-147.457C162.984,-146.413 235.239,-144.119 274.796,-142.864\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"274.913,-146.362 284.797,-142.546 274.691,-139.365 274.913,-146.362\"/>\n<text text-anchor=\"middle\" x=\"206\" y=\"-148.8\" font-family=\"Times,serif\" font-size=\"14.00\">a:c/1</text>\n</g>\n<!-- 7 -->\n<g id=\"node17\" class=\"node\"><title>7</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"206\" cy=\"-83\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"206\" y=\"-77.4\" font-family=\"Times,serif\" font-size=\"14.00\">7</text>\n</g>\n<!-- 2->7 -->\n<g id=\"edge18\" class=\"edge\"><title>2->7</title>\n<path fill=\"none\" stroke=\"black\" d=\"M123.069,-133.787C128.855,-126.362 136.625,-117.53 145,-111.2 155.264,-103.442 168.004,-97.0829 179.101,-92.3795\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"180.728,-95.4982 188.712,-88.5331 178.127,-88.9993 180.728,-95.4982\"/>\n<text text-anchor=\"middle\" x=\"159\" y=\"-114.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:c/1</text>\n</g>\n<!-- 3->5 -->\n<g id=\"edge22\" class=\"edge\"><title>3->5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M222.314,-214.621C234.759,-221.071 252.556,-230.891 267,-241.2 272.065,-244.815 277.244,-249.036 282.012,-253.173\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"279.773,-255.867 289.555,-259.936 284.445,-250.654 279.773,-255.867\"/>\n<text text-anchor=\"middle\" x=\"253\" y=\"-244.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:\u03b5/1</text>\n</g>\n<!-- 3->6 -->\n<g id=\"edge20\" class=\"edge\"><title>3->6</title>\n<path fill=\"none\" stroke=\"black\" d=\"M218.767,-194.181C224.535,-188.302 231.782,-181.483 239,-176.2 250.886,-167.5 265.249,-159.534 277.256,-153.484\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"278.845,-156.603 286.289,-149.064 275.769,-150.315 278.845,-156.603\"/>\n<text text-anchor=\"middle\" x=\"253\" y=\"-179.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:c/1</text>\n</g>\n<!-- 8 -->\n<g id=\"node21\" class=\"node\"><title>8</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"403\" cy=\"-207\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"403\" y=\"-201.4\" font-family=\"Times,serif\" font-size=\"14.00\">8</text>\n</g>\n<!-- 3->8 -->\n<g id=\"edge24\" class=\"edge\"><title>3->8</title>\n<path fill=\"none\" stroke=\"black\" d=\"M224.305,-207C258.274,-207 333.913,-207 374.691,-207\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"374.734,-210.5 384.734,-207 374.734,-203.5 374.734,-210.5\"/>\n<text text-anchor=\"middle\" x=\"303\" y=\"-209.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:c/1</text>\n</g>\n<!-- 4->5 -->\n<g id=\"edge26\" class=\"edge\"><title>4->5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M221.428,-325.432C236.634,-315.348 260.815,-299.312 278.723,-287.436\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"281.036,-290.102 287.436,-281.658 277.167,-284.268 281.036,-290.102\"/>\n<text text-anchor=\"middle\" x=\"253\" y=\"-315.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:a/1</text>\n</g>\n<!-- 9 -->\n<g id=\"node24\" class=\"node\"><title>9</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"303\" cy=\"-335\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"303\" y=\"-329.4\" font-family=\"Times,serif\" font-size=\"14.00\">9</text>\n</g>\n<!-- 4->9 -->\n<g id=\"edge28\" class=\"edge\"><title>4->9</title>\n<path fill=\"none\" stroke=\"black\" d=\"M224.424,-335C238.352,-335 258.139,-335 274.243,-335\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"274.686,-338.5 284.686,-335 274.686,-331.5 274.686,-338.5\"/>\n<text text-anchor=\"middle\" x=\"253\" y=\"-337.8\" font-family=\"Times,serif\" font-size=\"14.00\">c:\u03b5/1</text>\n</g>\n<!-- 10 -->\n<g id=\"node26\" class=\"node\"><title>10</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"403\" cy=\"-336\" rx=\"20.8887\" ry=\"20.8887\"/>\n<text text-anchor=\"middle\" x=\"403\" y=\"-330.4\" font-family=\"Times,serif\" font-size=\"14.00\">10</text>\n</g>\n<!-- 4->10 -->\n<g id=\"edge30\" class=\"edge\"><title>4->10</title>\n<path fill=\"none\" stroke=\"black\" d=\"M221.018,-345.449C226.395,-348.993 232.746,-352.646 239,-355 257.122,-361.821 262.7,-360.439 282,-362 319.749,-365.052 331.158,-368.232 367,-356 370.179,-354.915 373.397,-353.534 376.526,-352.005\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"378.401,-354.97 385.526,-347.129 375.066,-348.816 378.401,-354.97\"/>\n<text text-anchor=\"middle\" x=\"303\" y=\"-367.8\" font-family=\"Times,serif\" font-size=\"14.00\">c:a/1</text>\n</g>\n<!-- 5->8 -->\n<g id=\"edge34\" class=\"edge\"><title>5->8</title>\n<path fill=\"none\" stroke=\"black\" d=\"M316.396,-259.866C322.848,-253.875 331.036,-246.76 339,-241.2 351.078,-232.768 365.454,-224.822 377.422,-218.715\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"379.022,-221.829 386.414,-214.238 375.902,-215.562 379.022,-221.829\"/>\n<text text-anchor=\"middle\" x=\"353\" y=\"-244.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:c/1</text>\n</g>\n<!-- 5->10 -->\n<g id=\"edge32\" class=\"edge\"><title>5->10</title>\n<path fill=\"none\" stroke=\"black\" d=\"M318.46,-281.443C333.743,-291.424 358.145,-307.36 376.639,-319.438\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"374.891,-322.476 385.178,-325.014 378.719,-316.616 374.891,-322.476\"/>\n<text text-anchor=\"middle\" x=\"353\" y=\"-314.8\" font-family=\"Times,serif\" font-size=\"14.00\">c:\u03b5/1</text>\n</g>\n<!-- 11 -->\n<g id=\"node30\" class=\"node\"><title>11</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"503\" cy=\"-267\" rx=\"20.1809\" ry=\"20.1809\"/>\n<text text-anchor=\"middle\" x=\"503\" y=\"-261.4\" font-family=\"Times,serif\" font-size=\"14.00\">11</text>\n</g>\n<!-- 5->11 -->\n<g id=\"edge36\" class=\"edge\"><title>5->11</title>\n<path fill=\"none\" stroke=\"black\" d=\"M321.225,-271.565C355.067,-270.71 430.578,-268.804 472.509,-267.745\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"472.738,-271.24 482.647,-267.489 472.561,-264.242 472.738,-271.24\"/>\n<text text-anchor=\"middle\" x=\"403\" y=\"-272.8\" font-family=\"Times,serif\" font-size=\"14.00\">c:c</text>\n</g>\n<!-- 6->8 -->\n<g id=\"edge38\" class=\"edge\"><title>6->8</title>\n<path fill=\"none\" stroke=\"black\" d=\"M319.586,-149.238C332.695,-155.609 351.694,-165.514 367,-176.2 372.102,-179.762 377.296,-183.962 382.067,-188.096\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"379.826,-190.788 389.604,-194.866 384.503,-185.58 379.826,-190.788\"/>\n<text text-anchor=\"middle\" x=\"353\" y=\"-179.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:\u03b5/1</text>\n</g>\n<!-- 12 -->\n<g id=\"node33\" class=\"node\"><title>12</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"403\" cy=\"-81\" rx=\"20.8887\" ry=\"20.8887\"/>\n<text text-anchor=\"middle\" x=\"403\" y=\"-75.4\" font-family=\"Times,serif\" font-size=\"14.00\">12</text>\n</g>\n<!-- 6->12 -->\n<g id=\"edge40\" class=\"edge\"><title>6->12</title>\n<path fill=\"none\" stroke=\"black\" d=\"M316.279,-129.695C322.702,-123.661 330.899,-116.558 339,-111.2 349.955,-103.955 362.913,-97.4358 374.221,-92.3247\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"375.876,-95.4211 383.641,-88.2128 373.076,-89.0057 375.876,-95.4211\"/>\n<text text-anchor=\"middle\" x=\"353\" y=\"-114.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:t/1</text>\n</g>\n<!-- 13 -->\n<g id=\"node35\" class=\"node\"><title>13</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"503\" cy=\"-146\" rx=\"20.8887\" ry=\"20.8887\"/>\n<text text-anchor=\"middle\" x=\"503\" y=\"-140.4\" font-family=\"Times,serif\" font-size=\"14.00\">13</text>\n</g>\n<!-- 6->13 -->\n<g id=\"edge42\" class=\"edge\"><title>6->13</title>\n<path fill=\"none\" stroke=\"black\" d=\"M321.225,-142.348C354.894,-143.028 429.806,-144.542 471.863,-145.391\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"471.982,-148.894 482.051,-145.597 472.123,-141.896 471.982,-148.894\"/>\n<text text-anchor=\"middle\" x=\"403\" y=\"-147.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:t</text>\n</g>\n<!-- 7->6 -->\n<g id=\"edge44\" class=\"edge\"><title>7->6</title>\n<path fill=\"none\" stroke=\"black\" d=\"M223.188,-89.145C235.649,-94.2154 253.045,-102.047 267,-111.2 272.203,-114.613 277.437,-118.753 282.215,-122.877\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"279.97,-125.565 289.738,-129.668 284.661,-120.369 279.97,-125.565\"/>\n<text text-anchor=\"middle\" x=\"253\" y=\"-114.8\" font-family=\"Times,serif\" font-size=\"14.00\">a:\u03b5/1</text>\n</g>\n<!-- 7->12 -->\n<g id=\"edge46\" class=\"edge\"><title>7->12</title>\n<path fill=\"none\" stroke=\"black\" d=\"M224.305,-82.8225C257.575,-82.4813 330.815,-81.7301 372.129,-81.3064\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"372.181,-84.8061 382.144,-81.2036 372.109,-77.8065 372.181,-84.8061\"/>\n<text text-anchor=\"middle\" x=\"303\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">a:t/1</text>\n</g>\n<!-- 14 -->\n<g id=\"node39\" class=\"node\"><title>14</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"303\" cy=\"-20\" rx=\"20.8887\" ry=\"20.8887\"/>\n<text text-anchor=\"middle\" x=\"303\" y=\"-14.4\" font-family=\"Times,serif\" font-size=\"14.00\">14</text>\n</g>\n<!-- 7->14 -->\n<g id=\"edge48\" class=\"edge\"><title>7->14</title>\n<path fill=\"none\" stroke=\"black\" d=\"M216.957,-68.6344C222.71,-61.1649 230.484,-52.3391 239,-46.2 249.331,-38.7531 262.095,-32.9403 273.428,-28.7024\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"274.637,-31.9874 282.92,-25.3821 272.326,-25.3799 274.637,-31.9874\"/>\n<text text-anchor=\"middle\" x=\"253\" y=\"-49.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:t/1</text>\n</g>\n<!-- 8->11 -->\n<g id=\"edge50\" class=\"edge\"><title>8->11</title>\n<path fill=\"none\" stroke=\"black\" d=\"M419.356,-214.584C432.325,-221.164 451.246,-231.185 467,-241.2 470.727,-243.569 474.578,-246.203 478.302,-248.856\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"476.508,-251.881 486.643,-254.969 480.646,-246.235 476.508,-251.881\"/>\n<text text-anchor=\"middle\" x=\"453\" y=\"-244.8\" font-family=\"Times,serif\" font-size=\"14.00\">c:\u03b5/1</text>\n</g>\n<!-- 8->13 -->\n<g id=\"edge54\" class=\"edge\"><title>8->13</title>\n<path fill=\"none\" stroke=\"black\" d=\"M416.279,-194.695C422.702,-188.661 430.899,-181.558 439,-176.2 449.955,-168.955 462.913,-162.436 474.221,-157.325\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"475.876,-160.421 483.641,-153.213 473.076,-154.006 475.876,-160.421\"/>\n<text text-anchor=\"middle\" x=\"453\" y=\"-179.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:t/1</text>\n</g>\n<!-- 15 -->\n<g id=\"node42\" class=\"node\"><title>15</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"607\" cy=\"-207\" rx=\"20.8568\" ry=\"20.8568\"/>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"607\" cy=\"-207\" rx=\"24.8884\" ry=\"24.8884\"/>\n<text text-anchor=\"middle\" x=\"607\" y=\"-201.4\" font-family=\"Times,serif\" font-size=\"14.00\">15</text>\n</g>\n<!-- 8->15 -->\n<g id=\"edge52\" class=\"edge\"><title>8->15</title>\n<path fill=\"none\" stroke=\"black\" d=\"M421.222,-207C454.54,-207 528.365,-207 571.943,-207\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"572.066,-210.5 582.066,-207 572.066,-203.5 572.066,-210.5\"/>\n<text text-anchor=\"middle\" x=\"503\" y=\"-209.8\" font-family=\"Times,serif\" font-size=\"14.00\">c:t/1</text>\n</g>\n<!-- 9->10 -->\n<g id=\"edge56\" class=\"edge\"><title>9->10</title>\n<path fill=\"none\" stroke=\"black\" d=\"M321.07,-335.174C335.016,-335.316 355.073,-335.521 371.73,-335.691\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"372.052,-339.194 382.087,-335.797 372.123,-332.195 372.052,-339.194\"/>\n<text text-anchor=\"middle\" x=\"353\" y=\"-338.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:a/1</text>\n</g>\n<!-- 10->11 -->\n<g id=\"edge58\" class=\"edge\"><title>10->11</title>\n<path fill=\"none\" stroke=\"black\" d=\"M420.183,-324.606C435.787,-313.619 459.609,-296.847 477.531,-284.228\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"479.632,-287.03 485.793,-278.411 475.602,-281.306 479.632,-287.03\"/>\n<text text-anchor=\"middle\" x=\"453\" y=\"-312.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:c/1</text>\n</g>\n<!-- 11->15 -->\n<g id=\"edge60\" class=\"edge\"><title>11->15</title>\n<path fill=\"none\" stroke=\"black\" d=\"M520.843,-257.092C535.877,-248.249 558.239,-235.095 576.275,-224.485\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"578.406,-227.292 585.251,-219.205 574.857,-221.259 578.406,-227.292\"/>\n<text text-anchor=\"middle\" x=\"553\" y=\"-248.8\" font-family=\"Times,serif\" font-size=\"14.00\">\u03b5:t/1</text>\n</g>\n<!-- 12->13 -->\n<g id=\"edge62\" class=\"edge\"><title>12->13</title>\n<path fill=\"none\" stroke=\"black\" d=\"M422.539,-87.95C435.587,-93.2921 453.128,-101.406 467,-111.2 472.112,-114.809 477.156,-119.192 481.754,-123.612\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"479.49,-126.3 489.006,-130.957 484.471,-121.382 479.49,-126.3\"/>\n<text text-anchor=\"middle\" x=\"453\" y=\"-114.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:\u03b5/1</text>\n</g>\n<!-- 13->15 -->\n<g id=\"edge64\" class=\"edge\"><title>13->15</title>\n<path fill=\"none\" stroke=\"black\" d=\"M522.486,-153.567C535.351,-159.14 552.695,-167.277 567,-176.2 571.259,-178.857 575.597,-181.897 579.758,-185.01\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"577.927,-188.019 587.968,-191.399 582.226,-182.495 577.927,-188.019\"/>\n<text text-anchor=\"middle\" x=\"553\" y=\"-179.8\" font-family=\"Times,serif\" font-size=\"14.00\">c:\u03b5/1</text>\n</g>\n<!-- 14->12 -->\n<g id=\"edge66\" class=\"edge\"><title>14->12</title>\n<path fill=\"none\" stroke=\"black\" d=\"M323.149,-25.7855C336.157,-30.2233 353.401,-37.128 367,-46.2 372.206,-49.6729 377.29,-53.9965 381.898,-58.4028\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"379.631,-61.0896 389.141,-65.7606 384.62,-56.1788 379.631,-61.0896\"/>\n<text text-anchor=\"middle\" x=\"353\" y=\"-49.8\" font-family=\"Times,serif\" font-size=\"14.00\">a:\u03b5/1</text>\n</g>\n</g>\n</svg>\n", | |
| "text": "<fst.StdVectorFst at 0x109647d40>" | |
| } | |
| ], | |
| "prompt_number": 30 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": "print lattice.shortest_distance()[-1]", | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": "TropicalWeight(2.0)\n" | |
| } | |
| ], | |
| "prompt_number": 33 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": "", | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [] | |
| } | |
| ], | |
| "metadata": {} | |
| } | |
| ] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment