transducer_complex.ipynb

{
 "metadata": {
  "name": "transducer_complex"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "etwas komplexeres Beispiel, das Umlautung im Deutschen realisiert.\n",
      "\n",
      "Das Lexikon (hier: Kuh und Maus) wird mit einem Transducer komponiert, der Buchstaben durch ihre Umlaute ersetzt"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import fst\n",
      "\n",
      "isyms=osyms=fst.SymbolTable()\n",
      "\n",
      "def add_word(t, syms, state_end):\n",
      "    state_old=0\n",
      "    for sym in syms[:-1]:\n",
      "        state_new=t.add_state()\n",
      "        t.add_arc(state_old, state_new, sym, sym)\n",
      "        state_old=state_new\n",
      "    t.add_arc(state_old, state_end, syms[-1], syms[-1])\n",
      "\n",
      "def syms_only(syms):\n",
      "    t=fst.Transducer(isyms,osyms)\n",
      "    st_end=t.add_state()\n",
      "    add_word(t,syms,st_end)\n",
      "    t[st_end].final=True\n",
      "\n",
      "lex=fst.Transducer(isyms,osyms)\n",
      "\n",
      "st_end=lex.add_state()\n",
      "lex[st_end].final=True\n",
      "add_word(lex,'kuh',st_end)\n",
      "add_word(lex,'maus',st_end)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "lex"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 4,
       "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.26.3 (20100126.1600)\n",
        " -->\n",
        "<!-- Title: FST Pages: 1 -->\n",
        "<svg width=\"396pt\" height=\"98pt\"\n",
        " viewBox=\"0.00 0.00 396.00 98.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 94)\">\n",
        "<title>FST</title>\n",
        "<polygon fill=\"white\" stroke=\"white\" points=\"-4,5 -4,-94 393,-94 393,5 -4,5\"/>\n",
        "<!-- 0 -->\n",
        "<g id=\"node1\" class=\"node\"><title>0</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" stroke-width=\"2\" cx=\"19\" cy=\"-46\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"19\" y=\"-42.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">0</text>\n",
        "</g>\n",
        "<!-- 2 -->\n",
        "<g id=\"node3\" class=\"node\"><title>2</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"101\" cy=\"-72\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"101\" y=\"-68.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">2</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;2 -->\n",
        "<g id=\"edge2\" class=\"edge\"><title>0&#45;&gt;2</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M36.7928,-51.6416C47.5382,-55.0487 61.4547,-59.4612 73.5833,-63.3069\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"72.6518,-66.6832 83.2419,-66.3694 74.7675,-60.0106 72.6518,-66.6832\"/>\n",
        "<text text-anchor=\"middle\" x=\"60\" y=\"-65.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">k</text>\n",
        "</g>\n",
        "<!-- 4 -->\n",
        "<g id=\"node5\" class=\"node\"><title>4</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"101\" cy=\"-18\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"101\" y=\"-14.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">4</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;4 -->\n",
        "<g id=\"edge4\" class=\"edge\"><title>0&#45;&gt;4</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M36.7928,-39.9244C47.6118,-36.2301 61.6455,-31.4381 73.8323,-27.2768\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"75.1912,-30.5113 83.5236,-23.9675 72.9291,-23.8868 75.1912,-30.5113\"/>\n",
        "<text text-anchor=\"middle\" x=\"60\" y=\"-38.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">m</text>\n",
        "</g>\n",
        "<!-- 3 -->\n",
        "<g id=\"node8\" class=\"node\"><title>3</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"232\" cy=\"-72\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"232\" y=\"-68.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">3</text>\n",
        "</g>\n",
        "<!-- 2&#45;&gt;3 -->\n",
        "<g id=\"edge6\" class=\"edge\"><title>2&#45;&gt;3</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M119.769,-72C141.559,-72 177.747,-72 203.125,-72\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"203.266,-75.5001 213.266,-72 203.266,-68.5001 203.266,-75.5001\"/>\n",
        "<text text-anchor=\"middle\" x=\"140\" y=\"-77.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">u</text>\n",
        "</g>\n",
        "<!-- 5 -->\n",
        "<g id=\"node11\" class=\"node\"><title>5</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"179\" cy=\"-18\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"179\" y=\"-14.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">5</text>\n",
        "</g>\n",
        "<!-- 4&#45;&gt;5 -->\n",
        "<g id=\"edge10\" class=\"edge\"><title>4&#45;&gt;5</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M119.882,-18C128.983,-18 140.099,-18 150.224,-18\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"150.292,-21.5001 160.292,-18 150.292,-14.5001 150.292,-21.5001\"/>\n",
        "<text text-anchor=\"middle\" x=\"140\" y=\"-23.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">a</text>\n",
        "</g>\n",
        "<!-- 1 -->\n",
        "<g id=\"node6\" class=\"node\"><title>1</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"365\" cy=\"-50\" rx=\"17.9762\" ry=\"18.3848\"/>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"365\" cy=\"-50\" rx=\"21.8873\" ry=\"22.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"365\" y=\"-46.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">1</text>\n",
        "</g>\n",
        "<!-- 3&#45;&gt;1 -->\n",
        "<g id=\"edge8\" class=\"edge\"><title>3&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M250.493,-68.941C271.697,-65.4336 306.844,-59.6198 332.616,-55.3568\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"333.378,-58.7783 342.673,-53.6932 332.236,-51.8721 333.378,-58.7783\"/>\n",
        "<text text-anchor=\"middle\" x=\"285\" y=\"-71.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">h</text>\n",
        "</g>\n",
        "<!-- 6 -->\n",
        "<g id=\"node13\" class=\"node\"><title>6</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"285\" cy=\"-18\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"285\" y=\"-14.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">6</text>\n",
        "</g>\n",
        "<!-- 5&#45;&gt;6 -->\n",
        "<g id=\"edge12\" class=\"edge\"><title>5&#45;&gt;6</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M197.951,-18C214.079,-18 237.503,-18 255.991,-18\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"256.213,-21.5001 266.213,-18 256.213,-14.5001 256.213,-21.5001\"/>\n",
        "<text text-anchor=\"middle\" x=\"232\" y=\"-23.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">u</text>\n",
        "</g>\n",
        "<!-- 6&#45;&gt;1 -->\n",
        "<g id=\"edge14\" class=\"edge\"><title>6&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M302.359,-24.9435C311.718,-28.6871 323.542,-33.4169 334.39,-37.7561\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"333.395,-41.1274 343.979,-41.5917 335.994,-34.6281 333.395,-41.1274\"/>\n",
        "<text text-anchor=\"middle\" x=\"323\" y=\"-39.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">s</text>\n",
        "</g>\n",
        "</g>\n",
        "</svg>\n"
       ],
       "text": [
        "<StdVectorFst with 7 states>"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "any_letter=fst.Transducer(isyms,osyms)\n",
      "for sym in 'hkmsau':\n",
      "    any_letter.add_arc(0,1,sym,sym)\n",
      "any_letter[1].final=True\n",
      "\n",
      "consonant=fst.Transducer(isyms,osyms)\n",
      "for sym in 'hkms':\n",
      "    consonant.add_arc(0,1,sym,sym)\n",
      "consonant[1].final=True"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "any_letter"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 6,
       "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.26.3 (20100126.1600)\n",
        " -->\n",
        "<!-- Title: FST Pages: 1 -->\n",
        "<svg width=\"136pt\" height=\"184pt\"\n",
        " viewBox=\"0.00 0.00 136.00 184.25\" 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 180.255)\">\n",
        "<title>FST</title>\n",
        "<polygon fill=\"white\" stroke=\"white\" points=\"-4,5 -4,-180.255 133,-180.255 133,5 -4,5\"/>\n",
        "<!-- 0 -->\n",
        "<g id=\"node1\" class=\"node\"><title>0</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" stroke-width=\"2\" cx=\"19\" cy=\"-74.255\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"19\" y=\"-70.655\" font-family=\"Times Roman,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=\"105\" cy=\"-74.255\" rx=\"17.9762\" ry=\"18.3848\"/>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"105\" cy=\"-74.255\" rx=\"21.8873\" ry=\"22.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"105\" y=\"-70.655\" font-family=\"Times Roman,serif\" font-size=\"14.00\">1</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge2\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M20.8902,-92.4026C23.9771,-111.702 32.0437,-141.324 53,-155.255 75.4077,-170.151 90.1992,-134.265 98.0907,-105.585\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"101.497,-106.392 100.595,-95.8359 94.717,-104.65 101.497,-106.392\"/>\n",
        "<text text-anchor=\"middle\" x=\"60\" y=\"-163.655\" font-family=\"Times Roman,serif\" font-size=\"14.00\">h</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge4\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M27.7931,-90.325C36.6579,-104.195 51.2508,-121.016 67,-114.255 74.0194,-111.241 80.3531,-106.224 85.7472,-100.743\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"88.4837,-102.932 92.4965,-93.1265 83.2448,-98.2894 88.4837,-102.932\"/>\n",
        "<text text-anchor=\"middle\" x=\"60\" y=\"-120.655\" font-family=\"Times Roman,serif\" font-size=\"14.00\">k</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge6\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M37.6607,-74.255C47.7215,-74.255 60.4329,-74.255 72.0945,-74.255\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"72.4028,-77.7551 82.4028,-74.255 72.4027,-70.7551 72.4028,-77.7551\"/>\n",
        "<text text-anchor=\"middle\" x=\"60\" y=\"-79.655\" font-family=\"Times Roman,serif\" font-size=\"14.00\">m</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge8\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M33.3086,-62.3877C39.0613,-58.345 45.9875,-54.3259 53,-52.255 61.5139,-49.7407 70.5116,-51.7586 78.5854,-55.4166\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"77.0969,-58.5911 87.5545,-60.291 80.4395,-52.4407 77.0969,-58.5911\"/>\n",
        "<text text-anchor=\"middle\" x=\"60\" y=\"-57.655\" font-family=\"Times Roman,serif\" font-size=\"14.00\">s</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge10\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M26.4594,-57.4177C32.0991,-46.9395 40.9412,-34.3372 53,-28.255 66.6834,-21.3534 79.602,-32.655 89.1401,-45.7802\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"86.4635,-48.0785 94.8939,-54.4956 92.3053,-44.2219 86.4635,-48.0785\"/>\n",
        "<text text-anchor=\"middle\" x=\"60\" y=\"-33.655\" font-family=\"Times Roman,serif\" font-size=\"14.00\">a</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge12\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M22.0256,-56.3875C25.9505,-39.4203 34.6131,-14.8364 53,-3.25499 72.7707,9.19806 87.4771,-18.5647 96.1143,-42.939\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"92.8798,-44.3064 99.3361,-52.7067 99.5275,-42.1136 92.8798,-44.3064\"/>\n",
        "<text text-anchor=\"middle\" x=\"60\" y=\"-8.65499\" font-family=\"Times Roman,serif\" font-size=\"14.00\">u</text>\n",
        "</g>\n",
        "</g>\n",
        "</svg>\n"
       ],
       "text": [
        "<StdVectorFst with 2 states>"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "umlaut0 = fst.Transducer(isyms,osyms)\n",
      "umlaut0.add_arc(0,1,'u','\u00fc')\n",
      "umlaut0.add_arc(0,1,'a','\u00e4')\n",
      "umlaut0.add_arc(1,2,'u','u')\n",
      "umlaut0[1].final=umlaut0[2].final=True"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "umlaut0"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 8,
       "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.26.3 (20100126.1600)\n",
        " -->\n",
        "<!-- Title: FST Pages: 1 -->\n",
        "<svg width=\"246pt\" height=\"54pt\"\n",
        " viewBox=\"0.00 0.00 246.00 54.20\" 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 50.2022)\">\n",
        "<title>FST</title>\n",
        "<polygon fill=\"white\" stroke=\"white\" points=\"-4,5 -4,-50.2022 243,-50.2022 243,5 -4,5\"/>\n",
        "<!-- 0 -->\n",
        "<g id=\"node1\" class=\"node\"><title>0</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" stroke-width=\"2\" cx=\"19\" cy=\"-24.2022\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"19\" y=\"-20.6022\" font-family=\"Times Roman,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=\"115\" cy=\"-24.2022\" rx=\"17.9762\" ry=\"18.3848\"/>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"115\" cy=\"-24.2022\" rx=\"21.8873\" ry=\"22.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"115\" y=\"-20.6022\" font-family=\"Times Roman,serif\" font-size=\"14.00\">1</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge2\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M37.5098,-24.2022C50.1367,-24.2022 67.209,-24.2022 82.1154,-24.2022\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"82.4923,-27.7023 92.4923,-24.2022 82.4922,-20.7023 82.4923,-27.7023\"/>\n",
        "<text text-anchor=\"middle\" x=\"65\" y=\"-29.6022\" font-family=\"Times Roman,serif\" font-size=\"14.00\">u:\u00fc</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge4\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M33.3086,-12.335C39.0613,-8.29231 45.9875,-4.27315 53,-2.20225 63.2299,0.818794 66.6984,0.564657 77,-2.20225 80.5983,-3.1687 84.2077,-4.56803 87.6928,-6.1997\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"86.0654,-9.29844 96.5349,-10.9238 89.3641,-3.12437 86.0654,-9.29844\"/>\n",
        "<text text-anchor=\"middle\" x=\"65\" y=\"-7.60225\" font-family=\"Times Roman,serif\" font-size=\"14.00\">a:\u00e4</text>\n",
        "</g>\n",
        "<!-- 2 -->\n",
        "<g id=\"node6\" class=\"node\"><title>2</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"215\" cy=\"-24.2022\" rx=\"17.9762\" ry=\"18.3848\"/>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"215\" cy=\"-24.2022\" rx=\"21.8873\" ry=\"22.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"215\" y=\"-20.6022\" font-family=\"Times Roman,serif\" font-size=\"14.00\">2</text>\n",
        "</g>\n",
        "<!-- 1&#45;&gt;2 -->\n",
        "<g id=\"edge6\" class=\"edge\"><title>1&#45;&gt;2</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M137.692,-24.2022C150.861,-24.2022 167.676,-24.2022 182.258,-24.2022\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"182.398,-27.7023 192.398,-24.2022 182.398,-20.7023 182.398,-27.7023\"/>\n",
        "<text text-anchor=\"middle\" x=\"165\" y=\"-29.6022\" font-family=\"Times Roman,serif\" font-size=\"14.00\">u:u</text>\n",
        "</g>\n",
        "</g>\n",
        "</svg>\n"
       ],
       "text": [
        "<StdVectorFst with 3 states>"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "umlaut = any_letter.closure() + consonant + umlaut0 + consonant.closure()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "umlaut"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 10,
       "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.26.3 (20100126.1600)\n",
        " -->\n",
        "<!-- Title: FST Pages: 1 -->\n",
        "<svg width=\"612pt\" height=\"188pt\"\n",
        " viewBox=\"0.00 0.00 612.00 187.59\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
        "<g id=\"graph1\" class=\"graph\" transform=\"scale(0.613226 0.613226) rotate(0) translate(4 301.9)\">\n",
        "<title>FST</title>\n",
        "<polygon fill=\"white\" stroke=\"white\" points=\"-4,5 -4,-301.9 995,-301.9 995,5 -4,5\"/>\n",
        "<!-- 2 -->\n",
        "<g id=\"node1\" class=\"node\"><title>2</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" stroke-width=\"2\" cx=\"19\" cy=\"-52.8996\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"19\" y=\"-49.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">2</text>\n",
        "</g>\n",
        "<!-- 0 -->\n",
        "<g id=\"node3\" class=\"node\"><title>0</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"107\" cy=\"-151.9\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"107\" y=\"-148.3\" font-family=\"Times Roman,serif\" font-size=\"14.00\">0</text>\n",
        "</g>\n",
        "<!-- 2&#45;&gt;0 -->\n",
        "<g id=\"edge2\" class=\"edge\"><title>2&#45;&gt;0</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M31.236,-66.6651C45.9471,-83.2151 70.8017,-111.177 88.012,-130.538\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"85.6083,-133.102 94.8679,-138.251 90.8402,-128.452 85.6083,-133.102\"/>\n",
        "<text text-anchor=\"middle\" x=\"63\" y=\"-116.3\" font-family=\"Times Roman,serif\" font-size=\"14.00\">\u03b5:\u03b5</text>\n",
        "</g>\n",
        "<!-- 3 -->\n",
        "<g id=\"node5\" class=\"node\"><title>3</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"295\" cy=\"-52.8996\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"295\" y=\"-49.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">3</text>\n",
        "</g>\n",
        "<!-- 2&#45;&gt;3 -->\n",
        "<g id=\"edge4\" class=\"edge\"><title>2&#45;&gt;3</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M37.4876,-51.9137C66.3964,-50.4862 124.063,-48.0976 173,-48.8996 204.932,-49.4229 241.546,-50.7163 266.264,-51.6917\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"266.27,-55.1946 276.403,-52.1003 266.552,-48.2003 266.27,-55.1946\"/>\n",
        "<text text-anchor=\"middle\" x=\"157\" y=\"-54.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">\u03b5:\u03b5</text>\n",
        "</g>\n",
        "<!-- 1 -->\n",
        "<g id=\"node7\" class=\"node\"><title>1</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"207\" cy=\"-151.9\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"207\" y=\"-148.3\" font-family=\"Times Roman,serif\" font-size=\"14.00\">1</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge6\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M109.367,-170.013C113.806,-200.825 124.452,-261.333 141,-273.9 152.326,-282.501 161.674,-282.501 173,-273.9 187.867,-262.609 197.97,-212.621 203.088,-180.238\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"206.6,-180.423 204.633,-170.013 199.679,-179.378 206.6,-180.423\"/>\n",
        "<text text-anchor=\"middle\" x=\"157\" y=\"-285.3\" font-family=\"Times Roman,serif\" font-size=\"14.00\">h:h</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge8\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M108.89,-170.047C111.977,-189.346 120.044,-218.968 141,-232.9 152.844,-240.773 161.156,-240.773 173,-232.9 190.6,-221.2 199.108,-198.432 203.211,-180.007\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"206.675,-180.526 205.11,-170.047 199.799,-179.215 206.675,-180.526\"/>\n",
        "<text text-anchor=\"middle\" x=\"157\" y=\"-243.3\" font-family=\"Times Roman,serif\" font-size=\"14.00\">k:k</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge10\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M115.786,-167.817C121.646,-176.689 130.246,-186.926 141,-191.9 153.909,-197.869 160.091,-197.869 173,-191.9 180.562,-188.403 187.058,-182.304 192.286,-175.906\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"195.126,-177.952 198.214,-167.817 189.48,-173.814 195.126,-177.952\"/>\n",
        "<text text-anchor=\"middle\" x=\"157\" y=\"-201.3\" font-family=\"Times Roman,serif\" font-size=\"14.00\">m:m</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge12\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M125.809,-151.9C140.475,-151.9 161.102,-151.9 177.895,-151.9\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"178.275,-155.4 188.275,-151.9 178.275,-148.4 178.275,-155.4\"/>\n",
        "<text text-anchor=\"middle\" x=\"157\" y=\"-157.3\" font-family=\"Times Roman,serif\" font-size=\"14.00\">s:s</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge14\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M121.309,-140.032C127.061,-135.99 133.987,-131.971 141,-129.9 154.64,-125.872 159.36,-125.872 173,-129.9 176.725,-131 180.426,-132.65 183.94,-134.561\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"182.357,-137.699 192.691,-140.032 186.068,-131.763 182.357,-137.699\"/>\n",
        "<text text-anchor=\"middle\" x=\"157\" y=\"-135.3\" font-family=\"Times Roman,serif\" font-size=\"14.00\">a:a</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge16\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M114.033,-134.832C119.58,-123.815 128.482,-110.373 141,-103.9 153.633,-97.3668 160.367,-97.3668 173,-103.9 182.291,-108.704 189.59,-117.347 195.003,-125.989\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"192.02,-127.825 199.967,-134.832 198.125,-124.399 192.02,-127.825\"/>\n",
        "<text text-anchor=\"middle\" x=\"157\" y=\"-109.3\" font-family=\"Times Roman,serif\" font-size=\"14.00\">u:u</text>\n",
        "</g>\n",
        "<!-- 4 -->\n",
        "<g id=\"node16\" class=\"node\"><title>4</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"395\" cy=\"-52.8996\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"395\" y=\"-49.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">4</text>\n",
        "</g>\n",
        "<!-- 3&#45;&gt;4 -->\n",
        "<g id=\"edge22\" class=\"edge\"><title>3&#45;&gt;4</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M303.786,-68.8167C309.646,-77.6892 318.246,-87.9264 329,-92.8996 341.909,-98.8691 348.091,-98.8691 361,-92.8996 368.562,-89.4028 375.058,-83.3036 380.286,-76.9062\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"383.126,-78.9515 386.214,-68.8167 377.48,-74.8138 383.126,-78.9515\"/>\n",
        "<text text-anchor=\"middle\" x=\"345\" y=\"-102.3\" font-family=\"Times Roman,serif\" font-size=\"14.00\">h:h</text>\n",
        "</g>\n",
        "<!-- 3&#45;&gt;4 -->\n",
        "<g id=\"edge24\" class=\"edge\"><title>3&#45;&gt;4</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M313.809,-52.8996C328.475,-52.8996 349.102,-52.8996 365.895,-52.8996\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"366.275,-56.3997 376.275,-52.8996 366.275,-49.3997 366.275,-56.3997\"/>\n",
        "<text text-anchor=\"middle\" x=\"345\" y=\"-58.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">k:k</text>\n",
        "</g>\n",
        "<!-- 3&#45;&gt;4 -->\n",
        "<g id=\"edge26\" class=\"edge\"><title>3&#45;&gt;4</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M309.309,-41.0323C315.061,-36.9897 321.987,-32.9705 329,-30.8996 342.64,-26.8716 347.36,-26.8716 361,-30.8996 364.725,-31.9998 368.426,-33.6498 371.94,-35.5611\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"370.357,-38.6988 380.691,-41.0323 374.068,-32.7634 370.357,-38.6988\"/>\n",
        "<text text-anchor=\"middle\" x=\"345\" y=\"-36.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">m:m</text>\n",
        "</g>\n",
        "<!-- 3&#45;&gt;4 -->\n",
        "<g id=\"edge28\" class=\"edge\"><title>3&#45;&gt;4</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M302.033,-35.8324C307.58,-24.8154 316.482,-11.3729 329,-4.8996 341.633,1.6332 348.367,1.6332 361,-4.8996 370.291,-9.70402 377.59,-18.3474 383.003,-26.9888\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"380.02,-28.8252 387.967,-35.8324 386.125,-25.399 380.02,-28.8252\"/>\n",
        "<text text-anchor=\"middle\" x=\"345\" y=\"-10.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">s:s</text>\n",
        "</g>\n",
        "<!-- 1&#45;&gt;0 -->\n",
        "<g id=\"edge18\" class=\"edge\"><title>1&#45;&gt;0</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M204.488,-134.065C200.911,-116.149 192.466,-89.4479 173,-76.8996 161.046,-69.1939 152.954,-69.1939 141,-76.8996 124.88,-87.2912 116.318,-107.388 111.819,-124.165\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"108.373,-123.532 109.512,-134.065 115.19,-125.12 108.373,-123.532\"/>\n",
        "<text text-anchor=\"middle\" x=\"157\" y=\"-82.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">\u03b5:\u03b5</text>\n",
        "</g>\n",
        "<!-- 1&#45;&gt;3 -->\n",
        "<g id=\"edge20\" class=\"edge\"><title>1&#45;&gt;3</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M219.236,-138.134C233.947,-121.584 258.802,-93.6227 276.012,-74.2611\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"278.84,-76.3476 282.868,-66.5482 273.608,-71.6971 278.84,-76.3476\"/>\n",
        "<text text-anchor=\"middle\" x=\"251\" y=\"-116.3\" font-family=\"Times Roman,serif\" font-size=\"14.00\">\u03b5:\u03b5</text>\n",
        "</g>\n",
        "<!-- 5 -->\n",
        "<g id=\"node21\" class=\"node\"><title>5</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"483\" cy=\"-52.8996\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"483\" y=\"-49.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">5</text>\n",
        "</g>\n",
        "<!-- 4&#45;&gt;5 -->\n",
        "<g id=\"edge30\" class=\"edge\"><title>4&#45;&gt;5</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M413.663,-52.8996C425.446,-52.8996 440.908,-52.8996 454.24,-52.8996\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"454.364,-56.3997 464.364,-52.8996 454.364,-49.3997 454.364,-56.3997\"/>\n",
        "<text text-anchor=\"middle\" x=\"439\" y=\"-58.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">\u03b5:\u03b5</text>\n",
        "</g>\n",
        "<!-- 6 -->\n",
        "<g id=\"node23\" class=\"node\"><title>6</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"575\" cy=\"-52.8996\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"575\" y=\"-49.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">6</text>\n",
        "</g>\n",
        "<!-- 5&#45;&gt;6 -->\n",
        "<g id=\"edge32\" class=\"edge\"><title>5&#45;&gt;6</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M501.618,-52.8996C514.462,-52.8996 531.784,-52.8996 546.373,-52.8996\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"546.41,-56.3997 556.41,-52.8996 546.41,-49.3997 546.41,-56.3997\"/>\n",
        "<text text-anchor=\"middle\" x=\"529\" y=\"-58.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">u:\u00fc</text>\n",
        "</g>\n",
        "<!-- 5&#45;&gt;6 -->\n",
        "<g id=\"edge34\" class=\"edge\"><title>5&#45;&gt;6</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M497.309,-41.0323C503.061,-36.9897 509.987,-32.9705 517,-30.8996 527.23,-27.8786 530.77,-27.8786 541,-30.8996 544.725,-31.9998 548.426,-33.6498 551.94,-35.5611\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"550.357,-38.6988 560.691,-41.0323 554.068,-32.7634 550.357,-38.6988\"/>\n",
        "<text text-anchor=\"middle\" x=\"529\" y=\"-36.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">a:\u00e4</text>\n",
        "</g>\n",
        "<!-- 7 -->\n",
        "<g id=\"node26\" class=\"node\"><title>7</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"667\" cy=\"-90.8996\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"667\" y=\"-87.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">7</text>\n",
        "</g>\n",
        "<!-- 6&#45;&gt;7 -->\n",
        "<g id=\"edge36\" class=\"edge\"><title>6&#45;&gt;7</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M592.304,-60.0471C605.797,-65.6202 624.774,-73.4584 640.223,-79.8396\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"639.194,-83.2014 649.773,-83.7841 641.867,-76.7316 639.194,-83.2014\"/>\n",
        "<text text-anchor=\"middle\" x=\"621\" y=\"-81.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">u:u</text>\n",
        "</g>\n",
        "<!-- 10 -->\n",
        "<g id=\"node28\" class=\"node\"><title>10</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"765\" cy=\"-57.8996\" rx=\"24.3145\" ry=\"24.7487\"/>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"765\" cy=\"-57.8996\" rx=\"28.2444\" ry=\"28.7487\"/>\n",
        "<text text-anchor=\"middle\" x=\"765\" y=\"-54.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">10</text>\n",
        "</g>\n",
        "<!-- 6&#45;&gt;10 -->\n",
        "<g id=\"edge38\" class=\"edge\"><title>6&#45;&gt;10</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M593.567,-50.625C608.3,-48.9397 629.433,-46.7878 648,-45.8996 664.87,-45.0926 669.159,-44.6278 686,-45.8996 699.426,-46.9135 714.026,-48.8834 726.981,-50.9387\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"726.527,-54.411 736.964,-52.5887 727.669,-47.5047 726.527,-54.411\"/>\n",
        "<text text-anchor=\"middle\" x=\"667\" y=\"-51.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">\u03b5:\u03b5</text>\n",
        "</g>\n",
        "<!-- 7&#45;&gt;10 -->\n",
        "<g id=\"edge40\" class=\"edge\"><title>7&#45;&gt;10</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M684.52,-84.9999C696.714,-80.8938 713.419,-75.2688 728.449,-70.2075\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"729.66,-73.4929 738.02,-66.9845 727.426,-66.8589 729.66,-73.4929\"/>\n",
        "<text text-anchor=\"middle\" x=\"711\" y=\"-84.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">\u03b5:\u03b5</text>\n",
        "</g>\n",
        "<!-- 8 -->\n",
        "<g id=\"node30\" class=\"node\"><title>8</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"863\" cy=\"-57.8996\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"863\" y=\"-54.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">8</text>\n",
        "</g>\n",
        "<!-- 10&#45;&gt;8 -->\n",
        "<g id=\"edge52\" class=\"edge\"><title>10&#45;&gt;8</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M793.609,-57.8996C806.409,-57.8996 821.468,-57.8996 834.281,-57.8996\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"834.417,-61.3997 844.417,-57.8996 834.417,-54.3997 834.417,-61.3997\"/>\n",
        "<text text-anchor=\"middle\" x=\"819\" y=\"-63.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">\u03b5:\u03b5</text>\n",
        "</g>\n",
        "<!-- 9 -->\n",
        "<g id=\"node32\" class=\"node\"><title>9</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"967\" cy=\"-57.8996\" rx=\"17.9762\" ry=\"18.3848\"/>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"967\" cy=\"-57.8996\" rx=\"21.8873\" ry=\"22.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"967\" y=\"-54.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">9</text>\n",
        "</g>\n",
        "<!-- 8&#45;&gt;9 -->\n",
        "<g id=\"edge42\" class=\"edge\"><title>8&#45;&gt;9</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M867.679,-75.5906C872.477,-89.8122 881.483,-108.857 897,-117.9 909.288,-125.06 916.54,-124.757 929,-117.9 940.848,-111.379 949.519,-99.4324 955.56,-87.9059\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"958.726,-89.3985 959.852,-78.8637 952.402,-86.3969 958.726,-89.3985\"/>\n",
        "<text text-anchor=\"middle\" x=\"913\" y=\"-128.3\" font-family=\"Times Roman,serif\" font-size=\"14.00\">h:h</text>\n",
        "</g>\n",
        "<!-- 8&#45;&gt;9 -->\n",
        "<g id=\"edge44\" class=\"edge\"><title>8&#45;&gt;9</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M878.199,-68.5684C883.837,-71.9233 890.456,-75.1953 897,-76.8996 910.763,-80.4843 915.158,-80.1672 929,-76.8996 932.06,-76.1773 935.154,-75.1687 938.187,-73.9893\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"939.86,-77.0744 947.545,-69.781 936.99,-70.6902 939.86,-77.0744\"/>\n",
        "<text text-anchor=\"middle\" x=\"913\" y=\"-84.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">k:k</text>\n",
        "</g>\n",
        "<!-- 8&#45;&gt;9 -->\n",
        "<g id=\"edge46\" class=\"edge\"><title>8&#45;&gt;9</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M881.686,-55.9532C886.657,-55.5168 892.027,-55.1186 897,-54.8996 911.208,-54.274 914.789,-54.3395 929,-54.8996 930.728,-54.9677 932.498,-55.0531 934.285,-55.1517\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"934.303,-58.6604 944.513,-55.8296 934.766,-51.6757 934.303,-58.6604\"/>\n",
        "<text text-anchor=\"middle\" x=\"913\" y=\"-60.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">m:m</text>\n",
        "</g>\n",
        "<!-- 8&#45;&gt;9 -->\n",
        "<g id=\"edge48\" class=\"edge\"><title>8&#45;&gt;9</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M876.008,-44.733C881.891,-39.6896 889.258,-34.5206 897,-31.8996 910.471,-27.3391 915.413,-27.6963 929,-31.8996 933.21,-33.2019 937.368,-35.1489 941.303,-37.4026\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"939.704,-40.5381 949.995,-43.0587 943.522,-34.671 939.704,-40.5381\"/>\n",
        "<text text-anchor=\"middle\" x=\"913\" y=\"-37.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">s:s</text>\n",
        "</g>\n",
        "<!-- 9&#45;&gt;8 -->\n",
        "<g id=\"edge50\" class=\"edge\"><title>9&#45;&gt;8</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M958.009,-37.557C951.705,-25.9926 942.06,-12.5315 929,-5.8996 916.319,0.53965 909.509,0.867175 897,-5.8996 886.719,-11.461 879.05,-21.6319 873.623,-31.5133\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"870.359,-30.2194 869.095,-40.7386 876.643,-33.3035 870.359,-30.2194\"/>\n",
        "<text text-anchor=\"middle\" x=\"913\" y=\"-11.2996\" font-family=\"Times Roman,serif\" font-size=\"14.00\">\u03b5:\u03b5</text>\n",
        "</g>\n",
        "</g>\n",
        "</svg>\n"
       ],
       "text": [
        "<StdVectorFst with 11 states>"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "plural=(lex.compose(umlaut)).determinize()\n",
      "plural.remove_epsilon()\n",
      "plural.minimize()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "plural"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 12,
       "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.26.3 (20100126.1600)\n",
        " -->\n",
        "<!-- Title: FST Pages: 1 -->\n",
        "<svg width=\"454pt\" height=\"98pt\"\n",
        " viewBox=\"0.00 0.00 454.00 98.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 94)\">\n",
        "<title>FST</title>\n",
        "<polygon fill=\"white\" stroke=\"white\" points=\"-4,5 -4,-94 451,-94 451,5 -4,5\"/>\n",
        "<!-- 0 -->\n",
        "<g id=\"node1\" class=\"node\"><title>0</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" stroke-width=\"2\" cx=\"19\" cy=\"-41\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"19\" y=\"-37.4\" font-family=\"Times Roman,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=\"119\" cy=\"-70\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"119\" y=\"-66.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">1</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;1 -->\n",
        "<g id=\"edge2\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M36.878,-46.1846C51.9997,-50.5699 73.9192,-56.9266 91.3095,-61.9698\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"90.3605,-65.3387 100.94,-64.7625 92.3102,-58.6157 90.3605,-65.3387\"/>\n",
        "<text text-anchor=\"middle\" x=\"69\" y=\"-64.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">m:m</text>\n",
        "</g>\n",
        "<!-- 2 -->\n",
        "<g id=\"node5\" class=\"node\"><title>2</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"172\" cy=\"-18\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"172\" y=\"-14.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">2</text>\n",
        "</g>\n",
        "<!-- 0&#45;&gt;2 -->\n",
        "<g id=\"edge4\" class=\"edge\"><title>0&#45;&gt;2</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M36.4062,-33.9278C41.6609,-32.0471 47.4969,-30.206 53,-29 83.2293,-22.3754 118.63,-19.7362 142.914,-18.6871\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"143.366,-22.1729 153.231,-18.3083 143.109,-15.1776 143.366,-22.1729\"/>\n",
        "<text text-anchor=\"middle\" x=\"69\" y=\"-34.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">k:k</text>\n",
        "</g>\n",
        "<!-- 3 -->\n",
        "<g id=\"node7\" class=\"node\"><title>3</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"225\" cy=\"-72\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"225\" y=\"-68.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">3</text>\n",
        "</g>\n",
        "<!-- 1&#45;&gt;3 -->\n",
        "<g id=\"edge6\" class=\"edge\"><title>1&#45;&gt;3</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M137.951,-70.3576C154.079,-70.6619 177.503,-71.1038 195.991,-71.4527\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"196.149,-74.9562 206.213,-71.6455 196.281,-67.9574 196.149,-74.9562\"/>\n",
        "<text text-anchor=\"middle\" x=\"172\" y=\"-76.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">a:\u00e4</text>\n",
        "</g>\n",
        "<!-- 4 -->\n",
        "<g id=\"node9\" class=\"node\"><title>4</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"278\" cy=\"-18\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"278\" y=\"-14.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">4</text>\n",
        "</g>\n",
        "<!-- 2&#45;&gt;4 -->\n",
        "<g id=\"edge8\" class=\"edge\"><title>2&#45;&gt;4</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M190.951,-18C207.079,-18 230.503,-18 248.991,-18\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"249.213,-21.5001 259.213,-18 249.213,-14.5001 249.213,-21.5001\"/>\n",
        "<text text-anchor=\"middle\" x=\"225\" y=\"-23.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">u:\u00fc</text>\n",
        "</g>\n",
        "<!-- 5 -->\n",
        "<g id=\"node11\" class=\"node\"><title>5</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"331\" cy=\"-72\" rx=\"17.8879\" ry=\"18.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"331\" y=\"-68.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">5</text>\n",
        "</g>\n",
        "<!-- 3&#45;&gt;5 -->\n",
        "<g id=\"edge10\" class=\"edge\"><title>3&#45;&gt;5</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M243.951,-72C260.079,-72 283.503,-72 301.991,-72\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"302.213,-75.5001 312.213,-72 302.213,-68.5001 302.213,-75.5001\"/>\n",
        "<text text-anchor=\"middle\" x=\"278\" y=\"-77.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">u:u</text>\n",
        "</g>\n",
        "<!-- 6 -->\n",
        "<g id=\"node13\" class=\"node\"><title>6</title>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"423\" cy=\"-39\" rx=\"17.9762\" ry=\"18.3848\"/>\n",
        "<ellipse fill=\"none\" stroke=\"black\" cx=\"423\" cy=\"-39\" rx=\"21.8873\" ry=\"22.3848\"/>\n",
        "<text text-anchor=\"middle\" x=\"423\" y=\"-35.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">6</text>\n",
        "</g>\n",
        "<!-- 4&#45;&gt;6 -->\n",
        "<g id=\"edge12\" class=\"edge\"><title>4&#45;&gt;6</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M296.374,-20.0988C310.939,-21.8102 331.797,-24.3672 350,-27 363.307,-28.9247 377.939,-31.282 390.586,-33.3962\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"390.227,-36.8851 400.67,-35.1001 391.393,-29.9829 390.227,-36.8851\"/>\n",
        "<text text-anchor=\"middle\" x=\"331\" y=\"-32.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">h:h</text>\n",
        "</g>\n",
        "<!-- 5&#45;&gt;6 -->\n",
        "<g id=\"edge14\" class=\"edge\"><title>5&#45;&gt;6</title>\n",
        "<path fill=\"none\" stroke=\"black\" d=\"M348.739,-65.6373C361.042,-61.2242 377.749,-55.2315 392.2,-50.0477\"/>\n",
        "<polygon fill=\"black\" stroke=\"black\" points=\"393.532,-53.2884 401.763,-46.6175 391.169,-46.6994 393.532,-53.2884\"/>\n",
        "<text text-anchor=\"middle\" x=\"375\" y=\"-64.4\" font-family=\"Times Roman,serif\" font-size=\"14.00\">s:s</text>\n",
        "</g>\n",
        "</g>\n",
        "</svg>\n"
       ],
       "text": [
        "<StdVectorFst with 7 states>"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}