Automates_TP2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "tm7J027xlF-e"
   },
   "source": [
    "# Automates finis - TP 2 \n",
    "\n",
    "### Objectif du TP\n",
    "\n",
    "L'objectif de ce TP est d'implémenter la déterminisation d'un automate fini. Cela implique deux étapes : premièrement, étant donné un automate fini (potenitellement) non déterministe donné en entrée, il faut appliquer l'algorithme d'élimination des transitions-$\\varepsilon$. Deuxièmement, il faut appliquer l'algorithme de réduction des transitions de façon à créer des nouveaux états composés par des ensembles d'états joignables avec l'automate initial. Finalement, nous vous conseillons de renommer les états de l'automate déterminisé, par exemple, pour mieux le visualiser avec `to_graphviz`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithme d'élimination des transitions-$\\varepsilon$\n",
    "\n",
    "Dans la bibliothèque `automaton.py` fournie, les transitions-$\\varepsilon$ sont représentées par le symbole `%` dans le fichier d'entrée (utilisez la constante `automaton.EPSILON` pour plus d'élégance ;-). Ainsi, l'automate ci-dessous est une version non déterministe de l'automate qui reconnait l'expresison régulière `a*+b*`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?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.43.0 (0)\n",
       " -->\n",
       "<!-- Title: finite_state_machine Pages: 1 -->\n",
       "<svg width=\"170pt\" height=\"203pt\"\n",
       " viewBox=\"0.00 0.00 170.00 203.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 199)\">\n",
       "<title>finite_state_machine</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-199 166,-199 166,4 -4,4\"/>\n",
       "<text text-anchor=\"middle\" x=\"81\" y=\"-7.8\" font-family=\"Times,serif\" font-size=\"14.00\">astarbstar&#45;epsilon</text>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-140\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-140\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-136.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M131.99,-160.58C130.89,-170.84 133.55,-180 140,-180 144.13,-180 146.71,-176.24 147.74,-170.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"151.24,-170.67 148.01,-160.58 144.25,-170.49 151.24,-170.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-183.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-45\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-45\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-41.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;2 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M131.99,-65.58C130.89,-75.84 133.55,-85 140,-85 144.13,-85 146.71,-81.24 147.74,-75.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"151.24,-75.67 148.01,-65.58 144.25,-75.49 151.24,-75.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-88.8\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- __I__ -->\n",
       "<!-- 0 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"56\" cy=\"-92\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"56\" y=\"-88.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- __I__&#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__I__&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.15,-92C2.67,-92 15.1,-92 27.63,-92\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"27.94,-95.5 37.94,-92 27.94,-88.5 27.94,-95.5\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M72.04,-100.8C83.16,-107.31 98.61,-116.36 111.86,-124.12\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"110.21,-127.2 120.61,-129.24 113.75,-121.16 110.21,-127.2\"/>\n",
       "<text text-anchor=\"middle\" x=\"96\" y=\"-119.8\" font-family=\"Times,serif\" font-size=\"14.00\">ε</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>0&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M72.04,-83.38C83.16,-77.01 98.61,-68.15 111.86,-60.55\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"113.67,-63.55 120.61,-55.54 110.19,-57.48 113.67,-63.55\"/>\n",
       "<text text-anchor=\"middle\" x=\"96\" y=\"-75.8\" font-family=\"Times,serif\" font-size=\"14.00\">ε</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<automaton.Automaton at 0x7f1ffc732580>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from automaton import Automaton\n",
    "a = Automaton(\"astarbstar-epsilon\")\n",
    "source = \"\"\"0 % 1\n",
    "1 a 1\n",
    "0 % 2\n",
    "2 b 2\n",
    "A 1 2\n",
    "\"\"\"\n",
    "a.from_txt(source)\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans l'algorithme d'élimination des transitions-$\\varepsilon$, nous devons tout d'abord identifier un état _k_ dans lequel aboutit une transition-$\\varepsilon$. Disons que c'est l'état 1. Ensuite, nous devons identifier tous les états _q_ menant à _k_ avec une transition-$\\varepsilon$ (en l'occurrence, _q=0_ et _k=1_). Finalement, il faut rajouter des transitions depuis _q=0_ vers tous les états _r_ destination d'une transition qui part de _k_. Ici, _r=1_ et le symbole _x_ de cette nouvelle transition de _q_ vers _r_ est _a_. En somme, il faut rajouter une transition depuis _0_ vers _1_ avec _a_:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?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.43.0 (0)\n",
       " -->\n",
       "<!-- Title: finite_state_machine Pages: 1 -->\n",
       "<svg width=\"171pt\" height=\"203pt\"\n",
       " viewBox=\"0.00 0.00 171.00 203.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 199)\">\n",
       "<title>finite_state_machine</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-199 167,-199 167,4 -4,4\"/>\n",
       "<text text-anchor=\"middle\" x=\"81.5\" y=\"-7.8\" font-family=\"Times,serif\" font-size=\"14.00\">astarbstar&#45;epsilon</text>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"141\" cy=\"-140\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"141\" cy=\"-140\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"141\" y=\"-136.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M132.99,-160.58C131.89,-170.84 134.55,-180 141,-180 145.13,-180 147.71,-176.24 148.74,-170.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"152.24,-170.67 149.01,-160.58 145.25,-170.49 152.24,-170.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"141\" y=\"-183.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"141\" cy=\"-45\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"141\" cy=\"-45\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"141\" y=\"-41.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;2 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>2&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M132.99,-65.58C131.89,-75.84 134.55,-85 141,-85 145.13,-85 147.71,-81.24 148.74,-75.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"152.24,-75.67 149.01,-65.58 145.25,-75.49 152.24,-75.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"141\" y=\"-88.8\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- __I__ -->\n",
       "<!-- 0 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"56\" cy=\"-102\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"56\" y=\"-98.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- __I__&#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__I__&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.15,-102C2.67,-102 15.1,-102 27.63,-102\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"27.94,-105.5 37.94,-102 27.94,-98.5 27.94,-105.5\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M72.61,-109.15C83.46,-114.12 98.25,-120.88 111.2,-126.82\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"110.11,-130.16 120.66,-131.15 113.02,-123.8 110.11,-130.16\"/>\n",
       "<text text-anchor=\"middle\" x=\"96.5\" y=\"-125.8\" font-family=\"Times,serif\" font-size=\"14.00\">ε</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M73.49,-97.37C82.02,-95.83 92.42,-95.32 101,-99 108.74,-102.32 115.68,-108.02 121.47,-114.13\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"119.01,-116.64 128.18,-121.94 124.32,-112.08 119.01,-116.64\"/>\n",
       "<text text-anchor=\"middle\" x=\"96.5\" y=\"-102.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>0&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M71.46,-92.07C83.23,-83.99 100.14,-72.38 114.21,-62.71\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"116.28,-65.53 122.54,-56.99 112.32,-59.76 116.28,-65.53\"/>\n",
       "<text text-anchor=\"middle\" x=\"96.5\" y=\"-80.8\" font-family=\"Times,serif\" font-size=\"14.00\">ε</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<automaton.Automaton at 0x7f1ffc732580>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.add_transition(\"0\",\"a\",\"1\")\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Puis, on peut supprimer la transition-$\\varepsilon$ cible. Ici, l'état _1_ est un état d'acceptation, donc _0_ devient aussi un état d'acceptation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?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.43.0 (0)\n",
       " -->\n",
       "<!-- Title: finite_state_machine Pages: 1 -->\n",
       "<svg width=\"179pt\" height=\"203pt\"\n",
       " viewBox=\"0.00 0.00 179.00 203.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 199)\">\n",
       "<title>finite_state_machine</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-199 175,-199 175,4 -4,4\"/>\n",
       "<text text-anchor=\"middle\" x=\"85.5\" y=\"-7.8\" font-family=\"Times,serif\" font-size=\"14.00\">astarbstar&#45;epsilon</text>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"60\" cy=\"-92\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"60\" cy=\"-92\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"60\" y=\"-88.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"149\" cy=\"-140\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"149\" cy=\"-140\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"149\" y=\"-136.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.88,-102.42C91.7,-108.94 107.14,-117.46 120.33,-124.74\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"119.01,-128 129.46,-129.77 122.39,-121.87 119.01,-128\"/>\n",
       "<text text-anchor=\"middle\" x=\"104.5\" y=\"-120.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"149\" cy=\"-45\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"149\" cy=\"-45\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"149\" y=\"-41.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>0&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.88,-81.8C91.62,-75.46 106.93,-67.19 120.06,-60.09\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"122.02,-63.01 129.16,-55.18 118.7,-56.85 122.02,-63.01\"/>\n",
       "<text text-anchor=\"middle\" x=\"104.5\" y=\"-73.8\" font-family=\"Times,serif\" font-size=\"14.00\">ε</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M140.99,-160.58C139.89,-170.84 142.55,-180 149,-180 153.13,-180 155.71,-176.24 156.74,-170.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"160.24,-170.67 157.01,-160.58 153.25,-170.49 160.24,-170.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"149\" y=\"-183.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;2 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M140.99,-65.58C139.89,-75.84 142.55,-85 149,-85 153.13,-85 155.71,-81.24 156.74,-75.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"160.24,-75.67 157.01,-65.58 153.25,-75.49 160.24,-75.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"149\" y=\"-88.8\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- __I__ -->\n",
       "<!-- __I__&#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__I__&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.17,-92C2.72,-92 14.89,-92 27.67,-92\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"27.86,-95.5 37.86,-92 27.86,-88.5 27.86,-95.5\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<automaton.Automaton at 0x7f1ffc732580>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.remove_transition(\"0\",\"%\",\"1\")\n",
    "a.make_accept(\"0\")\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une fois que l'algorithme est appliqué à toutes les transitions-$\\varepsilon$, le résultat sera celui-ci :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?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.43.0 (0)\n",
       " -->\n",
       "<!-- Title: finite_state_machine Pages: 1 -->\n",
       "<svg width=\"180pt\" height=\"203pt\"\n",
       " viewBox=\"0.00 0.00 180.00 203.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 199)\">\n",
       "<title>finite_state_machine</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-199 176,-199 176,4 -4,4\"/>\n",
       "<text text-anchor=\"middle\" x=\"86\" y=\"-7.8\" font-family=\"Times,serif\" font-size=\"14.00\">astarbstar&#45;epsilon</text>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"60\" cy=\"-92\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"60\" cy=\"-92\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"60\" y=\"-88.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"150\" cy=\"-140\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"150\" cy=\"-140\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"150\" y=\"-136.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.66,-102.18C91.8,-108.8 107.83,-117.54 121.42,-124.96\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"119.91,-128.12 130.36,-129.84 123.26,-121.97 119.91,-128.12\"/>\n",
       "<text text-anchor=\"middle\" x=\"105\" y=\"-120.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"150\" cy=\"-45\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"150\" cy=\"-45\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"150\" y=\"-41.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>0&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.66,-82.03C91.8,-75.55 107.83,-66.99 121.42,-59.73\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"123.19,-62.75 130.36,-54.95 119.89,-56.58 123.19,-62.75\"/>\n",
       "<text text-anchor=\"middle\" x=\"105\" y=\"-73.8\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M141.99,-160.58C140.89,-170.84 143.55,-180 150,-180 154.13,-180 156.71,-176.24 157.74,-170.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"161.24,-170.67 158.01,-160.58 154.25,-170.49 161.24,-170.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"150\" y=\"-183.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;2 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M141.99,-65.58C140.89,-75.84 143.55,-85 150,-85 154.13,-85 156.71,-81.24 157.74,-75.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"161.24,-75.67 158.01,-65.58 154.25,-75.49 161.24,-75.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"150\" y=\"-88.8\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- __I__ -->\n",
       "<!-- __I__&#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__I__&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.17,-92C2.72,-92 14.89,-92 27.67,-92\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"27.86,-95.5 37.86,-92 27.86,-88.5 27.86,-95.5\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<automaton.Automaton at 0x7f1ffc732580>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.add_transition(\"0\",\"b\",\"2\")\n",
    "a.remove_transition(\"0\",\"%\",\"2\")\n",
    "a.make_accept(\"0\") # Il l'est déjà, mais on doit être systématique\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "N'oubliez pas que l'élimination des transitions-$\\varepsilon$ peut créer des états inaccessibles. Pour vous aider, une fonction dans `automaton.py` permet de supprimer les états inaccessibles de l'automate. Voici un exemple de son utilisation sur l'automate ci-dessus auquel on rajoute des états inaccessibles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?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.43.0 (0)\n",
       " -->\n",
       "<!-- Title: finite_state_machine Pages: 1 -->\n",
       "<svg width=\"223pt\" height=\"220pt\"\n",
       " viewBox=\"0.00 0.00 223.00 220.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 216)\">\n",
       "<title>finite_state_machine</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-216 219,-216 219,4 -4,4\"/>\n",
       "<text text-anchor=\"middle\" x=\"107.5\" y=\"-7.8\" font-family=\"Times,serif\" font-size=\"14.00\">astarbstar&#45;epsilon</text>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"103\" cy=\"-66\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"103\" cy=\"-66\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"103\" y=\"-62.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"193\" cy=\"-140\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"193\" cy=\"-140\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"193\" y=\"-136.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M120.55,-79.92C133.83,-91.08 152.65,-106.91 167.65,-119.52\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"165.62,-122.39 175.52,-126.14 170.12,-117.03 165.62,-122.39\"/>\n",
       "<text text-anchor=\"middle\" x=\"148\" y=\"-109.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"193\" cy=\"-45\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"193\" cy=\"-45\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"193\" y=\"-41.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>0&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M124.85,-61.02C135.81,-58.41 149.45,-55.15 161.57,-52.26\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"162.38,-55.67 171.29,-49.94 160.76,-48.86 162.38,-55.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"148\" y=\"-60.8\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M184.99,-160.58C183.89,-170.84 186.55,-180 193,-180 197.13,-180 199.71,-176.24 200.74,-170.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"204.24,-170.67 201.01,-160.58 197.25,-170.49 204.24,-170.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"193\" y=\"-183.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;2 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M184.99,-65.58C183.89,-75.84 186.55,-85 193,-85 197.13,-85 199.71,-81.24 200.74,-75.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"204.24,-75.67 201.01,-65.58 197.25,-75.49 204.24,-75.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"193\" y=\"-88.8\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- __I__ -->\n",
       "<!-- __I__&#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__I__&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M19.06,-66C20.51,-66 47.79,-66 70.68,-66\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"70.77,-69.5 80.77,-66 70.77,-62.5 70.77,-69.5\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-140\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-136.3\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"103\" cy=\"-140\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"103\" y=\"-136.3\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M36.2,-140C47.33,-140 62.06,-140 74.76,-140\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"74.82,-143.5 84.82,-140 74.82,-136.5 74.82,-143.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"58.5\" y=\"-143.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;1 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>4&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M121.39,-140C132.61,-140 147.54,-140 160.77,-140\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"160.93,-143.5 170.93,-140 160.93,-136.5 160.93,-143.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"148\" y=\"-143.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-194\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-190.3\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"103\" cy=\"-194\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"103\" y=\"-190.3\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M36.2,-194C47.33,-194 62.06,-194 74.76,-194\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"74.82,-197.5 84.82,-194 74.82,-190.5 74.82,-197.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"58.5\" y=\"-197.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<automaton.Automaton at 0x7f1ffc732580>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.add_transition(\"3\",\"a\",\"4\")\n",
    "a.add_transition(\"4\",\"a\",\"1\")\n",
    "a.add_transition(\"5\",\"a\",\"6\")\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?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.43.0 (0)\n",
       " -->\n",
       "<!-- Title: finite_state_machine Pages: 1 -->\n",
       "<svg width=\"180pt\" height=\"203pt\"\n",
       " viewBox=\"0.00 0.00 180.00 203.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 199)\">\n",
       "<title>finite_state_machine</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-199 176,-199 176,4 -4,4\"/>\n",
       "<text text-anchor=\"middle\" x=\"86\" y=\"-7.8\" font-family=\"Times,serif\" font-size=\"14.00\">astarbstar&#45;epsilon</text>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"60\" cy=\"-92\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"60\" cy=\"-92\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"60\" y=\"-88.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"150\" cy=\"-140\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"150\" cy=\"-140\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"150\" y=\"-136.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.66,-102.18C91.8,-108.8 107.83,-117.54 121.42,-124.96\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"119.91,-128.12 130.36,-129.84 123.26,-121.97 119.91,-128.12\"/>\n",
       "<text text-anchor=\"middle\" x=\"105\" y=\"-120.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"150\" cy=\"-45\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"150\" cy=\"-45\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"150\" y=\"-41.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>0&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.66,-82.03C91.8,-75.55 107.83,-66.99 121.42,-59.73\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"123.19,-62.75 130.36,-54.95 119.89,-56.58 123.19,-62.75\"/>\n",
       "<text text-anchor=\"middle\" x=\"105\" y=\"-73.8\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M141.99,-160.58C140.89,-170.84 143.55,-180 150,-180 154.13,-180 156.71,-176.24 157.74,-170.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"161.24,-170.67 158.01,-160.58 154.25,-170.49 161.24,-170.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"150\" y=\"-183.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;2 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M141.99,-65.58C140.89,-75.84 143.55,-85 150,-85 154.13,-85 156.71,-81.24 157.74,-75.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"161.24,-75.67 158.01,-65.58 154.25,-75.49 161.24,-75.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"150\" y=\"-88.8\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- __I__ -->\n",
       "<!-- __I__&#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__I__&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.17,-92C2.72,-92 14.89,-92 27.67,-92\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"27.86,-95.5 37.86,-92 27.86,-88.5 27.86,-95.5\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<automaton.Automaton at 0x7f1ffc732580>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.remove_unreachable()\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithme de réduction des transitions\n",
    "\n",
    "La deuxième étape de la déterminisation est la réduction des transitions. Pour l'illustrer, nous partirons de l'automate ci-dessous qui reconnait le langage des mots sur _{a,b}_ qui finissent par _b_, décrit par l'expression régulière _(a+b)*b_:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?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.43.0 (0)\n",
       " -->\n",
       "<!-- Title: finite_state_machine Pages: 1 -->\n",
       "<svg width=\"172pt\" height=\"137pt\"\n",
       " viewBox=\"0.00 0.00 172.00 137.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 133)\">\n",
       "<title>finite_state_machine</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-133 168,-133 168,4 -4,4\"/>\n",
       "<text text-anchor=\"middle\" x=\"82\" y=\"-7.8\" font-family=\"Times,serif\" font-size=\"14.00\">nondeterministe</text>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"142\" cy=\"-45\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"142\" cy=\"-45\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"142\" y=\"-41.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- __I__ -->\n",
       "<!-- 0 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"56\" cy=\"-45\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"56\" y=\"-41.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- __I__&#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__I__&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.15,-45C2.67,-45 15.1,-45 27.63,-45\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"27.94,-48.5 37.94,-45 27.94,-41.5 27.94,-48.5\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M74.4,-45C84.59,-45 97.75,-45 109.68,-45\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"109.74,-48.5 119.74,-45 109.74,-41.5 109.74,-48.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"97\" y=\"-48.8\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;0 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>0&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M52.76,-62.78C52.21,-72.31 53.29,-81 56,-81 57.65,-81 58.69,-77.77 59.13,-73.1\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"62.64,-72.82 59.24,-62.78 55.64,-72.75 62.64,-72.82\"/>\n",
       "<text text-anchor=\"middle\" x=\"56\" y=\"-84.8\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;0 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>0&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M50.68,-62.42C47.65,-79.79 49.43,-99 56,-99 61.29,-99 63.47,-86.56 62.54,-72.65\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"65.98,-71.93 61.32,-62.42 59.03,-72.77 65.98,-71.93\"/>\n",
       "<text text-anchor=\"middle\" x=\"56\" y=\"-102.8\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<automaton.Automaton at 0x7f1ffc7325b0>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from automaton import Automaton\n",
    "source = \"\"\"0 a 0\n",
    "0 b 0\n",
    "0 b 1\n",
    "A 1\"\"\"\n",
    "a = Automaton(\"nondeterministe\")\n",
    "a.from_txt(source)\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour initialiser l'algorithme, nous construisons un ensemble de nouveaux états à traiter. Elle est initialisée avec une liste composé de l'état initial seul (chaque nouvel état de l'automate déterminisé sera une liste d'états de l'automate original) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'0'}]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "new_states = [set([a.initial.name])] # une liste d'ensembles\n",
    "new_states"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ensuite, pour chaque élément de cette liste (qui continuera à grandir), nous constuisons de nouveaux états correspondant à l'ensemble d'états de l'automate initial vers lesquels on peut aller avec chaque symbole. Par exemple, avec _a_ on peut rester dans _0_, et avec _b_ on peut aller dans _0_ et _1_. On va donc rajouter un état à notre liste, et les transitions correspondantes à l'automate déterminisé :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'0'}, {'0', '1'}]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "new_states.append(set([a.statesdict[\"0\"].name, a.statesdict[\"1\"].name]))\n",
    "new_states"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?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.43.0 (0)\n",
       " -->\n",
       "<!-- Title: finite_state_machine Pages: 1 -->\n",
       "<svg width=\"258pt\" height=\"147pt\"\n",
       " viewBox=\"0.00 0.00 258.39 147.19\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 143.19)\">\n",
       "<title>finite_state_machine</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-143.19 254.39,-143.19 254.39,4 -4,4\"/>\n",
       "<text text-anchor=\"middle\" x=\"125.19\" y=\"-7.8\" font-family=\"Times,serif\" font-size=\"14.00\">det</text>\n",
       "<!-- __I__ -->\n",
       "<!-- {&#39;0&#39;} -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>{&#39;0&#39;}</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"71.15\" cy=\"-73.05\" rx=\"33.29\" ry=\"33.29\"/>\n",
       "<text text-anchor=\"middle\" x=\"71.15\" y=\"-69.35\" font-family=\"Times,serif\" font-size=\"14.00\">{&#39;0&#39;}</text>\n",
       "</g>\n",
       "<!-- __I__&#45;&gt;{&#39;0&#39;} -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__I__&#45;&gt;{&#39;0&#39;}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.05,-73.05C1.92,-73.05 13.96,-73.05 27.76,-73.05\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"27.98,-76.55 37.98,-73.05 27.98,-69.55 27.98,-76.55\"/>\n",
       "</g>\n",
       "<!-- {&#39;0&#39;}&#45;&gt;{&#39;0&#39;} -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>{&#39;0&#39;}&#45;&gt;{&#39;0&#39;}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M61.77,-105.01C61.77,-115.67 64.9,-124.19 71.15,-124.19 75.25,-124.19 78,-120.52 79.41,-114.99\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"82.9,-115.34 80.52,-105.01 75.94,-114.56 82.9,-115.34\"/>\n",
       "<text text-anchor=\"middle\" x=\"71.15\" y=\"-127.99\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- {&#39;0&#39;, &#39;1&#39;} -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>{&#39;0&#39;, &#39;1&#39;}</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"200.34\" cy=\"-73.05\" rx=\"50.09\" ry=\"50.09\"/>\n",
       "<text text-anchor=\"middle\" x=\"200.34\" y=\"-69.35\" font-family=\"Times,serif\" font-size=\"14.00\">{&#39;0&#39;, &#39;1&#39;}</text>\n",
       "</g>\n",
       "<!-- {&#39;0&#39;}&#45;&gt;{&#39;0&#39;, &#39;1&#39;} -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>{&#39;0&#39;}&#45;&gt;{&#39;0&#39;, &#39;1&#39;}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M104.57,-73.05C115.38,-73.05 127.79,-73.05 139.99,-73.05\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"140.14,-76.55 150.14,-73.05 140.14,-69.55 140.14,-76.55\"/>\n",
       "<text text-anchor=\"middle\" x=\"127.29\" y=\"-76.85\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<automaton.Automaton at 0x7f1ffc625ee0>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "det = Automaton(\"det\")\n",
    "det.add_transition(str(new_states[0]),\"a\",str(new_states[0]))\n",
    "det.add_transition(str(new_states[0]),\"b\",str(new_states[1]))\n",
    "det"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ensuite, il faudra appliquer la même procédure aux nouvel état _{0,1}_, pour enfin obtenir l'automate déterminisé:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?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.43.0 (0)\n",
       " -->\n",
       "<!-- Title: finite_state_machine Pages: 1 -->\n",
       "<svg width=\"258pt\" height=\"164pt\"\n",
       " viewBox=\"0.00 0.00 258.39 164.09\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 160.09)\">\n",
       "<title>finite_state_machine</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-160.09 254.39,-160.09 254.39,4 -4,4\"/>\n",
       "<text text-anchor=\"middle\" x=\"125.19\" y=\"-7.8\" font-family=\"Times,serif\" font-size=\"14.00\">det</text>\n",
       "<!-- __I__ -->\n",
       "<!-- {&#39;0&#39;} -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>{&#39;0&#39;}</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"71.15\" cy=\"-73.05\" rx=\"33.29\" ry=\"33.29\"/>\n",
       "<text text-anchor=\"middle\" x=\"71.15\" y=\"-69.35\" font-family=\"Times,serif\" font-size=\"14.00\">{&#39;0&#39;}</text>\n",
       "</g>\n",
       "<!-- __I__&#45;&gt;{&#39;0&#39;} -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__I__&#45;&gt;{&#39;0&#39;}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.05,-73.05C1.92,-73.05 13.96,-73.05 27.76,-73.05\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"27.98,-76.55 37.98,-73.05 27.98,-69.55 27.98,-76.55\"/>\n",
       "</g>\n",
       "<!-- {&#39;0&#39;}&#45;&gt;{&#39;0&#39;} -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>{&#39;0&#39;}&#45;&gt;{&#39;0&#39;}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M61.77,-105.01C61.77,-115.67 64.9,-124.19 71.15,-124.19 75.25,-124.19 78,-120.52 79.41,-114.99\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"82.9,-115.34 80.52,-105.01 75.94,-114.56 82.9,-115.34\"/>\n",
       "<text text-anchor=\"middle\" x=\"71.15\" y=\"-127.99\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- {&#39;0&#39;, &#39;1&#39;} -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>{&#39;0&#39;, &#39;1&#39;}</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"200.34\" cy=\"-73.05\" rx=\"50.09\" ry=\"50.09\"/>\n",
       "<text text-anchor=\"middle\" x=\"200.34\" y=\"-69.35\" font-family=\"Times,serif\" font-size=\"14.00\">{&#39;0&#39;, &#39;1&#39;}</text>\n",
       "</g>\n",
       "<!-- {&#39;0&#39;}&#45;&gt;{&#39;0&#39;, &#39;1&#39;} -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>{&#39;0&#39;}&#45;&gt;{&#39;0&#39;, &#39;1&#39;}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M104.57,-73.05C115.38,-73.05 127.79,-73.05 139.99,-73.05\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"140.14,-76.55 150.14,-73.05 140.14,-69.55 140.14,-76.55\"/>\n",
       "<text text-anchor=\"middle\" x=\"127.29\" y=\"-76.85\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- {&#39;0&#39;, &#39;1&#39;}&#45;&gt;{&#39;0&#39;} -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>{&#39;0&#39;, &#39;1&#39;}&#45;&gt;{&#39;0&#39;}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M153.5,-55.19C143.28,-53.04 132.46,-52.18 122.29,-54.05 118.65,-54.71 114.92,-55.63 111.22,-56.71\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"110.01,-53.43 101.6,-59.87 112.2,-60.08 110.01,-53.43\"/>\n",
       "<text text-anchor=\"middle\" x=\"127.29\" y=\"-57.85\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- {&#39;0&#39;, &#39;1&#39;}&#45;&gt;{&#39;0&#39;, &#39;1&#39;} -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>{&#39;0&#39;, &#39;1&#39;}&#45;&gt;{&#39;0&#39;, &#39;1&#39;}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M187.11,-121.36C188.19,-132.72 192.61,-141.09 200.34,-141.09 205.54,-141.09 209.23,-137.31 211.43,-131.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"214.9,-131.87 213.57,-121.36 208.06,-130.41 214.9,-131.87\"/>\n",
       "<text text-anchor=\"middle\" x=\"200.34\" y=\"-144.89\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<automaton.Automaton at 0x7f1ffc625ee0>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "det.add_transition(str(new_states[1]),\"b\",str(new_states[1]))\n",
    "det.add_transition(str(new_states[1]),\"a\",str(new_states[0]))\n",
    "det"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une fois qu'aucun nouvel état est ajouté à _new_states_, on peut arrêter la procédure et ajouter les états d'acceptation dans le nouvel automate, qui sont tous ceux qui contiennent au moins un état d'acceptation de l'automate original:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?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.43.0 (0)\n",
       " -->\n",
       "<!-- Title: finite_state_machine Pages: 1 -->\n",
       "<svg width=\"228pt\" height=\"192pt\"\n",
       " viewBox=\"0.00 0.00 228.39 191.55\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 187.55)\">\n",
       "<title>finite_state_machine</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-187.55 224.39,-187.55 224.39,4 -4,4\"/>\n",
       "<text text-anchor=\"middle\" x=\"110.19\" y=\"-7.8\" font-family=\"Times,serif\" font-size=\"14.00\">det</text>\n",
       "<!-- {&#39;0&#39;, &#39;1&#39;} -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>{&#39;0&#39;, &#39;1&#39;}</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54.05\" cy=\"-96.5\" rx=\"50.09\" ry=\"50.09\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54.05\" cy=\"-96.5\" rx=\"54.09\" ry=\"54.09\"/>\n",
       "<text text-anchor=\"middle\" x=\"54.05\" y=\"-92.8\" font-family=\"Times,serif\" font-size=\"14.00\">{&#39;0&#39;, &#39;1&#39;}</text>\n",
       "</g>\n",
       "<!-- {&#39;0&#39;, &#39;1&#39;}&#45;&gt;{&#39;0&#39;, &#39;1&#39;} -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>{&#39;0&#39;, &#39;1&#39;}&#45;&gt;{&#39;0&#39;, &#39;1&#39;}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M40.22,-148.96C41.57,-160.31 46.18,-168.55 54.05,-168.55 59.33,-168.55 63.15,-164.83 65.49,-158.94\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"68.96,-159.5 67.87,-148.96 62.15,-157.87 68.96,-159.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"54.05\" y=\"-172.35\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- {&#39;0&#39;} -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>{&#39;0&#39;}</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"187.24\" cy=\"-58.5\" rx=\"33.29\" ry=\"33.29\"/>\n",
       "<text text-anchor=\"middle\" x=\"187.24\" y=\"-54.8\" font-family=\"Times,serif\" font-size=\"14.00\">{&#39;0&#39;}</text>\n",
       "</g>\n",
       "<!-- {&#39;0&#39;, &#39;1&#39;}&#45;&gt;{&#39;0&#39;} -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>{&#39;0&#39;, &#39;1&#39;}&#45;&gt;{&#39;0&#39;}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M106.59,-82.87C116.41,-80.17 126.58,-77.31 136.09,-74.5 139.25,-73.57 142.51,-72.58 145.78,-71.58\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"147.04,-74.85 155.54,-68.53 144.95,-68.17 147.04,-74.85\"/>\n",
       "<text text-anchor=\"middle\" x=\"131.09\" y=\"-81.3\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- __I__ -->\n",
       "<!-- __I__&#45;&gt;{&#39;0&#39;} -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__I__&#45;&gt;{&#39;0&#39;}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M55.18,-23.51C57.91,-23.74 102.1,-27.58 136.09,-37.5 139.86,-38.6 143.72,-39.89 147.55,-41.29\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"146.35,-44.58 156.94,-44.93 148.88,-38.05 146.35,-44.58\"/>\n",
       "</g>\n",
       "<!-- {&#39;0&#39;}&#45;&gt;{&#39;0&#39;, &#39;1&#39;} -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>{&#39;0&#39;}&#45;&gt;{&#39;0&#39;, &#39;1&#39;}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M154.04,-56.31C144.89,-56.42 135,-57.24 126.09,-59.5 120.78,-60.85 115.43,-62.65 110.16,-64.75\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"108.61,-61.61 100.82,-68.79 111.39,-68.03 108.61,-61.61\"/>\n",
       "<text text-anchor=\"middle\" x=\"131.09\" y=\"-63.3\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- {&#39;0&#39;}&#45;&gt;{&#39;0&#39;} -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>{&#39;0&#39;}&#45;&gt;{&#39;0&#39;}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M176.74,-89.97C176.63,-100.85 180.13,-109.65 187.24,-109.65 191.9,-109.65 195.01,-105.86 196.57,-100.18\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"200.08,-100.3 197.74,-89.97 193.12,-99.5 200.08,-100.3\"/>\n",
       "<text text-anchor=\"middle\" x=\"187.24\" y=\"-113.45\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<automaton.Automaton at 0x7f1ffc625ee0>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "det.make_accept(str(new_states[1]))\n",
    "det"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les étiquettes d'états sont actuellement des ensembles. Une fois l'algorithme fini, vous pouvez (si vous le souhaitez, c'est pas obligatoire) renommer les états avec des noms plus courts :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?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.43.0 (0)\n",
       " -->\n",
       "<!-- Title: finite_state_machine Pages: 1 -->\n",
       "<svg width=\"134pt\" height=\"143pt\"\n",
       " viewBox=\"0.00 0.00 134.00 142.50\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 138.5)\">\n",
       "<title>finite_state_machine</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-138.5 130,-138.5 130,4 -4,4\"/>\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-7.8\" font-family=\"Times,serif\" font-size=\"14.00\">det</text>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"22\" cy=\"-79.5\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"22\" cy=\"-79.5\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"22\" y=\"-75.8\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M13.99,-100.08C12.89,-110.34 15.55,-119.5 22,-119.5 26.13,-119.5 28.71,-115.74 29.74,-110.34\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"33.24,-110.17 30.01,-100.08 26.25,-109.99 33.24,-110.17\"/>\n",
       "<text text-anchor=\"middle\" x=\"22\" y=\"-123.3\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"108\" cy=\"-56.5\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"108\" y=\"-52.8\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;0 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>1&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M44.27,-77.81C52.98,-76.77 63.09,-75.11 72,-72.5 75.44,-71.49 78.97,-70.2 82.41,-68.8\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"83.98,-71.93 91.69,-64.66 81.13,-65.54 83.98,-71.93\"/>\n",
       "<text text-anchor=\"middle\" x=\"67\" y=\"-79.3\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- __I__ -->\n",
       "<!-- __I__&#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__I__&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M23.06,-23.52C24.66,-24.15 57.38,-37.01 81.49,-46.48\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"80.27,-49.76 90.86,-50.16 82.83,-43.25 80.27,-49.76\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M90.05,-54.95C81.5,-54.64 71.04,-55.02 62,-57.5 57.78,-58.66 53.54,-60.37 49.48,-62.33\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"47.56,-59.39 40.45,-67.24 50.9,-65.54 47.56,-59.39\"/>\n",
       "<text text-anchor=\"middle\" x=\"67\" y=\"-61.3\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;0 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>0&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M100.97,-73.16C99.41,-83.12 101.75,-92.5 108,-92.5 112,-92.5 114.4,-88.65 115.2,-83.27\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"118.7,-83.1 115.03,-73.16 111.7,-83.22 118.7,-83.1\"/>\n",
       "<text text-anchor=\"middle\" x=\"108\" y=\"-96.3\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<automaton.Automaton at 0x7f1ffc625ee0>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "namecount = 0 # On va numéroter les nouveaux états 0, 1, 2...\n",
    "for statename in det.states : # Pour tous les états du nouvel automate    \n",
    "    newname = str(namecount) # transformer int -> str\n",
    "    det.rename_state(statename, newname) # renommer l'état est une fonction de la bibliothèque\n",
    "    namecount = namecount + 1 # incrémente le compteur de nouveaux états\n",
    "det"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "wwbVoN2GlGAh"
   },
   "source": [
    "# Travail à effectuer\n",
    "\n",
    "Vous devez modifier votre programme du TP1 de façon à ce que, au lieu d'afficher \"ERROR\" pour un automate non déterministe, le script maintenant le déterminise puis applique l'algorithme de reconnaissance sur l'automate résultant. Vous développerez donc un programme capable de dire si un mot est reconnu ou non par un automate quelconque, déterministe ou non déterministe. Voici quelques exemples d'exécution de votre programme sur la ligne de commande.\n",
    "\n",
    "```bash\n",
    "$ ./tp2automates.py test/astarbstar-epsilon.af abb\n",
    "NO\n",
    "$ ./tp2automates.py test/astarbstar-nfa.af abb\n",
    "NO\n",
    "$ ./tp2automates.py test/astarbstar-epsilon.af aaa\n",
    "YES\n",
    "$ ./tp2automates.py test/astarbstar-nfa.af bbb\n",
    "YES\n",
    "$ ./tp2automates.py test/astarbstar-nfa.af %\n",
    "YES\n",
    "```\n",
    "\n",
    "Nous vous conseillons de copier les fonctions `is_deterministic` et `recognizes` de `tp1automates.py` vers `tp2automates.py` pour éviter de perdre le travail accompli au TP1 en cas de problème, et pouvoir repartir à zéro si besoin."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Automates_TP1 ",
   "provenance": [],
   "toc_visible": true
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}