index.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`fapy`\n",
    "====="
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A little Python 3 module for finite automata theory and regular expressions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Simple automata fun"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from fapy.finite_automaton import FiniteAutomaton"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In `fapy`, all automata are non deterministic. Being deterministic is a _property_. The same goes for being complete, or epsilon-transition free.\n",
    "\n",
    "We start by defining a simple automaton accepting all words containing at least an `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.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"109pt\" height=\"180pt\"\n",
       " viewBox=\"0.00 0.00 109.00 179.60\" 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 175.6)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-175.6 105,-175.6 105,4 -4,4\"/>\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title></title>\n",
       "<ellipse fill=\"#000000\" stroke=\"#000000\" cx=\"31\" cy=\"-169.8\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- q0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q0</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"58,-131 4,-131 4,-95 58,-95 58,-131\"/>\n",
       "<text text-anchor=\"middle\" x=\"31\" y=\"-109.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n",
       "</g>\n",
       "<!-- &#45;&gt;q0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M31,-167.9102C31,-163.5478 31,-152.2893 31,-141.0942\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"34.5001,-141.0304 31,-131.0304 27.5001,-141.0304 34.5001,-141.0304\"/>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q0 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M58.2408,-119.7434C68.0239,-119.8884 76,-117.6406 76,-113 76,-110.1721 73.0382,-108.2328 68.5105,-107.182\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"68.5146,-103.6683 58.2408,-106.2566 67.8863,-110.64 68.5146,-103.6683\"/>\n",
       "<text text-anchor=\"middle\" x=\"86.5\" y=\"-109.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a, b</text>\n",
       "</g>\n",
       "<!-- q1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>q1</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"58,-40 4,-40 4,-4 58,-4 58,-40\"/>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"62,-44 0,-44 0,0 62,0 62,-44\"/>\n",
       "<text text-anchor=\"middle\" x=\"31\" y=\"-18.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q1 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M31,-94.5848C31,-83.1105 31,-68.0231 31,-54.5774\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"34.5001,-54.2465 31,-44.2465 27.5001,-54.2466 34.5001,-54.2465\"/>\n",
       "<text text-anchor=\"middle\" x=\"34.5\" y=\"-65.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M62.102,-30.6229C72.0865,-30.5345 80,-27.6602 80,-22 80,-18.4624 76.9088,-16.013 72.1528,-14.6519\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"72.4629,-11.1633 62.102,-13.3771 71.5821,-18.1076 72.4629,-11.1633\"/>\n",
       "<text text-anchor=\"middle\" x=\"90.5\" y=\"-18.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a, b</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fa6e82e27f0>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "automaton1 = FiniteAutomaton(\n",
    "    alphabet={'a', 'b'},\n",
    "    states={'q0', 'q1'},\n",
    "    initial_states={'q0'},\n",
    "    accepting_states={'q1'},\n",
    "    transitions={\n",
    "        'q0': [('a', 'q0'), ('b', 'q0'), ('a', 'q1')],\n",
    "        'q1': [('a', 'q1'), ('b', 'q1')]\n",
    "    }\n",
    ")\n",
    "automaton1.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's run some tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Word: \"\", Output: False, Expected: False.\n",
      "Word: \"a\", Output: True, Expected: True.\n",
      "Word: \"b\", Output: False, Expected: False.\n",
      "Word: \"bb\", Output: False, Expected: False.\n",
      "Word: \"bbabb\", Output: True, Expected: True.\n"
     ]
    }
   ],
   "source": [
    "problems = [\n",
    "    ('', False),\n",
    "    ('a', True),\n",
    "    ('b', False),\n",
    "    ('bb', False),\n",
    "    ('bbabb', True)\n",
    "]\n",
    "for problem, solution in problems:\n",
    "    print(f'Word: \"{\"\".join(problem)}\", Output: {automaton1.read(problem)}, Expected: {solution}.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Regular expressions\n",
    "\n",
    "They exist."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(a + b)* a\n"
     ]
    }
   ],
   "source": [
    "from fapy.regular_expression import (\n",
    "    parse_regular_expression,\n",
    "    RegularExpression\n",
    ")\n",
    "\n",
    "reg = parse_regular_expression(\"(a + b)* a\")\n",
    "print(reg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Residuals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((b b a)* + a (b b a)*) c\n"
     ]
    }
   ],
   "source": [
    "from fapy.algorithm_residual import residual\n",
    "\n",
    "print(residual(parse_regular_expression(\"(a + abb) (bba)* c\"), \"abb\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have some algorithms!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Determinization"
   ]
  },
  {
   "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.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"109pt\" height=\"180pt\"\n",
       " viewBox=\"0.00 0.00 109.00 179.60\" 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 175.6)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-175.6 105,-175.6 105,4 -4,4\"/>\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title></title>\n",
       "<ellipse fill=\"#000000\" stroke=\"#000000\" cx=\"31\" cy=\"-169.8\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- q0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q0</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"58,-131 4,-131 4,-95 58,-95 58,-131\"/>\n",
       "<text text-anchor=\"middle\" x=\"31\" y=\"-109.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n",
       "</g>\n",
       "<!-- &#45;&gt;q0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M31,-167.9102C31,-163.5478 31,-152.2893 31,-141.0942\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"34.5001,-141.0304 31,-131.0304 27.5001,-141.0304 34.5001,-141.0304\"/>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q0 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M58.2408,-119.7434C68.0239,-119.8884 76,-117.6406 76,-113 76,-110.1721 73.0382,-108.2328 68.5105,-107.182\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"68.5146,-103.6683 58.2408,-106.2566 67.8863,-110.64 68.5146,-103.6683\"/>\n",
       "<text text-anchor=\"middle\" x=\"79.5\" y=\"-109.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n",
       "</g>\n",
       "<!-- q0,q1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>q0,q1</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"58,-40 4,-40 4,-4 58,-4 58,-40\"/>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"62,-44 0,-44 0,0 62,0 62,-44\"/>\n",
       "<text text-anchor=\"middle\" x=\"31\" y=\"-18.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0,q1</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q0,q1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q0,q1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M31,-94.5848C31,-83.1105 31,-68.0231 31,-54.5774\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"34.5001,-54.2465 31,-44.2465 27.5001,-54.2466 34.5001,-54.2465\"/>\n",
       "<text text-anchor=\"middle\" x=\"34.5\" y=\"-65.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "<!-- q0,q1&#45;&gt;q0,q1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>q0,q1&#45;&gt;q0,q1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M62.102,-30.6229C72.0865,-30.5345 80,-27.6602 80,-22 80,-18.4624 76.9088,-16.013 72.1528,-14.6519\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"72.4629,-11.1633 62.102,-13.3771 71.5821,-18.1076 72.4629,-11.1633\"/>\n",
       "<text text-anchor=\"middle\" x=\"90.5\" y=\"-18.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a, b</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fa6e829c7b8>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from fapy.algorithms import powerset_determinize\n",
    "\n",
    "automaton1_det = powerset_determinize(automaton1)\n",
    "automaton1_det.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Thompson's algorithm\n",
    "\n",
    "It transforms a regular expression into an automaton by induction on the syntax tree of the regular expression.\n"
   ]
  },
  {
   "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.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"340pt\" height=\"1224pt\"\n",
       " viewBox=\"0.00 0.00 340.00 1223.60\" 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 1219.6)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-1219.6 336,-1219.6 336,4 -4,4\"/>\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title></title>\n",
       "<ellipse fill=\"#000000\" stroke=\"#000000\" cx=\"166\" cy=\"-1213.8\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- q6 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>q6</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"193,-1175 139,-1175 139,-1139 193,-1139 193,-1175\"/>\n",
       "<text text-anchor=\"middle\" x=\"166\" y=\"-1153.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q6</text>\n",
       "</g>\n",
       "<!-- &#45;&gt;q6 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>&#45;&gt;q6</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M166,-1211.9102C166,-1207.5478 166,-1196.2893 166,-1185.0942\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"169.5001,-1185.0304 166,-1175.0304 162.5001,-1185.0304 169.5001,-1185.0304\"/>\n",
       "</g>\n",
       "<!-- q7 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q7</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"187,-740 133,-740 133,-704 187,-704 187,-740\"/>\n",
       "<text text-anchor=\"middle\" x=\"160\" y=\"-718.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q7</text>\n",
       "</g>\n",
       "<!-- q8 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>q8</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"187,-653 133,-653 133,-617 187,-617 187,-653\"/>\n",
       "<text text-anchor=\"middle\" x=\"160\" y=\"-631.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q8</text>\n",
       "</g>\n",
       "<!-- q7&#45;&gt;q8 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>q7&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M160,-703.9735C160,-692.1918 160,-676.5607 160,-663.1581\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"163.5001,-663.0033 160,-653.0034 156.5001,-663.0034 163.5001,-663.0033\"/>\n",
       "<text text-anchor=\"middle\" x=\"163.5\" y=\"-674.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q11 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>q11</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"126,-218 72,-218 72,-182 126,-182 126,-218\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-196.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q11</text>\n",
       "</g>\n",
       "<!-- q15 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>q15</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"162,-131 108,-131 108,-95 162,-95 162,-131\"/>\n",
       "<text text-anchor=\"middle\" x=\"135\" y=\"-109.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q15</text>\n",
       "</g>\n",
       "<!-- q11&#45;&gt;q15 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>q11&#45;&gt;q15</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M106.4592,-181.9735C111.431,-169.9585 118.0593,-153.9401 123.6767,-140.3646\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"126.9608,-141.5818 127.5503,-131.0034 120.4927,-138.9053 126.9608,-141.5818\"/>\n",
       "<text text-anchor=\"middle\" x=\"123.5\" y=\"-152.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q9 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>q9</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"187,-566 133,-566 133,-530 187,-530 187,-566\"/>\n",
       "<text text-anchor=\"middle\" x=\"160\" y=\"-544.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q9</text>\n",
       "</g>\n",
       "<!-- q16 -->\n",
       "<g id=\"node17\" class=\"node\">\n",
       "<title>q16</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"187,-479 133,-479 133,-443 187,-443 187,-479\"/>\n",
       "<text text-anchor=\"middle\" x=\"160\" y=\"-457.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q16</text>\n",
       "</g>\n",
       "<!-- q9&#45;&gt;q16 -->\n",
       "<g id=\"edge24\" class=\"edge\">\n",
       "<title>q9&#45;&gt;q16</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M160,-529.9735C160,-518.1918 160,-502.5607 160,-489.1581\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"163.5001,-489.0033 160,-479.0034 156.5001,-489.0034 163.5001,-489.0033\"/>\n",
       "<text text-anchor=\"middle\" x=\"163.5\" y=\"-500.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>q4</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"236,-1088 182,-1088 182,-1052 236,-1052 236,-1088\"/>\n",
       "<text text-anchor=\"middle\" x=\"209\" y=\"-1066.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q4</text>\n",
       "</g>\n",
       "<!-- q0 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>q0</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"226,-1001 172,-1001 172,-965 226,-965 226,-1001\"/>\n",
       "<text text-anchor=\"middle\" x=\"199\" y=\"-979.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n",
       "</g>\n",
       "<!-- q4&#45;&gt;q0 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>q4&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M206.928,-1051.9735C205.5738,-1040.1918 203.7771,-1024.5607 202.2366,-1011.1581\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"205.6885,-1010.5383 201.0694,-1001.0034 198.7342,-1011.3376 205.6885,-1010.5383\"/>\n",
       "<text text-anchor=\"middle\" x=\"207.5\" y=\"-1022.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q2 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>q2</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"298,-1001 244,-1001 244,-965 298,-965 298,-1001\"/>\n",
       "<text text-anchor=\"middle\" x=\"271\" y=\"-979.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n",
       "</g>\n",
       "<!-- q4&#45;&gt;q2 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>q4&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M221.8464,-1051.9735C230.6583,-1039.6085 242.4917,-1023.0036 252.3396,-1009.1847\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"255.2167,-1011.1783 258.17,-1001.0034 249.5162,-1007.1158 255.2167,-1011.1783\"/>\n",
       "<text text-anchor=\"middle\" x=\"246.5\" y=\"-1022.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q1 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>q1</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"226,-914 172,-914 172,-878 226,-878 226,-914\"/>\n",
       "<text text-anchor=\"middle\" x=\"199\" y=\"-892.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M199,-964.9735C199,-953.1918 199,-937.5607 199,-924.1581\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"202.5001,-924.0033 199,-914.0034 195.5001,-924.0034 202.5001,-924.0033\"/>\n",
       "<text text-anchor=\"middle\" x=\"202.5\" y=\"-935.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "<!-- q13 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>q13</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"54,-218 0,-218 0,-182 54,-182 54,-218\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-196.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q13</text>\n",
       "</g>\n",
       "<!-- q13&#45;&gt;q15 -->\n",
       "<g id=\"edge19\" class=\"edge\">\n",
       "<title>q13&#45;&gt;q15</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M49.3777,-181.9735C65.3066,-169.1419 86.9036,-151.7443 104.4216,-137.6326\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"107.0591,-140.0023 112.651,-131.0034 102.6678,-134.551 107.0591,-140.0023\"/>\n",
       "<text text-anchor=\"middle\" x=\"91.5\" y=\"-152.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q5 -->\n",
       "<g id=\"node15\" class=\"node\">\n",
       "<title>q5</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"252,-827 198,-827 198,-791 252,-791 252,-827\"/>\n",
       "<text text-anchor=\"middle\" x=\"225\" y=\"-805.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q5</text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q5 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M204.3872,-877.9735C207.9431,-866.0751 212.6722,-850.2508 216.7037,-836.7606\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"220.1097,-837.5869 219.6197,-827.0034 213.4028,-835.5825 220.1097,-837.5869\"/>\n",
       "<text text-anchor=\"middle\" x=\"216.5\" y=\"-848.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q14 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>q14</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"154,-392 100,-392 100,-356 154,-356 154,-392\"/>\n",
       "<text text-anchor=\"middle\" x=\"127\" y=\"-370.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q14</text>\n",
       "</g>\n",
       "<!-- q12 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>q12</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"54,-305 0,-305 0,-269 54,-269 54,-305\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-283.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q12</text>\n",
       "</g>\n",
       "<!-- q14&#45;&gt;q12 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>q14&#45;&gt;q12</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M106.2799,-355.9735C91.5309,-343.1419 71.5337,-325.7443 55.3133,-311.6326\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"57.5353,-308.9265 47.6935,-305.0034 52.9407,-314.2076 57.5353,-308.9265\"/>\n",
       "<text text-anchor=\"middle\" x=\"86.5\" y=\"-326.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q10 -->\n",
       "<g id=\"node16\" class=\"node\">\n",
       "<title>q10</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"126,-305 72,-305 72,-269 126,-269 126,-305\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-283.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q10</text>\n",
       "</g>\n",
       "<!-- q14&#45;&gt;q10 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>q14&#45;&gt;q10</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M121.1984,-355.9735C117.369,-344.0751 112.2761,-328.2508 107.9345,-314.7606\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"111.1896,-313.4502 104.7942,-305.0034 104.5262,-315.5948 111.1896,-313.4502\"/>\n",
       "<text text-anchor=\"middle\" x=\"118.5\" y=\"-326.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q12&#45;&gt;q13 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>q12&#45;&gt;q13</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M27,-268.9735C27,-257.1918 27,-241.5607 27,-228.1581\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"30.5001,-228.0033 27,-218.0034 23.5001,-228.0034 30.5001,-228.0033\"/>\n",
       "<text text-anchor=\"middle\" x=\"30.5\" y=\"-239.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n",
       "</g>\n",
       "<!-- q6&#45;&gt;q7 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>q6&#45;&gt;q7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M158.5518,-1138.6713C152.1694,-1121.294 144,-1094.3042 144,-1070 144,-1070 144,-1070 144,-809 144,-789.0329 148.127,-766.9069 152.1889,-749.9652\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"155.6119,-750.7052 154.6722,-740.1521 148.8259,-748.9879 155.6119,-750.7052\"/>\n",
       "<text text-anchor=\"middle\" x=\"147.5\" y=\"-935.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q6&#45;&gt;q4 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>q6&#45;&gt;q4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M174.9096,-1138.9735C180.9058,-1126.8418 188.9192,-1110.6287 195.6701,-1096.9698\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"198.8085,-1098.519 200.1018,-1088.0034 192.5332,-1095.4173 198.8085,-1098.519\"/>\n",
       "<text text-anchor=\"middle\" x=\"193.5\" y=\"-1109.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q3 -->\n",
       "<g id=\"node18\" class=\"node\">\n",
       "<title>q3</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"298,-914 244,-914 244,-878 298,-878 298,-914\"/>\n",
       "<text text-anchor=\"middle\" x=\"271\" y=\"-892.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q3</text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M271,-964.9735C271,-953.1918 271,-937.5607 271,-924.1581\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"274.5001,-924.0033 271,-914.0034 267.5001,-924.0034 274.5001,-924.0033\"/>\n",
       "<text text-anchor=\"middle\" x=\"274.5\" y=\"-935.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n",
       "</g>\n",
       "<!-- q15&#45;&gt;q14 -->\n",
       "<g id=\"edge23\" class=\"edge\">\n",
       "<title>q15&#45;&gt;q14</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M135.6922,-131.02C136.8458,-165.0533 138.6916,-241.1066 135,-305 134.2253,-318.4088 132.6104,-333.2104 131.0331,-345.655\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"127.5209,-345.5173 129.6787,-355.8901 134.4604,-346.4357 127.5209,-345.5173\"/>\n",
       "<text text-anchor=\"middle\" x=\"141.5\" y=\"-239.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q17 -->\n",
       "<g id=\"node19\" class=\"node\">\n",
       "<title>q17</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"192,-40 138,-40 138,-4 192,-4 192,-40\"/>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"196,-44 134,-44 134,0 196,0 196,-44\"/>\n",
       "<text text-anchor=\"middle\" x=\"165\" y=\"-18.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q17</text>\n",
       "</g>\n",
       "<!-- q15&#45;&gt;q17 -->\n",
       "<g id=\"edge22\" class=\"edge\">\n",
       "<title>q15&#45;&gt;q17</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M141.0709,-94.5848C144.9286,-82.8833 150.025,-67.4241 154.5229,-53.7806\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"157.859,-54.8396 157.666,-44.2465 151.2109,-52.6479 157.859,-54.8396\"/>\n",
       "<text text-anchor=\"middle\" x=\"155.5\" y=\"-65.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q8&#45;&gt;q9 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>q8&#45;&gt;q9</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M160,-616.9735C160,-605.1918 160,-589.5607 160,-576.1581\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"163.5001,-576.0033 160,-566.0034 156.5001,-576.0034 163.5001,-576.0033\"/>\n",
       "<text text-anchor=\"middle\" x=\"163.5\" y=\"-587.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "<!-- q5&#45;&gt;q7 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>q5&#45;&gt;q7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M211.532,-790.9735C202.2937,-778.6085 189.8877,-762.0036 179.5633,-748.1847\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"182.24,-745.9196 173.4508,-740.0034 176.6322,-750.1093 182.24,-745.9196\"/>\n",
       "<text text-anchor=\"middle\" x=\"199.5\" y=\"-761.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q5&#45;&gt;q4 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>q5&#45;&gt;q4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M252.2633,-823.3642C271.502,-835.1758 295.7725,-853.879 307,-878 330.0688,-927.5608 332.1793,-952.4774 307,-1001 294.0854,-1025.8875 267.6143,-1043.6924 245.4363,-1054.9754\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"243.7293,-1051.9129 236.2463,-1059.4133 246.7733,-1058.2164 243.7293,-1051.9129\"/>\n",
       "<text text-anchor=\"middle\" x=\"328.5\" y=\"-935.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q10&#45;&gt;q11 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>q10&#45;&gt;q11</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M99,-268.9735C99,-257.1918 99,-241.5607 99,-228.1581\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"102.5001,-228.0033 99,-218.0034 95.5001,-228.0034 102.5001,-228.0033\"/>\n",
       "<text text-anchor=\"middle\" x=\"102.5\" y=\"-239.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "<!-- q16&#45;&gt;q14 -->\n",
       "<g id=\"edge20\" class=\"edge\">\n",
       "<title>q16&#45;&gt;q14</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M153.1624,-442.9735C148.6049,-430.9585 142.529,-414.9401 137.3797,-401.3646\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"140.648,-400.112 133.8289,-392.0034 134.103,-402.5947 140.648,-400.112\"/>\n",
       "<text text-anchor=\"middle\" x=\"149.5\" y=\"-413.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q16&#45;&gt;q17 -->\n",
       "<g id=\"edge21\" class=\"edge\">\n",
       "<title>q16&#45;&gt;q17</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M171.0126,-442.7079C180.269,-425.5766 192,-398.9449 192,-374 192,-374 192,-374 192,-113 192,-92.7497 185.7789,-70.9728 179.3091,-53.8007\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"182.4654,-52.266 175.5162,-44.2685 175.9614,-54.854 182.4654,-52.266\"/>\n",
       "<text text-anchor=\"middle\" x=\"195.5\" y=\"-239.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "<!-- q3&#45;&gt;q5 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>q3&#45;&gt;q5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M261.4688,-877.9735C255.0543,-865.8418 246.4818,-849.6287 239.2599,-835.9698\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"242.2874,-834.2077 234.519,-827.0034 236.0992,-837.4797 242.2874,-834.2077\"/>\n",
       "<text text-anchor=\"middle\" x=\"253.5\" y=\"-848.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">ε</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fa6e82aa9e8>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from fapy.algorithms import thompson\n",
    "\n",
    "alphabet = {'a', 'b'}\n",
    "automaton = thompson(\n",
    "    parse_regular_expression('(a + b)* a (a + b)*'),\n",
    "    alphabet\n",
    ")\n",
    "automaton.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Glushkov's algorithm\n",
    "\n",
    "It transforms a regular expression into an equivalent automaton."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "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.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"97pt\" height=\"370pt\"\n",
       " viewBox=\"0.00 0.00 97.00 369.60\" 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 365.6)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-365.6 93,-365.6 93,4 -4,4\"/>\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title></title>\n",
       "<ellipse fill=\"#000000\" stroke=\"#000000\" cx=\"31\" cy=\"-359.8\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"58,-317 4,-317 4,-281 58,-281 58,-317\"/>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"62,-321 0,-321 0,-277 62,-277 62,-321\"/>\n",
       "<text text-anchor=\"middle\" x=\"31\" y=\"-295.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n",
       "</g>\n",
       "<!-- &#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M31,-357.7771C31,-353.3914 31,-342.4945 31,-331.2579\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"34.5001,-331.02 31,-321.02 27.5001,-331.0201 34.5001,-331.02\"/>\n",
       "</g>\n",
       "<!-- a0 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>a0</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"58,-222 4,-222 4,-186 58,-186 58,-222\"/>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"62,-226 0,-226 0,-182 62,-182 62,-226\"/>\n",
       "<text text-anchor=\"middle\" x=\"31\" y=\"-200.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a0</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;a0 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>0&#45;&gt;a0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M31,-276.9663C31,-264.9427 31,-249.8283 31,-236.4785\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"34.5001,-236.2433 31,-226.2433 27.5001,-236.2433 34.5001,-236.2433\"/>\n",
       "<text text-anchor=\"middle\" x=\"34.5\" y=\"-247.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "<!-- a1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>a1</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"89,-131 35,-131 35,-95 89,-95 89,-131\"/>\n",
       "<text text-anchor=\"middle\" x=\"62\" y=\"-109.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a1</text>\n",
       "</g>\n",
       "<!-- b2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>b2</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"70,-40 16,-40 16,-4 70,-4 70,-40\"/>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"74,-44 12,-44 12,0 74,0 74,-44\"/>\n",
       "<text text-anchor=\"middle\" x=\"43\" y=\"-18.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b2</text>\n",
       "</g>\n",
       "<!-- a1&#45;&gt;b2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>a1&#45;&gt;b2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M52.3604,-94.7687C49.8469,-89.2105 47.4414,-82.9844 46,-77 44.2649,-69.7963 43.3053,-61.9148 42.8108,-54.4256\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"46.2986,-54.0579 42.3888,-44.2109 39.3046,-54.3469 46.2986,-54.0579\"/>\n",
       "<text text-anchor=\"middle\" x=\"49.5\" y=\"-65.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n",
       "</g>\n",
       "<!-- b2&#45;&gt;a1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>b2&#45;&gt;a1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M47.6449,-44.2465C50.1906,-56.439 53.3723,-71.6779 56.093,-84.7084\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"52.685,-85.5113 58.1551,-94.5848 59.5373,-84.0805 52.685,-85.5113\"/>\n",
       "<text text-anchor=\"middle\" x=\"57.5\" y=\"-65.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "<!-- b2&#45;&gt;a0 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>b2&#45;&gt;a0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M33.6462,-44.2288C28.1744,-58.4606 21.8061,-77.4798 19,-95 14.8859,-120.6862 18.5824,-150.0054 22.9236,-171.7617\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"19.5543,-172.7426 25.0751,-181.7854 26.3985,-171.2735 19.5543,-172.7426\"/>\n",
       "<text text-anchor=\"middle\" x=\"22.5\" y=\"-109.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "<!-- a0&#45;&gt;a1 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>a0&#45;&gt;a1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M38.5042,-181.9714C42.7309,-169.5642 48.0499,-153.9504 52.5576,-140.7179\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"55.9035,-141.7501 55.8151,-131.1556 49.2774,-139.4928 55.9035,-141.7501\"/>\n",
       "<text text-anchor=\"middle\" x=\"52.5\" y=\"-152.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "<!-- a0&#45;&gt;a0 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>a0&#45;&gt;a0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M62.102,-212.6229C72.0865,-212.5345 80,-209.6602 80,-204 80,-200.4624 76.9088,-198.013 72.1528,-196.6519\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"72.4629,-193.1633 62.102,-195.3771 71.5821,-200.1076 72.4629,-193.1633\"/>\n",
       "<text text-anchor=\"middle\" x=\"83.5\" y=\"-200.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fa6e82aaba8>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from fapy.algorithms import glushkov\n",
    "\n",
    "automaton = glushkov(parse_regular_expression('(a (ab)*)*'))\n",
    "automaton.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Brozozwski's algorithm\n",
    "\n",
    "It transforms a finite automaton into an equivalent regular expression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(a a a)* b\n"
     ]
    },
    {
     "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.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"183pt\" height=\"267pt\"\n",
       " viewBox=\"0.00 0.00 183.00 266.60\" 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 262.6)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-262.6 179,-262.6 179,4 -4,4\"/>\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title></title>\n",
       "<ellipse fill=\"#000000\" stroke=\"#000000\" cx=\"107\" cy=\"-256.8\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- q0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q0</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"134,-218 80,-218 80,-182 134,-182 134,-218\"/>\n",
       "<text text-anchor=\"middle\" x=\"107\" y=\"-196.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n",
       "</g>\n",
       "<!-- &#45;&gt;q0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M107,-254.9102C107,-250.5478 107,-239.2893 107,-228.0942\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"110.5001,-228.0304 107,-218.0304 103.5001,-228.0304 110.5001,-228.0304\"/>\n",
       "</g>\n",
       "<!-- q3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>q3</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"58,-127 4,-127 4,-91 58,-91 58,-127\"/>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"62,-131 0,-131 0,-87 62,-87 62,-131\"/>\n",
       "<text text-anchor=\"middle\" x=\"31\" y=\"-105.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q3</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M91.6203,-181.5848C81.4681,-169.4289 67.9291,-153.2178 56.2216,-139.1996\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"58.6761,-136.6783 49.5795,-131.2465 53.3033,-141.1654 58.6761,-136.6783\"/>\n",
       "<text text-anchor=\"middle\" x=\"79.5\" y=\"-152.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n",
       "</g>\n",
       "<!-- q1 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>q1</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"134,-127 80,-127 80,-91 134,-91 134,-127\"/>\n",
       "<text text-anchor=\"middle\" x=\"107\" y=\"-105.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M107,-181.5848C107,-168.9209 107,-151.8558 107,-137.4541\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"110.5001,-137.0772 107,-127.0773 103.5001,-137.0773 110.5001,-137.0772\"/>\n",
       "<text text-anchor=\"middle\" x=\"110.5\" y=\"-152.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "<!-- q2 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>q2</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"175,-36 121,-36 121,0 175,0 175,-36\"/>\n",
       "<text text-anchor=\"middle\" x=\"148\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q2 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M115.297,-90.5848C121.1146,-77.6726 128.9936,-60.1849 135.5603,-45.6101\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"138.9385,-46.6324 139.8553,-36.0773 132.5564,-43.7569 138.9385,-46.6324\"/>\n",
       "<text text-anchor=\"middle\" x=\"135.5\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q0 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M149.5949,-36.3749C151.0186,-59.0466 151.7155,-98.5711 143,-131 139.0597,-145.6613 131.6433,-160.7447 124.5612,-173.0554\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"121.4132,-171.4995 119.2737,-181.8761 127.4172,-175.0985 121.4132,-171.4995\"/>\n",
       "<text text-anchor=\"middle\" x=\"153.5\" y=\"-105.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fa6e82aacf8>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from fapy.algorithms import brozozwski\n",
    "\n",
    "automaton = FiniteAutomaton(\n",
    "    alphabet={'a', 'b'},\n",
    "    states={'q0', 'q1', 'q2', 'q3'},\n",
    "    initial_states={'q0'},\n",
    "    accepting_states={'q3'},\n",
    "    transitions={\n",
    "        'q0': [('a', 'q1'), ('b', 'q3')],\n",
    "        'q1': [('a', 'q2')],\n",
    "        'q2': [('a', 'q0')]\n",
    "    }\n",
    ")\n",
    "print(brozozwski(automaton))\n",
    "automaton.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Brozozwski's minimization algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "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.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"895pt\" height=\"441pt\"\n",
       " viewBox=\"0.00 0.00 895.00 440.60\" 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 436.6)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-436.6 891,-436.6 891,4 -4,4\"/>\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title></title>\n",
       "<ellipse fill=\"#000000\" stroke=\"#000000\" cx=\"578\" cy=\"-430.8\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"862,-392 294,-392 294,-356 862,-356 862,-392\"/>\n",
       "<text text-anchor=\"middle\" x=\"578\" y=\"-370.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8</text>\n",
       "</g>\n",
       "<!-- &#45;&gt;q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>&#45;&gt;q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M578,-428.9102C578,-424.5478 578,-413.2893 578,-402.0942\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"581.5001,-402.0304 578,-392.0304 574.5001,-402.0304 581.5001,-402.0304\"/>\n",
       "</g>\n",
       "<!-- q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8&#45;&gt;q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8&#45;&gt;q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M862.2504,-377.9798C873.4994,-376.9438 880,-375.6172 880,-374 880,-372.964 877.3322,-372.0472 872.4571,-371.2497\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"872.5972,-367.7414 862.2504,-370.0202 871.76,-374.6912 872.5972,-367.7414\"/>\n",
       "<text text-anchor=\"middle\" x=\"883.5\" y=\"-370.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n",
       "</g>\n",
       "<!-- q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"730,-305 0,-305 0,-269 730,-269 730,-305\"/>\n",
       "<text text-anchor=\"middle\" x=\"365\" y=\"-283.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8</text>\n",
       "</g>\n",
       "<!-- q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8&#45;&gt;q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8&#45;&gt;q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M533.8663,-355.9735C500.3089,-342.267 453.9966,-323.3507 418.3587,-308.7944\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"419.6582,-305.5445 409.0772,-305.0034 417.0113,-312.0248 419.6582,-305.5445\"/>\n",
       "<text text-anchor=\"middle\" x=\"487.5\" y=\"-326.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "<!-- q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8,q0,q11,q12,q2,q3,q4,q5,q7,q8 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8,q0,q11,q12,q2,q3,q4,q5,q7,q8</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"763.5,-218 26.5,-218 26.5,-182 763.5,-182 763.5,-218\"/>\n",
       "<text text-anchor=\"middle\" x=\"395\" y=\"-196.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8,q0,q11,q12,q2,q3,q4,q5,q7,q8</text>\n",
       "</g>\n",
       "<!-- q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8,q0,q11,q12,q2,q3,q4,q5,q7,q8&#45;&gt;q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8,q0,q11,q12,q2,q3,q4,q5,q7,q8&#45;&gt;q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M617.8745,-218.0188C683.5375,-228.238 743.3911,-244.1803 764,-269 797.0422,-308.7935 738.8586,-336.3949 679.0509,-353.2766\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"677.7918,-349.992 669.0628,-355.9966 679.6311,-356.746 677.7918,-349.992\"/>\n",
       "<text text-anchor=\"middle\" x=\"776.5\" y=\"-283.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n",
       "</g>\n",
       "<!-- q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8,q0,q11,q12,q2,q3,q4,q5,q7,q8&#45;&gt;q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8,q0,q11,q12,q2,q3,q4,q5,q7,q8&#45;&gt;q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M388.7919,-218.0034C384.6908,-229.8967 379.2345,-245.72 374.5817,-259.2132\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"371.1672,-258.3788 371.216,-268.9735 377.7848,-260.6608 371.1672,-258.3788\"/>\n",
       "<text text-anchor=\"middle\" x=\"385.5\" y=\"-239.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "<!-- q13,q14,q16,q20,q22,q23,q14,q15,q16,q20,q21,q23,q14,q16,q19,q20,q21,q23 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>q13,q14,q16,q20,q22,q23,q14,q15,q16,q20,q21,q23,q14,q16,q19,q20,q21,q23</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"617.5,-127 172.5,-127 172.5,-91 617.5,-91 617.5,-127\"/>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"621.5,-131 168.5,-131 168.5,-87 621.5,-87 621.5,-131\"/>\n",
       "<text text-anchor=\"middle\" x=\"395\" y=\"-105.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q13,q14,q16,q20,q22,q23,q14,q15,q16,q20,q21,q23,q14,q16,q19,q20,q21,q23</text>\n",
       "</g>\n",
       "<!-- q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8,q0,q11,q12,q2,q3,q4,q5,q7,q8&#45;&gt;q13,q14,q16,q20,q22,q23,q14,q15,q16,q20,q21,q23,q14,q16,q19,q20,q21,q23 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8,q0,q11,q12,q2,q3,q4,q5,q7,q8&#45;&gt;q13,q14,q16,q20,q22,q23,q14,q15,q16,q20,q21,q23,q14,q16,q19,q20,q21,q23</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M395,-181.5848C395,-170.1105 395,-155.0231 395,-141.5774\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"398.5001,-141.2465 395,-131.2465 391.5001,-141.2466 398.5001,-141.2465\"/>\n",
       "<text text-anchor=\"middle\" x=\"398.5\" y=\"-152.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">c</text>\n",
       "</g>\n",
       "<!-- q17,q18 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>q17,q18</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"425.5,-36 364.5,-36 364.5,0 425.5,0 425.5,-36\"/>\n",
       "<text text-anchor=\"middle\" x=\"395\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q17,q18</text>\n",
       "</g>\n",
       "<!-- q17,q18&#45;&gt;q13,q14,q16,q20,q22,q23,q14,q15,q16,q20,q21,q23,q14,q16,q19,q20,q21,q23 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>q17,q18&#45;&gt;q13,q14,q16,q20,q22,q23,q14,q15,q16,q20,q21,q23,q14,q16,q19,q20,q21,q23</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M395,-36.1556C395,-47.8111 395,-63.2722 395,-76.9511\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"391.5001,-76.9714 395,-86.9714 398.5001,-76.9715 391.5001,-76.9714\"/>\n",
       "<text text-anchor=\"middle\" x=\"398.5\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n",
       "</g>\n",
       "<!-- q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8&#45;&gt;q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8,q0,q11,q12,q2,q3,q4,q5,q7,q8 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8&#45;&gt;q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8,q0,q11,q12,q2,q3,q4,q5,q7,q8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M363.553,-268.542C363.395,-258.6154 364.2171,-246.3271 368,-236 369.1555,-232.8456 370.6846,-229.7352 372.4291,-226.743\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"375.4968,-228.4522 378.1512,-218.1953 369.6798,-224.5582 375.4968,-228.4522\"/>\n",
       "<text text-anchor=\"middle\" x=\"371.5\" y=\"-239.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n",
       "</g>\n",
       "<!-- q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8&#45;&gt;q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8&#45;&gt;q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q1,q10,q2,q4,q5,q7,q8,q9,q0,q11,q12,q2,q3,q4,q5,q7,q8,q0,q2,q3,q4,q5,q7,q8,q0,q2,q4,q6,q7,q8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M730.3449,-291.195C741.6095,-290.0595 748,-288.6611 748,-287 748,-285.9358 745.3773,-284.9795 740.5307,-284.1311\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"740.7131,-280.6254 730.3449,-282.805 739.8093,-287.5668 740.7131,-280.6254\"/>\n",
       "<text text-anchor=\"middle\" x=\"751.5\" y=\"-283.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "<!-- q13,q14,q16,q20,q22,q23,q14,q15,q16,q20,q21,q23,q14,q16,q19,q20,q21,q23&#45;&gt;q17,q18 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>q13,q14,q16,q20,q22,q23,q14,q15,q16,q20,q21,q23,q14,q16,q19,q20,q21,q23&#45;&gt;q17,q18</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M386.2942,-86.8925C383.3618,-76.8948 381.231,-64.9012 383,-54 383.4399,-51.2891 384.0548,-48.5064 384.7759,-45.7473\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"388.1708,-46.6132 387.7308,-36.0275 381.4734,-44.5771 388.1708,-46.6132\"/>\n",
       "<text text-anchor=\"middle\" x=\"386.5\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n",
       "</g>\n",
       "<!-- q13,q14,q16,q20,q22,q23,q14,q15,q16,q20,q21,q23,q14,q16,q19,q20,q21,q23&#45;&gt;q13,q14,q16,q20,q22,q23,q14,q15,q16,q20,q21,q23,q14,q16,q19,q20,q21,q23 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>q13,q14,q16,q20,q22,q23,q14,q15,q16,q20,q21,q23,q14,q16,q19,q20,q21,q23&#45;&gt;q13,q14,q16,q20,q22,q23,q14,q15,q16,q20,q21,q23,q14,q16,q19,q20,q21,q23</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M621.7007,-114.5442C632.9034,-113.1615 639.5,-111.3135 639.5,-109 639.5,-107.5179 636.7927,-106.2269 631.9016,-105.1268\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"632.135,-101.6185 621.7007,-103.4558 631.0033,-108.5264 632.135,-101.6185\"/>\n",
       "<text text-anchor=\"middle\" x=\"643\" y=\"-105.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fa6e82e20b8>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from fapy.algorithms import brozozwski_minimize\n",
    "\n",
    "alphabet = {'a', 'b', 'c'}\n",
    "automaton = thompson(\n",
    "    parse_regular_expression('(a + b)* a b c (a + bb)*'),\n",
    "    alphabet\n",
    ")\n",
    "minimized_automaton = brozozwski_minimize(automaton)\n",
    "minimized_automaton.draw()"
   ]
  }
 ],
 "metadata": {
  "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}