examples/fa_quiz.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a05bd1f9-ec2b-45e5-b89f-d4797c3b000e",
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "cf416a45-26f4-46ee-a49d-1193ab091f02",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "sys.path.insert(0, \"..\")\n",
    "from tcs.tools.tools import Tools\n",
    "from tcs.automata.fa.dfa import DFA\n",
    "from tcs.automata.fa.nfa import NFA\n",
    "from tcs.regexpr.reg_expression import RegEx"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3822c65-cb28-405c-812f-c66d3e5b9503",
   "metadata": {},
   "source": [
    "Definire un ASFD che riconosce il linguaggio $L\\subseteq\\{0,1\\}^*$ definito\n",
    "come $$L = \\{w| w \\text{ ogni } 0 \\text{ in } w \\text{ è seguito immediatamente da almeno due } 1 \\}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "b7ab43ee-a28d-4761-86e6-5cd5bf11bcb5",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa0 = DFA(\n",
    "    states={'q0', 'q1', 'q2'},\n",
    "    input_symbols={'0', '1'},\n",
    "    delta={\n",
    "        'q0': {'0': 'q1', '1': 'q0'},\n",
    "        'q1': {'1': 'q2'},\n",
    "        'q2': {'1': 'q0'}\n",
    "    },\n",
    "    initial_state='q0',\n",
    "    final_states={'q0'}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "7a5f44fb-60aa-463b-a4f4-e7d05d5e129f",
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"225pt\" height=\"89pt\"\n viewBox=\"0.00 0.00 224.89 89.30\" 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 85.2964)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-85.2964 220.8893,-85.2964 220.8893,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"24.1482\" cy=\"-24.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"24.1482\" cy=\"-24.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"24.1482\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\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=\"M15.658,-47.126C14.8494,-57.4058 17.6795,-66.2964 24.1482,-66.2964 28.2923,-66.2964 30.943,-62.6477 32.1004,-57.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"35.6066,-57.2966 32.6384,-47.126 28.6163,-56.9276 35.6066,-57.2966\"/>\n<text text-anchor=\"middle\" x=\"24.1482\" y=\"-70.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q1 -->\n<g id=\"node2\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"112.4446\" cy=\"-61.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"112.4446\" y=\"-57.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n</g>\n<!-- q0&#45;&gt;q1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M46.4291,-33.4849C57.9583,-38.3161 72.1492,-44.2627 84.4157,-49.4029\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"83.1773,-52.6788 93.753,-53.3156 85.8827,-46.2227 83.1773,-52.6788\"/>\n<text text-anchor=\"middle\" x=\"70.2964\" y=\"-47.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2 -->\n<g id=\"node3\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"196.7411\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"196.7411\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q1&#45;&gt;q2 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q1&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M131.1527,-52.9367C142.1754,-48.0986 156.3343,-41.8838 168.6739,-36.4677\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"170.3352,-39.5608 178.0852,-32.3368 167.5217,-33.1511 170.3352,-39.5608\"/>\n<text text-anchor=\"middle\" x=\"154.5928\" y=\"-46.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q2&#45;&gt;q0 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q2&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M176.5631,-21.3776C163.9525,-19.7875 147.3589,-17.9515 132.5928,-17.1482 114.7098,-16.1754 110.1825,-16.232 92.2964,-17.1482 81.2249,-17.7153 69.1811,-18.7975 58.341,-19.9444\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"57.9405,-16.4673 48.3876,-21.0492 58.7128,-23.4246 57.9405,-16.4673\"/>\n<text text-anchor=\"middle\" x=\"112.4446\" y=\"-20.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fc898174580>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa0.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "352fa25e-5ce5-41b7-9bc3-cd7e4e26200b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q0\t 0111011011\n",
      "q1\t 111011011\n",
      "q2\t 11011011\n",
      "q0\t 1011011\n",
      "q0\t 011011\n",
      "q1\t 11011\n",
      "q2\t 1011\n",
      "q0\t 011\n",
      "q1\t 11\n",
      "q2\t 1\n",
      "q0\t _\n",
      "Completed computation: string accepted\n"
     ]
    }
   ],
   "source": [
    "dfa0.report_computation(Tools.tokens('0111011011'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c698f748",
   "metadata": {},
   "source": [
    "Automa equivalente con $\\delta$ totale"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "0a6b9333",
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"309pt\" height=\"109pt\"\n viewBox=\"0.00 0.00 309.19 109.30\" 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 105.2964)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-105.2964 305.1857,-105.2964 305.1857,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"24.1482\" cy=\"-29.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"24.1482\" cy=\"-29.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"24.1482\" y=\"-25.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\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=\"M15.658,-52.126C14.8494,-62.4058 17.6795,-71.2964 24.1482,-71.2964 28.2923,-71.2964 30.943,-67.6477 32.1004,-62.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"35.6066,-62.2966 32.6384,-52.126 28.6163,-61.9276 35.6066,-62.2966\"/>\n<text text-anchor=\"middle\" x=\"24.1482\" y=\"-75.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q1 -->\n<g id=\"node2\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"112.4446\" cy=\"-66.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"112.4446\" y=\"-62.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n</g>\n<!-- q0&#45;&gt;q1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M46.4291,-38.4849C57.9583,-43.3161 72.1492,-49.2627 84.4157,-54.4029\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"83.1773,-57.6788 93.753,-58.3156 85.8827,-51.2227 83.1773,-57.6788\"/>\n<text text-anchor=\"middle\" x=\"70.2964\" y=\"-52.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2 -->\n<g id=\"node3\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"196.7411\" cy=\"-20.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"196.7411\" y=\"-16.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q1&#45;&gt;q2 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q1&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M130.3217,-56.3928C141.8331,-50.1111 157.0086,-41.83 169.9477,-34.7692\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"171.7882,-37.7521 178.8897,-29.8896 168.4351,-31.6074 171.7882,-37.7521\"/>\n<text text-anchor=\"middle\" x=\"154.5928\" y=\"-47.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q* -->\n<g id=\"node4\" class=\"node\">\n<title>q*</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"281.0375\" cy=\"-48.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"281.0375\" y=\"-44.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q*</text>\n</g>\n<!-- q1&#45;&gt;q* -->\n<g id=\"edge4\" class=\"edge\">\n<title>q1&#45;&gt;q*</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M132.6699,-64.4828C140.7377,-63.7956 150.108,-62.9688 158.5928,-62.1482 196.0959,-58.5212 205.4748,-57.5968 242.8893,-53.1482 245.4429,-52.8446 248.0913,-52.5192 250.7482,-52.1855\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"251.3831,-55.6327 260.8547,-50.8853 250.4898,-48.6899 251.3831,-55.6327\"/>\n<text text-anchor=\"middle\" x=\"196.7411\" y=\"-63.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</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=\"M176.3075,-20.0377C155.2379,-20.0414 121.4416,-20.3754 92.2964,-22.1482 81.2308,-22.8213 69.1887,-23.9323 58.3482,-25.073\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"57.9538,-21.5951 48.394,-26.1625 58.7155,-28.5536 57.9538,-21.5951\"/>\n<text text-anchor=\"middle\" x=\"112.4446\" y=\"-25.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q2&#45;&gt;q* -->\n<g id=\"edge6\" class=\"edge\">\n<title>q2&#45;&gt;q*</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M215.8692,-26.5018C226.5712,-30.0566 240.1294,-34.5601 252.1042,-38.5377\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"251.0997,-41.892 261.6932,-41.7228 253.3064,-35.2489 251.0997,-41.892\"/>\n<text text-anchor=\"middle\" x=\"238.8893\" y=\"-37.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q*&#45;&gt;q* -->\n<g id=\"edge7\" class=\"edge\">\n<title>q*&#45;&gt;q*</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M273.4874,-66.991C272.2044,-77.0931 274.7211,-86.2964 281.0375,-86.2964 285.0839,-86.2964 287.571,-82.5194 288.4986,-77.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"291.9998,-77.0213 288.5876,-66.991 285,-76.96 291.9998,-77.0213\"/>\n<text text-anchor=\"middle\" x=\"281.0375\" y=\"-90.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fc897abcac0>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa0.total.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "692597e3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q0\t 0111011010\n",
      "q1\t 111011010\n",
      "q2\t 11011010\n",
      "q0\t 1011010\n",
      "q0\t 011010\n",
      "q1\t 11010\n",
      "q2\t 1010\n",
      "q0\t 010\n",
      "q1\t 10\n",
      "q2\t 0\n",
      "q*\t _\n",
      "Completed computation: string rejected\n"
     ]
    }
   ],
   "source": [
    "dfa0.total.report_computation(Tools.tokens('0111011010'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82837c77-77a8-4aa2-84f2-0cff9a9e4496",
   "metadata": {},
   "source": [
    "Definire un ASFD che riconosce il linguaggio $L\\subseteq\\{0,1\\}^*$ definito come $$L = \\{w| w\\not=\\varepsilon \\text{ e il primo simbolo di } w \\text{ e\n",
    "l'ultimo sono uguali } \\}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "a98b1d4a-495c-44d4-be74-b7451ecfae0a",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa1 = DFA(\n",
    "    states={'q0', 'q1', 'q2', 'q3', 'q4'},\n",
    "    input_symbols={'0', '1'},\n",
    "    delta={\n",
    "        'q0': {'0': 'q1', '1': 'q2'},\n",
    "        'q1': {'0': 'q1', '1': 'q3'},\n",
    "        'q2': {'0': 'q4', '1': 'q2'},\n",
    "        'q3': {'0': 'q1', '1': 'q3'},\n",
    "        'q4': {'0': 'q4', '1': 'q2'}\n",
    "    },\n",
    "    initial_state='q0',\n",
    "    final_states={'q1', 'q2'}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "b5f4b056-9bbf-43e9-ba52-5ef2977dd4b1",
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"225pt\" height=\"191pt\"\n viewBox=\"0.00 0.00 224.89 191.30\" 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.2964)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-187.2964 220.8893,-187.2964 220.8893,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"20.1482\" cy=\"-73.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-69.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q2 -->\n<g id=\"node2\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"108.4446\" cy=\"-123.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"108.4446\" cy=\"-123.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"108.4446\" y=\"-119.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q0&#45;&gt;q2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q0&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M38.0163,-83.2665C49.5623,-89.8046 64.8787,-98.4779 78.2787,-106.066\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"76.7532,-109.2244 87.1796,-111.1063 80.2025,-103.1332 76.7532,-109.2244\"/>\n<text text-anchor=\"middle\" x=\"62.2964\" y=\"-101.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q1 -->\n<g id=\"node3\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"108.4446\" cy=\"-24.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"108.4446\" cy=\"-24.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"108.4446\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n</g>\n<!-- q0&#45;&gt;q1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M38.0163,-63.2323C49.5623,-56.8249 64.8787,-48.3251 78.2787,-40.8888\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"80.1341,-43.862 87.1796,-35.9492 76.7374,-37.7413 80.1341,-43.862\"/>\n<text text-anchor=\"middle\" x=\"62.2964\" y=\"-54.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2&#45;&gt;q2 -->\n<g id=\"edge6\" class=\"edge\">\n<title>q2&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M99.9544,-146.126C99.1458,-156.4058 101.9759,-165.2964 108.4446,-165.2964 112.5887,-165.2964 115.2394,-161.6477 116.3968,-156.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"119.903,-156.2966 116.9349,-146.126 112.9127,-155.9276 119.903,-156.2966\"/>\n<text text-anchor=\"middle\" x=\"108.4446\" y=\"-169.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q4 -->\n<g id=\"node5\" class=\"node\">\n<title>q4</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"196.7411\" cy=\"-130.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"196.7411\" y=\"-126.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q4</text>\n</g>\n<!-- q2&#45;&gt;q4 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q2&#45;&gt;q4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M132.572,-125.061C143.0195,-125.8892 155.3647,-126.868 166.4224,-127.7446\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"166.2802,-131.2442 176.5256,-128.5456 166.8335,-124.2661 166.2802,-131.2442\"/>\n<text text-anchor=\"middle\" x=\"154.5928\" y=\"-129.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q1&#45;&gt;q1 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q1&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M99.9544,-47.126C99.1458,-57.4058 101.9759,-66.2964 108.4446,-66.2964 112.5887,-66.2964 115.2394,-62.6477 116.3968,-57.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"119.903,-57.2966 116.9349,-47.126 112.9127,-56.9276 119.903,-57.2966\"/>\n<text text-anchor=\"middle\" x=\"108.4446\" y=\"-70.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q3 -->\n<g id=\"node4\" class=\"node\">\n<title>q3</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"196.7411\" cy=\"-32.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"196.7411\" y=\"-28.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q3</text>\n</g>\n<!-- q1&#45;&gt;q3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q1&#45;&gt;q3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M131.9335,-30.0768C137.974,-31.3491 144.4912,-32.504 150.5928,-33.1482 154.1288,-33.5215 155.0376,-33.1948 158.5928,-33.1482 161.1433,-33.1148 163.7895,-33.0688 166.4449,-33.0148\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"166.6344,-36.5114 176.5489,-32.7763 166.4691,-29.5133 166.6344,-36.5114\"/>\n<text text-anchor=\"middle\" x=\"154.5928\" y=\"-36.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q3&#45;&gt;q1 -->\n<g id=\"edge7\" class=\"edge\">\n<title>q3&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M179.0868,-21.8353C172.8277,-18.723 165.5959,-15.7174 158.5928,-14.1482 153.0161,-12.8986 147.073,-12.9098 141.3004,-13.6267\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"140.3728,-10.2407 131.2098,-15.5595 141.6897,-17.1157 140.3728,-10.2407\"/>\n<text text-anchor=\"middle\" x=\"154.5928\" y=\"-17.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q3&#45;&gt;q3 -->\n<g id=\"edge8\" class=\"edge\">\n<title>q3&#45;&gt;q3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M189.191,-50.991C187.908,-61.0931 190.4247,-70.2964 196.7411,-70.2964 200.7875,-70.2964 203.2746,-66.5194 204.2022,-61.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"207.7033,-61.0213 204.2911,-50.991 200.7036,-60.96 207.7033,-61.0213\"/>\n<text text-anchor=\"middle\" x=\"196.7411\" y=\"-74.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q4&#45;&gt;q2 -->\n<g id=\"edge10\" class=\"edge\">\n<title>q4&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M180.5605,-117.7311C174.0905,-113.5034 166.3416,-109.3034 158.5928,-107.1482 152.2371,-105.3805 145.4783,-105.8819 139.0491,-107.5133\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"137.6498,-104.2929 129.3227,-110.8434 139.9173,-110.9155 137.6498,-104.2929\"/>\n<text text-anchor=\"middle\" x=\"154.5928\" y=\"-110.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q4&#45;&gt;q4 -->\n<g id=\"edge9\" class=\"edge\">\n<title>q4&#45;&gt;q4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M189.191,-148.991C187.908,-159.0931 190.4247,-168.2964 196.7411,-168.2964 200.7875,-168.2964 203.2746,-164.5194 204.2022,-159.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"207.7033,-159.0213 204.2911,-148.991 200.7036,-158.96 207.7033,-159.0213\"/>\n<text text-anchor=\"middle\" x=\"196.7411\" y=\"-172.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fc898174520>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa1.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "759d058a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q0\t 1100100101\n",
      "q2\t 100100101\n",
      "q2\t 00100101\n",
      "q4\t 0100101\n",
      "q4\t 100101\n",
      "q2\t 00101\n",
      "q4\t 0101\n",
      "q4\t 101\n",
      "q2\t 01\n",
      "q4\t 1\n",
      "q2\t _\n",
      "Completed computation: string accepted\n"
     ]
    }
   ],
   "source": [
    "dfa1.report_computation(Tools.tokens('1100100101'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "762b3821",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa1_c = dfa1.complement"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "1b94f3c7",
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"233pt\" height=\"194pt\"\n viewBox=\"0.00 0.00 232.89 194.30\" 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 190.2964)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-190.2964 228.8893,-190.2964 228.8893,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"24.1482\" cy=\"-67.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"24.1482\" cy=\"-67.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"24.1482\" y=\"-63.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q1 -->\n<g id=\"node4\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"112.4446\" cy=\"-113.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"112.4446\" y=\"-109.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n</g>\n<!-- q0&#45;&gt;q1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M45.9743,-78.519C57.8573,-84.7097 72.6683,-92.4258 85.2916,-99.0022\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"83.9477,-102.2486 94.4335,-103.7649 87.182,-96.0405 83.9477,-102.2486\"/>\n<text text-anchor=\"middle\" x=\"70.2964\" y=\"-95.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2 -->\n<g id=\"node5\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"112.4446\" cy=\"-22.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"112.4446\" y=\"-18.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q0&#45;&gt;q2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q0&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M45.9743,-56.0246C57.8573,-49.9685 72.6683,-42.4201 85.2916,-35.9867\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"87.1131,-38.9867 94.4335,-31.3275 83.9346,-32.75 87.1131,-38.9867\"/>\n<text text-anchor=\"middle\" x=\"70.2964\" y=\"-47.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q4 -->\n<g id=\"node2\" class=\"node\">\n<title>q4</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"200.7411\" cy=\"-24.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"200.7411\" cy=\"-24.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"200.7411\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q4</text>\n</g>\n<!-- q4&#45;&gt;q4 -->\n<g id=\"edge9\" class=\"edge\">\n<title>q4&#45;&gt;q4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M192.2508,-47.126C191.4422,-57.4058 194.2723,-66.2964 200.7411,-66.2964 204.8851,-66.2964 207.5358,-62.6477 208.6933,-57.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"212.1994,-57.2966 209.2313,-47.126 205.2091,-56.9276 212.1994,-57.2966\"/>\n<text text-anchor=\"middle\" x=\"200.7411\" y=\"-70.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q4&#45;&gt;q2 -->\n<g id=\"edge10\" class=\"edge\">\n<title>q4&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M178.4255,-13.9586C172.1425,-11.5667 165.2135,-9.3626 158.5928,-8.1482 152.5787,-7.0451 146.2403,-7.7107 140.252,-9.2257\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"139.0161,-5.948 130.6239,-12.4149 141.2172,-12.593 139.0161,-5.948\"/>\n<text text-anchor=\"middle\" x=\"154.5928\" y=\"-11.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q3 -->\n<g id=\"node3\" class=\"node\">\n<title>q3</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"200.7411\" cy=\"-129.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"200.7411\" cy=\"-129.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"200.7411\" y=\"-125.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q3</text>\n</g>\n<!-- q3&#45;&gt;q3 -->\n<g id=\"edge8\" class=\"edge\">\n<title>q3&#45;&gt;q3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M192.2508,-152.126C191.4422,-162.4058 194.2723,-171.2964 200.7411,-171.2964 204.8851,-171.2964 207.5358,-167.6477 208.6933,-162.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"212.1994,-162.2966 209.2313,-152.126 205.2091,-161.9276 212.1994,-162.2966\"/>\n<text text-anchor=\"middle\" x=\"200.7411\" y=\"-175.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q3&#45;&gt;q1 -->\n<g id=\"edge7\" class=\"edge\">\n<title>q3&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M182.2312,-113.4561C175.2739,-108.515 167.0029,-103.6871 158.5928,-101.1482 152.7036,-99.3703 146.3448,-99.6358 140.2853,-100.9081\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"139.093,-97.6111 130.5059,-103.8169 141.0888,-104.3206 139.093,-97.6111\"/>\n<text text-anchor=\"middle\" x=\"154.5928\" y=\"-104.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q1&#45;&gt;q3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q1&#45;&gt;q3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M132.4805,-116.7789C142.6336,-118.6187 155.2412,-120.9033 166.8478,-123.0065\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"166.2391,-126.4531 176.703,-124.7923 167.4873,-119.5653 166.2391,-126.4531\"/>\n<text text-anchor=\"middle\" x=\"154.5928\" y=\"-124.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q1&#45;&gt;q1 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q1&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M104.8946,-131.991C103.6115,-142.0931 106.1282,-151.2964 112.4446,-151.2964 116.4911,-151.2964 118.9781,-147.5194 119.9058,-142.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"123.4069,-142.0213 119.9947,-131.991 116.4072,-141.96 123.4069,-142.0213\"/>\n<text text-anchor=\"middle\" x=\"112.4446\" y=\"-155.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2&#45;&gt;q4 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q2&#45;&gt;q4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M132.5904,-25.2874C138.3865,-26.055 144.7273,-26.7655 150.5928,-27.1482 155.7373,-27.4839 161.1797,-27.5047 166.5081,-27.338\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"166.7006,-30.8328 176.5061,-26.82 166.3383,-23.8422 166.7006,-30.8328\"/>\n<text text-anchor=\"middle\" x=\"154.5928\" y=\"-30.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2&#45;&gt;q2 -->\n<g id=\"edge6\" class=\"edge\">\n<title>q2&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M104.8946,-40.991C103.6115,-51.0931 106.1282,-60.2964 112.4446,-60.2964 116.4911,-60.2964 118.9781,-56.5194 119.9058,-51.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"123.4069,-51.0213 119.9947,-40.991 116.4072,-50.96 123.4069,-51.0213\"/>\n<text text-anchor=\"middle\" x=\"112.4446\" y=\"-64.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fc897abcdc0>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa1_c.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "5501ebc9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q0\t 1100100101\n",
      "q2\t 100100101\n",
      "q2\t 00100101\n",
      "q4\t 0100101\n",
      "q4\t 100101\n",
      "q2\t 00101\n",
      "q4\t 0101\n",
      "q4\t 101\n",
      "q2\t 01\n",
      "q4\t 1\n",
      "q2\t _\n",
      "Completed computation: string rejected\n"
     ]
    }
   ],
   "source": [
    "dfa1_c.report_computation(Tools.tokens('1100100101'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f10235aa",
   "metadata": {},
   "source": [
    "Definire un ASFD che riconosce il linguaggio $L\\subseteq\\{0,1\\}^*$ definito come $$L = \\{w| \\mid w\\mid = 7i,\\; i\\geq 0 \\}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "46f37668-f965-4ec4-a9ac-7459435047a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa2 = DFA(\n",
    "    states={'q0', 'q1', 'q2', 'q3', 'q4', 'q5', 'q6'},\n",
    "    input_symbols={'0', '1'},\n",
    "    delta={\n",
    "        'q0': {'0': 'q1', '1': 'q1'},\n",
    "        'q1': {'0': 'q2', '1': 'q2'},\n",
    "        'q2': {'0': 'q3', '1': 'q3'},\n",
    "        'q3': {'0': 'q4', '1': 'q4'},\n",
    "        'q4': {'0': 'q5', '1': 'q5'},\n",
    "        'q5': {'0': 'q6', '1': 'q6'},\n",
    "        'q6': {'0': 'q0', '1': 'q0'}\n",
    "    },\n",
    "    initial_state='q0',\n",
    "    final_states={'q0'}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "c8628dd2-e86e-4f05-895e-d6d08e29da11",
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"504pt\" height=\"72pt\"\n viewBox=\"0.00 0.00 504.00 72.35\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(.8102 .8102) rotate(0) translate(4 85.2964)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-85.2964 618.075,-85.2964 618.075,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"24.1482\" cy=\"-24.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"24.1482\" cy=\"-24.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"24.1482\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q1 -->\n<g id=\"node2\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"122.4446\" cy=\"-56.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"122.4446\" y=\"-52.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n</g>\n<!-- q0&#45;&gt;q1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M47.4431,-31.7318C61.2814,-36.2368 78.9425,-41.9863 93.65,-46.7742\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"92.6847,-50.1407 103.277,-49.9083 94.8517,-43.4846 92.6847,-50.1407\"/>\n<text text-anchor=\"middle\" x=\"75.2964\" y=\"-45.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q2 -->\n<g id=\"node3\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"216.7411\" cy=\"-57.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"216.7411\" y=\"-53.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q1&#45;&gt;q2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q1&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M142.9056,-56.3652C155.5095,-56.4989 171.9073,-56.6728 186.0474,-56.8227\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"186.2835,-60.3253 196.3201,-56.9317 186.3578,-53.3257 186.2835,-60.3253\"/>\n<text text-anchor=\"middle\" x=\"169.5928\" y=\"-59.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q3 -->\n<g id=\"node4\" class=\"node\">\n<title>q3</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"311.0375\" cy=\"-61.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"311.0375\" y=\"-57.4482\" 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=\"M237.202,-58.0162C249.8059,-58.5508 266.2037,-59.2464 280.3438,-59.8462\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"280.4771,-63.3549 290.6165,-60.282 280.7738,-56.3612 280.4771,-63.3549\"/>\n<text text-anchor=\"middle\" x=\"263.8893\" y=\"-62.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q4 -->\n<g id=\"node5\" class=\"node\">\n<title>q4</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"405.3339\" cy=\"-60.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"405.3339\" y=\"-56.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q4</text>\n</g>\n<!-- q3&#45;&gt;q4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q3&#45;&gt;q4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M331.4984,-60.9312C344.1023,-60.7976 360.5001,-60.6237 374.6402,-60.4737\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"374.9506,-63.9707 384.9129,-60.3648 374.8763,-56.9711 374.9506,-63.9707\"/>\n<text text-anchor=\"middle\" x=\"358.1857\" y=\"-63.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q5 -->\n<g id=\"node6\" class=\"node\">\n<title>q5</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"499.6303\" cy=\"-58.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"499.6303\" y=\"-54.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q5</text>\n</g>\n<!-- q4&#45;&gt;q5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q4&#45;&gt;q5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M425.7948,-59.7142C438.3987,-59.4469 454.7966,-59.0991 468.9367,-58.7992\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"469.2858,-62.2927 479.2093,-58.5813 469.1373,-55.2943 469.2858,-62.2927\"/>\n<text text-anchor=\"middle\" x=\"452.4821\" y=\"-62.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q6 -->\n<g id=\"node7\" class=\"node\">\n<title>q6</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"593.9268\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"593.9268\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q6</text>\n</g>\n<!-- q5&#45;&gt;q6 -->\n<g id=\"edge6\" class=\"edge\">\n<title>q5&#45;&gt;q6</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M518.7126,-51.2678C532.1329,-46.4289 550.3231,-39.8702 565.4531,-34.4148\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"566.6529,-37.7029 574.8728,-31.0184 564.2785,-31.1178 566.6529,-37.7029\"/>\n<text text-anchor=\"middle\" x=\"546.7785\" y=\"-47.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q6&#45;&gt;q0 -->\n<g id=\"edge7\" class=\"edge\">\n<title>q6&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M574.2237,-18.8204C555.2598,-14.166 525.7,-8.1482 499.6303,-8.1482 122.4446,-8.1482 122.4446,-8.1482 122.4446,-8.1482 100.7079,-8.1482 76.6146,-12.0069 57.7214,-15.9344\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"56.8311,-12.5462 47.8082,-18.0993 58.3247,-19.385 56.8311,-12.5462\"/>\n<text text-anchor=\"middle\" x=\"311.0375\" y=\"-11.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fc89819e7c0>"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa2.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "351db01f",
   "metadata": {},
   "source": [
    "Definire un ASFD che riconosce il linguaggio $L\\subseteq\\{0,1\\}^*$ definito\n",
    "come $$L = \\{0,1\\}^*- \\{\\varepsilon\\}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "40bbc394",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa3 = DFA(\n",
    "    states={'q0', 'q1'},\n",
    "    input_symbols={'0', '1'},\n",
    "    delta={\n",
    "        'q0': {'0': 'q1', '1': 'q1'},\n",
    "        'q1': {'0': 'q1', '1': 'q1'}\n",
    "    },\n",
    "    initial_state='q0',\n",
    "    final_states={'q1'}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "fd210309-134a-4bb2-b425-298a0ed1ea8a",
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"151pt\" height=\"89pt\"\n viewBox=\"0.00 0.00 150.59 89.30\" 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 85.2964)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-85.2964 146.5928,-85.2964 146.5928,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"20.1482\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q1 -->\n<g id=\"node2\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"118.4446\" cy=\"-24.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"118.4446\" cy=\"-24.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"118.4446\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n</g>\n<!-- q0&#45;&gt;q1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M40.5153,-24.1482C53.0949,-24.1482 69.5586,-24.1482 84.1109,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"84.2865,-27.6483 94.2865,-24.1482 84.2865,-20.6483 84.2865,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"67.2964\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q1&#45;&gt;q1 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q1&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M109.255,-46.6969C108.2525,-57.1571 111.3157,-66.2964 118.4446,-66.2964 123.123,-66.2964 126.0504,-62.3604 127.2268,-56.6982\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"130.7242,-56.8311 127.6342,-46.6969 123.73,-56.5461 130.7242,-56.8311\"/>\n<text text-anchor=\"middle\" x=\"118.4446\" y=\"-70.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fc897abc7c0>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa3.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "30131785-c47a-4513-8099-87d0ebdc75ca",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q0\t _\n",
      "Completed computation: string rejected\n"
     ]
    }
   ],
   "source": [
    "dfa3.report_computation(Tools.tokens(''))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "764c92f0",
   "metadata": {},
   "source": [
    "Definire un ASFD che riconosce il linguaggio $L\\subseteq\\{0,1\\}^*$ definito\n",
    "come $$L = \\{w| w \\text{ inizia con } 1 \\text{ e termina con } 0 \\}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "b15483e1",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa4 = DFA(\n",
    "    states={'q0', 'q1', 'q2'},\n",
    "    input_symbols={'0', '1'},\n",
    "    delta={\n",
    "        'q0': {'1': 'q1'},\n",
    "        'q1': {'0': 'q2', '1': 'q1'},\n",
    "        'q2': {'0': 'q2', '1': 'q1'}\n",
    "    },\n",
    "    initial_state='q0',\n",
    "    final_states={'q2'}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "db705471",
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"225pt\" height=\"89pt\"\n viewBox=\"0.00 0.00 224.89 89.30\" 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 85.2964)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-85.2964 220.8893,-85.2964 220.8893,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"20.1482\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q1 -->\n<g id=\"node3\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"104.4446\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"104.4446\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n</g>\n<!-- q0&#45;&gt;q1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M40.554,-24.1482C50.5977,-24.1482 62.9096,-24.1482 74.0357,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"74.2268,-27.6483 84.2267,-24.1482 74.2267,-20.6483 74.2268,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"62.2964\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q2 -->\n<g id=\"node2\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"192.7411\" cy=\"-24.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"192.7411\" cy=\"-24.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"192.7411\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q2&#45;&gt;q2 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q2&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M184.2508,-47.126C183.4422,-57.4058 186.2723,-66.2964 192.7411,-66.2964 196.8851,-66.2964 199.5358,-62.6477 200.6933,-57.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"204.1994,-57.2966 201.2313,-47.126 197.2091,-56.9276 204.1994,-57.2966\"/>\n<text text-anchor=\"middle\" x=\"192.7411\" y=\"-70.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2&#45;&gt;q1 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q2&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M172.625,-10.6097C163.6107,-6.0986 152.7432,-2.7604 142.5928,-5.1482 138.6541,-6.0748 134.6572,-7.4726 130.8069,-9.0979\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"129.1701,-6.0009 121.6541,-13.4683 132.1863,-12.3178 129.1701,-6.0009\"/>\n<text text-anchor=\"middle\" x=\"146.5928\" y=\"-8.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q1&#45;&gt;q2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q1&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M124.9235,-24.1482C134.8307,-24.1482 146.9956,-24.1482 158.2739,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"158.2922,-27.6483 168.2921,-24.1482 158.2921,-20.6483 158.2922,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"146.5928\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q1&#45;&gt;q1 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q1&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M96.8946,-42.991C95.6115,-53.0931 98.1282,-62.2964 104.4446,-62.2964 108.4911,-62.2964 110.9781,-58.5194 111.9058,-53.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"115.4069,-53.0213 111.9947,-42.991 108.4072,-52.96 115.4069,-53.0213\"/>\n<text text-anchor=\"middle\" x=\"104.4446\" y=\"-66.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fc89819e6d0>"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa4.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "397d2186",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q0\t 10\n",
      "q1\t 0\n",
      "q2\t _\n",
      "Completed computation: string accepted\n"
     ]
    }
   ],
   "source": [
    "dfa4.report_computation(Tools.tokens('10'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "2172dd18",
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"225pt\" height=\"176pt\"\n viewBox=\"0.00 0.00 224.89 176.30\" 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 172.2964)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-172.2964 220.8893,-172.2964 220.8893,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"20.1482\" cy=\"-65.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-61.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q1 -->\n<g id=\"node3\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"104.4446\" cy=\"-111.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"104.4446\" y=\"-107.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n</g>\n<!-- q0&#45;&gt;q1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M38.0253,-74.9036C49.5367,-81.1853 64.7121,-89.4664 77.6512,-96.5272\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"76.1387,-99.689 86.5933,-101.4069 79.4918,-93.5443 76.1387,-99.689\"/>\n<text text-anchor=\"middle\" x=\"62.2964\" y=\"-92.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q* -->\n<g id=\"node4\" class=\"node\">\n<title>q*</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"104.4446\" cy=\"-20.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"104.4446\" y=\"-16.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q*</text>\n</g>\n<!-- q0&#45;&gt;q* -->\n<g id=\"edge2\" class=\"edge\">\n<title>q0&#45;&gt;q*</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M38.0253,-55.6049C49.5367,-49.4598 64.7121,-41.3586 77.6512,-34.4513\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"79.4199,-37.4747 86.5933,-29.6778 76.1233,-31.2995 79.4199,-37.4747\"/>\n<text text-anchor=\"middle\" x=\"62.2964\" y=\"-47.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2 -->\n<g id=\"node2\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"192.7411\" cy=\"-111.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"192.7411\" cy=\"-111.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"192.7411\" y=\"-107.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q2&#45;&gt;q2 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q2&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M184.2508,-134.126C183.4422,-144.4058 186.2723,-153.2964 192.7411,-153.2964 196.8851,-153.2964 199.5358,-149.6477 200.6933,-144.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"204.1994,-144.2966 201.2313,-134.126 197.2091,-143.9276 204.1994,-144.2966\"/>\n<text text-anchor=\"middle\" x=\"192.7411\" y=\"-157.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2&#45;&gt;q1 -->\n<g id=\"edge6\" class=\"edge\">\n<title>q2&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M172.625,-97.6097C163.6107,-93.0986 152.7432,-89.7604 142.5928,-92.1482 138.6541,-93.0748 134.6572,-94.4726 130.8069,-96.0979\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"129.1701,-93.0009 121.6541,-100.4683 132.1863,-99.3178 129.1701,-93.0009\"/>\n<text text-anchor=\"middle\" x=\"146.5928\" y=\"-95.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q1&#45;&gt;q2 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q1&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M124.9235,-111.1482C134.8307,-111.1482 146.9956,-111.1482 158.2739,-111.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"158.2922,-114.6483 168.2921,-111.1482 158.2921,-107.6483 158.2922,-114.6483\"/>\n<text text-anchor=\"middle\" x=\"146.5928\" y=\"-114.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</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=\"M96.8946,-129.991C95.6115,-140.0931 98.1282,-149.2964 104.4446,-149.2964 108.4911,-149.2964 110.9781,-145.5194 111.9058,-140.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"115.4069,-140.0213 111.9947,-129.991 108.4072,-139.96 115.4069,-140.0213\"/>\n<text text-anchor=\"middle\" x=\"104.4446\" y=\"-153.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q*&#45;&gt;q* -->\n<g id=\"edge7\" class=\"edge\">\n<title>q*&#45;&gt;q*</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M96.8946,-38.991C95.6115,-49.0931 98.1282,-58.2964 104.4446,-58.2964 108.4911,-58.2964 110.9781,-54.5194 111.9058,-49.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"115.4069,-49.0213 111.9947,-38.991 108.4072,-48.96 115.4069,-49.0213\"/>\n<text text-anchor=\"middle\" x=\"104.4446\" y=\"-62.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fc89819eb50>"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa4.total.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "1ebf4f1d",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa4_c = dfa4.complement"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "456c03cc",
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"233pt\" height=\"188pt\"\n viewBox=\"0.00 0.00 232.89 188.30\" 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 184.2964)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-184.2964 228.8893,-184.2964 228.8893,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"24.1482\" cy=\"-73.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"24.1482\" cy=\"-73.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"24.1482\" y=\"-69.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q* -->\n<g id=\"node2\" class=\"node\">\n<title>q*</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"116.4446\" cy=\"-123.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"116.4446\" cy=\"-123.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"116.4446\" y=\"-119.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q*</text>\n</g>\n<!-- q0&#45;&gt;q* -->\n<g id=\"edge2\" class=\"edge\">\n<title>q0&#45;&gt;q*</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M45.5549,-84.7449C57.6698,-91.308 73.0146,-99.6208 86.3271,-106.8326\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"84.6942,-109.9285 95.1541,-111.6144 88.0286,-103.7736 84.6942,-109.9285\"/>\n<text text-anchor=\"middle\" x=\"70.2964\" y=\"-102.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q1 -->\n<g id=\"node3\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"116.4446\" cy=\"-24.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"116.4446\" cy=\"-24.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"116.4446\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n</g>\n<!-- q0&#45;&gt;q1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M45.5549,-61.7835C57.4676,-55.459 72.5033,-47.4766 85.6589,-40.4923\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"87.6431,-43.4016 94.8344,-35.6211 84.3607,-37.2189 87.6431,-43.4016\"/>\n<text text-anchor=\"middle\" x=\"70.2964\" y=\"-52.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q*&#45;&gt;q* -->\n<g id=\"edge7\" class=\"edge\">\n<title>q*&#45;&gt;q*</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M107.9544,-146.126C107.1458,-156.4058 109.9759,-165.2964 116.4446,-165.2964 120.5887,-165.2964 123.2394,-161.6477 124.3968,-156.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"127.903,-156.2966 124.9349,-146.126 120.9127,-155.9276 127.903,-156.2966\"/>\n<text text-anchor=\"middle\" x=\"116.4446\" y=\"-169.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</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=\"M107.9544,-47.126C107.1458,-57.4058 109.9759,-66.2964 116.4446,-66.2964 120.5887,-66.2964 123.2394,-62.6477 124.3968,-57.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"127.903,-57.2966 124.9349,-47.126 120.9127,-56.9276 127.903,-57.2966\"/>\n<text text-anchor=\"middle\" x=\"116.4446\" y=\"-70.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q2 -->\n<g id=\"node4\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"204.7411\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"204.7411\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q1&#45;&gt;q2 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q1&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M141.0401,-24.1482C151.2967,-24.1482 163.3177,-24.1482 174.137,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"174.446,-27.6483 184.446,-24.1482 174.446,-20.6483 174.446,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"162.5928\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2&#45;&gt;q1 -->\n<g id=\"edge6\" class=\"edge\">\n<title>q2&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M187.5316,-13.4683C181.1916,-10.1123 173.7952,-6.8425 166.5928,-5.1482 159.7731,-3.5439 152.6296,-4.5244 145.9419,-6.7088\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"144.4504,-3.5384 136.5607,-10.6097 147.1381,-10.0018 144.4504,-3.5384\"/>\n<text text-anchor=\"middle\" x=\"162.5928\" y=\"-8.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q2&#45;&gt;q2 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q2&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M197.191,-42.991C195.908,-53.0931 198.4247,-62.2964 204.7411,-62.2964 208.7875,-62.2964 211.2746,-58.5194 212.2022,-53.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"215.7033,-53.0213 212.2911,-42.991 208.7036,-52.96 215.7033,-53.0213\"/>\n<text text-anchor=\"middle\" x=\"204.7411\" y=\"-66.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fc89819e640>"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa4_c.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "c5577ec9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q0\t 10\n",
      "q1\t 0\n",
      "q2\t _\n",
      "Completed computation: string rejected\n"
     ]
    }
   ],
   "source": [
    "dfa4_c.report_computation(Tools.tokens('10'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9484920",
   "metadata": {},
   "source": [
    "Definire un ASFD che riconosce il linguaggio $L\\subseteq\\{0,1\\}^*$ definito\n",
    "come $$L = \\{w| w \\text{ contiene un numero pari di } 0, \\text{ o contiene\n",
    "esattamente due } 1 \\}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "c5040eaa",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa5 = DFA(\n",
    "    states={'q0p', 'q1p', 'q2p', 'q0d', 'q1d', 'q2d'},\n",
    "    input_symbols={'0', '1'},\n",
    "    delta={\n",
    "        'q0p': {'0': 'q0d', '1': 'q1p'},\n",
    "        'q0d': {'0': 'q0p', '1': 'q1d'},\n",
    "        'q1p': {'0': 'q1d', '1': 'q2p'},\n",
    "        'q1d': {'0': 'q1p', '1': 'q2d'},\n",
    "        'q2p': {'0': 'q2d'},\n",
    "        'q2d': {'0': 'q2p'}\n",
    "    },\n",
    "    initial_state='q0p',\n",
    "    final_states={'q0p', 'q1p', 'q2p', 'q2d'}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "263a846b",
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"370pt\" height=\"175pt\"\n viewBox=\"0.00 0.00 369.58 175.40\" 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 171.3956)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-171.3956 365.5825,-171.3956 365.5825,4 -4,4\"/>\n<!-- q0p -->\n<g id=\"node1\" class=\"node\">\n<title>q0p</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"28.6978\" cy=\"-62.6978\" rx=\"24.8692\" ry=\"24.8692\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"28.6978\" cy=\"-62.6978\" rx=\"28.897\" ry=\"28.897\"/>\n<text text-anchor=\"middle\" x=\"28.6978\" y=\"-58.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0p</text>\n</g>\n<!-- q1p -->\n<g id=\"node2\" class=\"node\">\n<title>q1p</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"130.0934\" cy=\"-100.6978\" rx=\"24.8692\" ry=\"24.8692\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"130.0934\" cy=\"-100.6978\" rx=\"28.897\" ry=\"28.897\"/>\n<text text-anchor=\"middle\" x=\"130.0934\" y=\"-96.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1p</text>\n</g>\n<!-- q0p&#45;&gt;q1p -->\n<g id=\"edge2\" class=\"edge\">\n<title>q0p&#45;&gt;q1p</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M55.6038,-72.7813C67.1773,-77.1188 80.8902,-82.2579 93.3759,-86.9372\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"92.4694,-90.3351 103.0617,-90.5672 94.926,-83.7803 92.4694,-90.3351\"/>\n<text text-anchor=\"middle\" x=\"79.3956\" y=\"-86.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q0d -->\n<g id=\"node5\" class=\"node\">\n<title>q0d</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"130.0934\" cy=\"-24.6978\" rx=\"24.8972\" ry=\"24.8972\"/>\n<text text-anchor=\"middle\" x=\"130.0934\" y=\"-20.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0d</text>\n</g>\n<!-- q0p&#45;&gt;q0d -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0p&#45;&gt;q0d</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M55.6038,-52.6143C68.4451,-47.8017 83.9202,-42.0021 97.4305,-36.9389\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"98.7194,-40.1936 106.8551,-33.4068 96.2628,-33.6388 98.7194,-40.1936\"/>\n<text text-anchor=\"middle\" x=\"79.3956\" y=\"-49.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2p -->\n<g id=\"node4\" class=\"node\">\n<title>q2p</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"231.489\" cy=\"-138.6978\" rx=\"24.8692\" ry=\"24.8692\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"231.489\" cy=\"-138.6978\" rx=\"28.897\" ry=\"28.897\"/>\n<text text-anchor=\"middle\" x=\"231.489\" y=\"-134.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2p</text>\n</g>\n<!-- q1p&#45;&gt;q2p -->\n<g id=\"edge6\" class=\"edge\">\n<title>q1p&#45;&gt;q2p</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M156.9994,-110.7813C168.5729,-115.1188 182.2858,-120.2579 194.7715,-124.9372\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"193.8651,-128.3351 204.4574,-128.5672 196.3216,-121.7803 193.8651,-128.3351\"/>\n<text text-anchor=\"middle\" x=\"180.7912\" y=\"-124.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q1d -->\n<g id=\"node6\" class=\"node\">\n<title>q1d</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"231.489\" cy=\"-62.6978\" rx=\"24.8972\" ry=\"24.8972\"/>\n<text text-anchor=\"middle\" x=\"231.489\" y=\"-58.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1d</text>\n</g>\n<!-- q1p&#45;&gt;q1d -->\n<g id=\"edge5\" class=\"edge\">\n<title>q1p&#45;&gt;q1d</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M156.9994,-90.6143C169.8407,-85.8017 185.3158,-80.0021 198.8261,-74.9389\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"200.115,-78.1936 208.2507,-71.4068 197.6584,-71.6388 200.115,-78.1936\"/>\n<text text-anchor=\"middle\" x=\"180.7912\" y=\"-86.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2d -->\n<g id=\"node3\" class=\"node\">\n<title>q2d</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"332.8847\" cy=\"-100.6978\" rx=\"24.8692\" ry=\"24.8692\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"332.8847\" cy=\"-100.6978\" rx=\"28.897\" ry=\"28.897\"/>\n<text text-anchor=\"middle\" x=\"332.8847\" y=\"-96.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2d</text>\n</g>\n<!-- q2d&#45;&gt;q2p -->\n<g id=\"edge10\" class=\"edge\">\n<title>q2d&#45;&gt;q2p</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M304.3977,-95.5544C295.757,-95.0717 286.3866,-95.6661 278.1869,-98.6978 271.1656,-101.2938 264.487,-105.469 258.4902,-110.1634\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"256.0791,-107.6203 250.767,-116.7872 260.6363,-112.9338 256.0791,-107.6203\"/>\n<text text-anchor=\"middle\" x=\"282.1869\" y=\"-102.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2p&#45;&gt;q2d -->\n<g id=\"edge9\" class=\"edge\">\n<title>q2p&#45;&gt;q2d</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M258.395,-128.6143C269.9685,-124.2769 283.6814,-119.1377 296.1671,-114.4584\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"297.7173,-117.6153 305.853,-110.8285 295.2607,-111.0605 297.7173,-117.6153\"/>\n<text text-anchor=\"middle\" x=\"282.1869\" y=\"-124.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q0d&#45;&gt;q0p -->\n<g id=\"edge3\" class=\"edge\">\n<title>q0d&#45;&gt;q0p</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M105.5111,-20.535C95.8646,-19.847 84.86,-20.2655 75.3956,-23.6978 68.4323,-26.2231 61.7798,-30.2913 55.7904,-34.8676\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"53.4933,-32.226 48.0671,-41.3259 57.9837,-37.596 53.4933,-32.226\"/>\n<text text-anchor=\"middle\" x=\"79.3956\" y=\"-27.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q0d&#45;&gt;q1d -->\n<g id=\"edge4\" class=\"edge\">\n<title>q0d&#45;&gt;q1d</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M154.6626,-21.8268C164.3073,-21.5456 175.314,-22.3009 184.7912,-25.6978 192.4592,-28.4462 199.8285,-33.0049 206.3572,-38.0002\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"204.2066,-40.7637 214.1367,-44.4575 208.6775,-35.3774 204.2066,-40.7637\"/>\n<text text-anchor=\"middle\" x=\"180.7912\" y=\"-29.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q1d&#45;&gt;q1p -->\n<g id=\"edge7\" class=\"edge\">\n<title>q1d&#45;&gt;q1p</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M207.1621,-57.8705C197.4481,-56.9426 186.3279,-57.1717 176.7912,-60.6978 169.77,-63.2938 163.0914,-67.469 157.0945,-72.1634\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"154.6835,-69.6203 149.3714,-78.7872 159.2406,-74.9338 154.6835,-69.6203\"/>\n<text text-anchor=\"middle\" x=\"180.7912\" y=\"-64.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q1d&#45;&gt;q2d -->\n<g id=\"edge8\" class=\"edge\">\n<title>q1d&#45;&gt;q2d</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M256.0582,-59.8268C265.7029,-59.5456 276.7096,-60.3009 286.1869,-63.6978 292.7289,-66.0427 299.0536,-69.7053 304.8244,-73.8325\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"302.8126,-76.7025 312.8438,-80.1123 307.1284,-71.1912 302.8126,-76.7025\"/>\n<text text-anchor=\"middle\" x=\"282.1869\" y=\"-67.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fc89819e5e0>"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa5.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "17c5392c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q0p\t 101000\n",
      "q1p\t 01000\n",
      "q1d\t 1000\n",
      "q2d\t 000\n",
      "q2p\t 00\n",
      "q2d\t 0\n",
      "q2p\t _\n",
      "Completed computation: string accepted\n"
     ]
    }
   ],
   "source": [
    "dfa5.report_computation(Tools.tokens('101000'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de9ae80c",
   "metadata": {},
   "source": [
    "Definire un ASFD che riconosce il linguaggio $L\\subseteq\\{0,1\\}^*$ definito come $$L = \\{w| w \\text{ contiene esattamente due } 0  \\}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "93552a91",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa6 = DFA(\n",
    "    states={'q0', 'q1', 'q2'},\n",
    "    input_symbols={'0', '1'},\n",
    "    delta={\n",
    "        'q0': {'0': 'q1', '1': 'q0'},\n",
    "        'q1': {'0': 'q2', '1': 'q1'},\n",
    "        'q2': {'1': 'q2'}\n",
    "    },\n",
    "    initial_state='q0',\n",
    "    final_states={'q2'}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "5ff93871",
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"225pt\" height=\"89pt\"\n viewBox=\"0.00 0.00 224.89 89.30\" 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 85.2964)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-85.2964 220.8893,-85.2964 220.8893,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"20.1482\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\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=\"M12.5981,-42.991C11.3151,-53.0931 13.8318,-62.2964 20.1482,-62.2964 24.1947,-62.2964 26.6817,-58.5194 27.6093,-53.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"31.1105,-53.0213 27.6983,-42.991 24.1108,-52.96 31.1105,-53.0213\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-66.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q1 -->\n<g id=\"node3\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"104.4446\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"104.4446\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n</g>\n<!-- q0&#45;&gt;q1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M40.554,-24.1482C50.5977,-24.1482 62.9096,-24.1482 74.0357,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"74.2268,-27.6483 84.2267,-24.1482 74.2267,-20.6483 74.2268,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"62.2964\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2 -->\n<g id=\"node2\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"192.7411\" cy=\"-24.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"192.7411\" cy=\"-24.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"192.7411\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q2&#45;&gt;q2 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q2&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M184.2508,-47.126C183.4422,-57.4058 186.2723,-66.2964 192.7411,-66.2964 196.8851,-66.2964 199.5358,-62.6477 200.6933,-57.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"204.1994,-57.2966 201.2313,-47.126 197.2091,-56.9276 204.1994,-57.2966\"/>\n<text text-anchor=\"middle\" x=\"192.7411\" y=\"-70.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q1&#45;&gt;q2 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q1&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M124.9235,-24.1482C134.8307,-24.1482 146.9956,-24.1482 158.2739,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"158.2922,-27.6483 168.2921,-24.1482 158.2921,-20.6483 158.2922,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"146.5928\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</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=\"M96.8946,-42.991C95.6115,-53.0931 98.1282,-62.2964 104.4446,-62.2964 108.4911,-62.2964 110.9781,-58.5194 111.9058,-53.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"115.4069,-53.0213 111.9947,-42.991 108.4072,-52.96 115.4069,-53.0213\"/>\n<text text-anchor=\"middle\" x=\"104.4446\" y=\"-66.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fc89819ee80>"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa6.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "169ab452",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q0\t 101110\n",
      "q0\t 01110\n",
      "q1\t 1110\n",
      "q1\t 110\n",
      "q1\t 10\n",
      "q1\t 0\n",
      "q2\t _\n",
      "Completed computation: string accepted\n"
     ]
    }
   ],
   "source": [
    "dfa6.report_computation(Tools.tokens('101110'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e55429c",
   "metadata": {},
   "source": [
    "Definire un ASFD che riconosce il linguaggio $L\\subseteq\\{0,1\\}^*$ definito come\n",
    "$$L = \\{w| w \\text{ contiene esattamente due } 0 \\text{ e almeno due }\n",
    "1\\}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "6ccec586",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa7 = DFA(\n",
    "    states={'q00', 'q01', 'q02', 'q10', 'q11', 'q12', 'q20', 'q21', 'q22'},\n",
    "    input_symbols={'0', '1'},\n",
    "    delta={\n",
    "        'q00': {'0': 'q10', '1': 'q01'},\n",
    "        'q01': {'0': 'q11', '1': 'q02'},\n",
    "        'q02': {'0': 'q12', '1': 'q02'},\n",
    "        'q10': {'0': 'q20', '1': 'q11'},\n",
    "        'q11': {'0': 'q21', '1': 'q12'},\n",
    "        'q12': {'0': 'q22', '1': 'q12'},\n",
    "        'q20': {'1': 'q21'},\n",
    "        'q21': {'1': 'q22'},\n",
    "        'q22': {'1': 'q22'}\n",
    "    },\n",
    "    initial_state='q00',\n",
    "    final_states={'q22'}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "281055f8",
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"439pt\" height=\"224pt\"\n viewBox=\"0.00 0.00 438.98 224.40\" 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 220.3956)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-220.3956 434.9781,-220.3956 434.9781,4 -4,4\"/>\n<!-- q00 -->\n<g id=\"node1\" class=\"node\">\n<title>q00</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"24.6978\" cy=\"-115.6978\" rx=\"24.8972\" ry=\"24.8972\"/>\n<text text-anchor=\"middle\" x=\"24.6978\" y=\"-111.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q00</text>\n</g>\n<!-- q10 -->\n<g id=\"node3\" class=\"node\">\n<title>q10</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"118.0934\" cy=\"-149.6978\" rx=\"24.8972\" ry=\"24.8972\"/>\n<text text-anchor=\"middle\" x=\"118.0934\" y=\"-145.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q10</text>\n</g>\n<!-- q00&#45;&gt;q10 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q00&#45;&gt;q10</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M48.2655,-124.2774C59.5223,-128.3754 73.1783,-133.3468 85.4177,-137.8024\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"84.2628,-141.1067 94.8568,-141.2387 86.6574,-134.529 84.2628,-141.1067\"/>\n<text text-anchor=\"middle\" x=\"71.3956\" y=\"-137.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q01 -->\n<g id=\"node4\" class=\"node\">\n<title>q01</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"118.0934\" cy=\"-82.6978\" rx=\"24.8972\" ry=\"24.8972\"/>\n<text text-anchor=\"middle\" x=\"118.0934\" y=\"-78.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q01</text>\n</g>\n<!-- q00&#45;&gt;q01 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q00&#45;&gt;q01</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M48.2655,-107.3705C59.3265,-103.4623 72.7037,-98.7356 84.7774,-94.4695\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"86.2706,-97.6541 94.5333,-91.0224 83.9385,-91.054 86.2706,-97.6541\"/>\n<text text-anchor=\"middle\" x=\"71.3956\" y=\"-103.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q22 -->\n<g id=\"node2\" class=\"node\">\n<title>q22</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"402.2803\" cy=\"-101.6978\" rx=\"24.8692\" ry=\"24.8692\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"402.2803\" cy=\"-101.6978\" rx=\"28.897\" ry=\"28.897\"/>\n<text text-anchor=\"middle\" x=\"402.2803\" y=\"-97.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q22</text>\n</g>\n<!-- q22&#45;&gt;q22 -->\n<g id=\"edge15\" class=\"edge\">\n<title>q22&#45;&gt;q22</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M392.9419,-129.0384C392.5269,-139.6094 395.6397,-148.3956 402.2803,-148.3956 406.6382,-148.3956 409.4768,-144.6117 410.7961,-139.0227\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"414.2856,-139.2921 411.6187,-129.0384 407.3093,-138.7172 414.2856,-139.2921\"/>\n<text text-anchor=\"middle\" x=\"402.2803\" y=\"-152.1956\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q11 -->\n<g id=\"node5\" class=\"node\">\n<title>q11</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"211.489\" cy=\"-124.6978\" rx=\"24.8972\" ry=\"24.8972\"/>\n<text text-anchor=\"middle\" x=\"211.489\" y=\"-120.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q11</text>\n</g>\n<!-- q10&#45;&gt;q11 -->\n<g id=\"edge8\" class=\"edge\">\n<title>q10&#45;&gt;q11</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M142.1451,-143.2597C152.9302,-140.3728 165.8417,-136.9166 177.5838,-133.7735\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"178.764,-137.0809 187.5189,-131.1141 176.9539,-130.319 178.764,-137.0809\"/>\n<text text-anchor=\"middle\" x=\"164.7912\" y=\"-141.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q20 -->\n<g id=\"node8\" class=\"node\">\n<title>q20</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"211.489\" cy=\"-191.6978\" rx=\"24.8972\" ry=\"24.8972\"/>\n<text text-anchor=\"middle\" x=\"211.489\" y=\"-187.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q20</text>\n</g>\n<!-- q10&#45;&gt;q20 -->\n<g id=\"edge7\" class=\"edge\">\n<title>q10&#45;&gt;q20</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M140.7019,-159.8648C152.3173,-165.0883 166.6708,-171.5431 179.41,-177.2719\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"178.2093,-180.5695 188.7651,-181.4788 181.0803,-174.1853 178.2093,-180.5695\"/>\n<text text-anchor=\"middle\" x=\"164.7912\" y=\"-175.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q01&#45;&gt;q11 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q01&#45;&gt;q11</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M140.7019,-92.8648C152.3173,-98.0883 166.6708,-104.5431 179.41,-110.2719\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"178.2093,-113.5695 188.7651,-114.4788 181.0803,-107.1853 178.2093,-113.5695\"/>\n<text text-anchor=\"middle\" x=\"164.7912\" y=\"-108.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q02 -->\n<g id=\"node6\" class=\"node\">\n<title>q02</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"211.489\" cy=\"-24.6978\" rx=\"24.8972\" ry=\"24.8972\"/>\n<text text-anchor=\"middle\" x=\"211.489\" y=\"-20.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q02</text>\n</g>\n<!-- q01&#45;&gt;q02 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q01&#45;&gt;q02</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M139.2863,-69.5367C151.8246,-61.7503 167.9015,-51.7663 181.7008,-43.1967\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"183.7313,-46.0558 190.38,-37.8068 180.0383,-40.1092 183.7313,-46.0558\"/>\n<text text-anchor=\"middle\" x=\"164.7912\" y=\"-59.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q12 -->\n<g id=\"node7\" class=\"node\">\n<title>q12</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"304.8847\" cy=\"-51.6978\" rx=\"24.8972\" ry=\"24.8972\"/>\n<text text-anchor=\"middle\" x=\"304.8847\" y=\"-47.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q12</text>\n</g>\n<!-- q11&#45;&gt;q12 -->\n<g id=\"edge10\" class=\"edge\">\n<title>q11&#45;&gt;q12</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M231.2959,-109.2164C244.5451,-98.8605 262.1753,-85.0803 276.8577,-73.6043\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"279.383,-76.0728 285.1064,-67.1569 275.0722,-70.5576 279.383,-76.0728\"/>\n<text text-anchor=\"middle\" x=\"258.1869\" y=\"-93.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q21 -->\n<g id=\"node9\" class=\"node\">\n<title>q21</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"304.8847\" cy=\"-151.6978\" rx=\"24.8972\" ry=\"24.8972\"/>\n<text text-anchor=\"middle\" x=\"304.8847\" y=\"-147.9978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q21</text>\n</g>\n<!-- q11&#45;&gt;q21 -->\n<g id=\"edge9\" class=\"edge\">\n<title>q11&#45;&gt;q21</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M235.5407,-131.651C246.3258,-134.7689 259.2373,-138.5015 270.9794,-141.8961\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"270.3358,-145.3532 280.9145,-144.7682 272.2799,-138.6286 270.3358,-145.3532\"/>\n<text text-anchor=\"middle\" x=\"258.1869\" y=\"-142.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q02&#45;&gt;q02 -->\n<g id=\"edge6\" class=\"edge\">\n<title>q02&#45;&gt;q02</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M202.9988,-47.9752C202.1902,-58.389 205.0203,-67.3956 211.489,-67.3956 215.6331,-67.3956 218.2838,-63.6993 219.4412,-58.3047\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"222.9543,-58.1438 219.9793,-47.9752 215.9637,-57.7796 222.9543,-58.1438\"/>\n<text text-anchor=\"middle\" x=\"211.489\" y=\"-71.1956\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q02&#45;&gt;q12 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q02&#45;&gt;q12</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M235.5407,-31.651C246.3258,-34.7689 259.2373,-38.5015 270.9794,-41.8961\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"270.3358,-45.3532 280.9145,-44.7682 272.2799,-38.6286 270.3358,-45.3532\"/>\n<text text-anchor=\"middle\" x=\"258.1869\" y=\"-43.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q12&#45;&gt;q22 -->\n<g id=\"edge11\" class=\"edge\">\n<title>q12&#45;&gt;q22</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M326.9852,-63.0436C338.9328,-69.1771 353.9613,-76.8923 367.4436,-83.8137\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"365.979,-86.996 376.4736,-88.4495 369.1759,-80.7687 365.979,-86.996\"/>\n<text text-anchor=\"middle\" x=\"351.5825\" y=\"-80.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q12&#45;&gt;q12 -->\n<g id=\"edge12\" class=\"edge\">\n<title>q12&#45;&gt;q12</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M296.3944,-74.9752C295.5858,-85.389 298.4159,-94.3956 304.8847,-94.3956 309.0287,-94.3956 311.6794,-90.6993 312.8369,-85.3047\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"316.3499,-85.1438 313.3749,-74.9752 309.3594,-84.7796 316.3499,-85.1438\"/>\n<text text-anchor=\"middle\" x=\"304.8847\" y=\"-98.1956\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q20&#45;&gt;q21 -->\n<g id=\"edge13\" class=\"edge\">\n<title>q20&#45;&gt;q21</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M234.5756,-181.8102C246.1118,-176.8694 260.2568,-170.8113 272.8272,-165.4275\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"274.2492,-168.6261 282.0637,-161.4717 271.4933,-162.1914 274.2492,-168.6261\"/>\n<text text-anchor=\"middle\" x=\"258.1869\" y=\"-176.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q21&#45;&gt;q22 -->\n<g id=\"edge14\" class=\"edge\">\n<title>q21&#45;&gt;q22</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M326.9852,-140.352C338.9328,-134.2185 353.9613,-126.5033 367.4436,-119.5819\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"369.1759,-122.6269 376.4736,-114.9462 365.979,-116.3996 369.1759,-122.6269\"/>\n<text text-anchor=\"middle\" x=\"351.5825\" y=\"-132.4978\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fc8981afa90>"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa7.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "115abe3c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q00\t 10010\n",
      "q01\t 0010\n",
      "q11\t 010\n",
      "q21\t 10\n",
      "q22\t 0\n",
      "Incomplete computation: string rejected\n"
     ]
    }
   ],
   "source": [
    "dfa7.report_computation(Tools.tokens('10010'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf2855ed",
   "metadata": {},
   "source": [
    "Definire un ASFD che riconosce il linguaggio $L\\subseteq\\{0,1\\}^*$ definito\n",
    "come $$L = \\{w| \\mid w\\mid mod\\; 5=1\\}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "781fb527",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa8 = DFA(\n",
    "    states={'q0', 'q1', 'q2', 'q3', 'q4'},\n",
    "    input_symbols={'0', '1'},\n",
    "    delta={\n",
    "        'q0': {'0': 'q1', '1': 'q1'},\n",
    "        'q1': {'0': 'q2', '1': 'q2'},\n",
    "        'q2': {'0': 'q3', '1': 'q3'},\n",
    "        'q3': {'0': 'q4', '1': 'q4'},\n",
    "        'q4': {'0': 'q0', '1': 'q0'},\n",
    "    },\n",
    "    initial_state='q0',\n",
    "    final_states={'q1'}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "ceee36a9",
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"433pt\" height=\"88pt\"\n viewBox=\"0.00 0.00 433.48 88.30\" 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 84.2964)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-84.2964 429.4821,-84.2964 429.4821,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"20.1482\" cy=\"-20.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-16.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q1 -->\n<g id=\"node2\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"118.4446\" cy=\"-56.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"118.4446\" cy=\"-56.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"118.4446\" y=\"-52.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n</g>\n<!-- q0&#45;&gt;q1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M39.1008,-27.0894C52.3724,-31.95 70.44,-38.567 85.9819,-44.2591\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"85.1608,-47.6857 95.7546,-47.8382 87.5682,-41.1126 85.1608,-47.6857\"/>\n<text text-anchor=\"middle\" x=\"67.2964\" y=\"-43.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q2 -->\n<g id=\"node3\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"216.7411\" cy=\"-57.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"216.7411\" y=\"-53.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q1&#45;&gt;q2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q1&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M142.7426,-56.3954C155.8809,-56.5291 172.2341,-56.6954 186.2237,-56.8377\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"186.3333,-60.3389 196.3684,-56.941 186.4045,-53.3393 186.3333,-60.3389\"/>\n<text text-anchor=\"middle\" x=\"169.5928\" y=\"-59.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q3 -->\n<g id=\"node4\" class=\"node\">\n<title>q3</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"311.0375\" cy=\"-54.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"311.0375\" y=\"-50.4482\" 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=\"M237.202,-56.4973C249.8059,-56.0963 266.2037,-55.5746 280.3438,-55.1247\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"280.7329,-58.6142 290.6165,-54.7979 280.5102,-51.6177 280.7329,-58.6142\"/>\n<text text-anchor=\"middle\" x=\"263.8893\" y=\"-58.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q4 -->\n<g id=\"node5\" class=\"node\">\n<title>q4</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"405.3339\" cy=\"-20.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"405.3339\" y=\"-16.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q4</text>\n</g>\n<!-- q3&#45;&gt;q4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q3&#45;&gt;q4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M330.1198,-47.2678C343.5401,-42.4289 361.7303,-35.8702 376.8603,-30.4148\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"378.06,-33.7029 386.28,-27.0184 375.6856,-27.1178 378.06,-33.7029\"/>\n<text text-anchor=\"middle\" x=\"358.1857\" y=\"-43.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q4&#45;&gt;q0 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q4&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M385.6308,-14.8204C366.667,-10.166 337.1072,-4.1482 311.0375,-4.1482 118.4446,-4.1482 118.4446,-4.1482 118.4446,-4.1482 95.1417,-4.1482 69.1303,-8.583 49.7212,-12.783\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"48.9292,-9.3737 39.9502,-14.9976 50.4766,-16.2005 48.9292,-9.3737\"/>\n<text text-anchor=\"middle\" x=\"216.7411\" y=\"-7.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fc8981bd1f0>"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa8.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "831f4a95",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q0\t 100010\n",
      "q1\t 00010\n",
      "q2\t 0010\n",
      "q3\t 010\n",
      "q4\t 10\n",
      "q0\t 0\n",
      "q1\t _\n",
      "Completed computation: string accepted\n"
     ]
    }
   ],
   "source": [
    "dfa8.report_computation(Tools.tokens('100010'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "449140a3",
   "metadata": {},
   "source": [
    "Definire un ASFD che riconosce il linguaggio $L\\subseteq\\{0,1\\}^*$ definito\n",
    "come $$L = \\{w| \\mid w\\mid mod\\geq 4\\}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "a95686a5",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa9 = DFA(\n",
    "    states={'q0', 'q1', 'q2', 'q3', 'q4'},\n",
    "    input_symbols={'0', '1'},\n",
    "    delta={\n",
    "        'q0': {'0': 'q1', '1': 'q1'},\n",
    "        'q1': {'0': 'q2', '1': 'q2'},\n",
    "        'q2': {'0': 'q3', '1': 'q3'},\n",
    "        'q3': {'0': 'q4', '1': 'q4'},\n",
    "        'q4': {'0': 'q4', '1': 'q4'}\n",
    "    },\n",
    "    initial_state='q0',\n",
    "    final_states={'q4'}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "da09d6ff",
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"433pt\" height=\"89pt\"\n viewBox=\"0.00 0.00 433.48 89.30\" 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 85.2964)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-85.2964 429.4821,-85.2964 429.4821,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"20.1482\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q1 -->\n<g id=\"node3\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"114.4446\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"114.4446\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n</g>\n<!-- q0&#45;&gt;q1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M40.6091,-24.1482C53.213,-24.1482 69.6109,-24.1482 83.751,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"84.0237,-27.6483 94.0236,-24.1482 84.0236,-20.6483 84.0237,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"67.2964\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q4 -->\n<g id=\"node2\" class=\"node\">\n<title>q4</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"401.3339\" cy=\"-24.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"401.3339\" cy=\"-24.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"401.3339\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q4</text>\n</g>\n<!-- q4&#45;&gt;q4 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q4&#45;&gt;q4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M392.1443,-46.6969C391.1418,-57.1571 394.205,-66.2964 401.3339,-66.2964 406.0123,-66.2964 408.9396,-62.3604 410.1161,-56.6982\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"413.6135,-56.8311 410.5235,-46.6969 406.6193,-56.5461 413.6135,-56.8311\"/>\n<text text-anchor=\"middle\" x=\"401.3339\" y=\"-70.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q2 -->\n<g id=\"node4\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"208.7411\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"208.7411\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q1&#45;&gt;q2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q1&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M134.9056,-24.1482C147.5095,-24.1482 163.9073,-24.1482 178.0474,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"178.3201,-27.6483 188.3201,-24.1482 178.32,-20.6483 178.3201,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"161.5928\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q3 -->\n<g id=\"node5\" class=\"node\">\n<title>q3</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"303.0375\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"303.0375\" y=\"-20.4482\" 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=\"M229.202,-24.1482C241.8059,-24.1482 258.2037,-24.1482 272.3438,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"272.6165,-27.6483 282.6165,-24.1482 272.6165,-20.6483 272.6165,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"255.8893\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q3&#45;&gt;q4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q3&#45;&gt;q4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M323.4046,-24.1482C335.9842,-24.1482 352.4479,-24.1482 367.0002,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"367.1758,-27.6483 377.1758,-24.1482 367.1758,-20.6483 367.1758,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"350.1857\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fc8981af3a0>"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa9.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "67bb1bd8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q0\t 01001\n",
      "q1\t 1001\n",
      "q2\t 001\n",
      "q3\t 01\n",
      "q4\t 1\n",
      "q4\t _\n",
      "Completed computation: string accepted\n"
     ]
    }
   ],
   "source": [
    "dfa9.report_computation(Tools.tokens('01001'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a60cf9d5",
   "metadata": {},
   "source": [
    "Definire un ASFND avente 3 stati e che riconosce il linguaggio $L\\subseteq\\{0,1\\}^*$ definito come $$L = 0^*1^*0^+$$\n",
    "\n",
    "$L$ è quindi l'insieme delle stringhe composte da una sequenza (eventualmente\n",
    "nulla) di 0 seguita da una sequenza (eventualmente nulla) di 1 seguita da una\n",
    "sequenza di almeno uno 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "ef0d8b6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "nfa0 = NFA(\n",
    "    states={'q0', 'q1', 'q2', 'q3'},\n",
    "    input_symbols={'0', '1'},\n",
    "    delta={\n",
    "        'q0': {'0': {'q0'}, '': {'q1'}},\n",
    "        'q1': {'1': {'q1'}, '': {'q2'}},\n",
    "        'q2': {'0': {'q3'}},\n",
    "        'q3': {'0': {'q3'}}\n",
    "    },\n",
    "    initial_state='q0',\n",
    "    final_states={'q3'}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "8651f9ac",
   "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: nondeterministic_finite_state_machine Pages: 1 -->\n<svg width=\"309pt\" height=\"89pt\"\n viewBox=\"0.00 0.00 309.19 89.30\" 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 85.2964)\">\n<title>nondeterministic_finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-85.2964 305.1857,-85.2964 305.1857,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"20.1482\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q0&#45;&gt;q0 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M12.5981,-42.991C11.3151,-53.0931 13.8318,-62.2964 20.1482,-62.2964 24.1947,-62.2964 26.6817,-58.5194 27.6093,-53.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"31.1105,-53.0213 27.6983,-42.991 24.1108,-52.96 31.1105,-53.0213\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-66.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q1 -->\n<g id=\"node3\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"104.4446\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"104.4446\" y=\"-20.4482\" 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=\"M40.554,-24.1482C50.5977,-24.1482 62.9096,-24.1482 74.0357,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"74.2268,-27.6483 84.2267,-24.1482 74.2267,-20.6483 74.2268,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"62.2964\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">_</text>\n</g>\n<!-- q3 -->\n<g id=\"node2\" class=\"node\">\n<title>q3</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"277.0375\" cy=\"-24.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"277.0375\" cy=\"-24.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"277.0375\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q3</text>\n</g>\n<!-- q3&#45;&gt;q3 -->\n<g id=\"edge6\" class=\"edge\">\n<title>q3&#45;&gt;q3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M268.5473,-47.126C267.7387,-57.4058 270.5687,-66.2964 277.0375,-66.2964 281.1815,-66.2964 283.8323,-62.6477 284.9897,-57.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"288.4958,-57.2966 285.5277,-47.126 281.5055,-56.9276 288.4958,-57.2966\"/>\n<text text-anchor=\"middle\" x=\"277.0375\" y=\"-70.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q1&#45;&gt;q1 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q1&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M96.8946,-42.991C95.6115,-53.0931 98.1282,-62.2964 104.4446,-62.2964 108.4911,-62.2964 110.9781,-58.5194 111.9058,-53.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"115.4069,-53.0213 111.9947,-42.991 108.4072,-52.96 115.4069,-53.0213\"/>\n<text text-anchor=\"middle\" x=\"104.4446\" y=\"-66.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q2 -->\n<g id=\"node4\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"188.7411\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"188.7411\" y=\"-20.4482\" 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=\"M124.8504,-24.1482C134.8941,-24.1482 147.2061,-24.1482 158.3321,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"158.5232,-27.6483 168.5232,-24.1482 158.5231,-20.6483 158.5232,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"146.5928\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">_</text>\n</g>\n<!-- q2&#45;&gt;q3 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q2&#45;&gt;q3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M209.22,-24.1482C219.1271,-24.1482 231.292,-24.1482 242.5704,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"242.5886,-27.6483 252.5886,-24.1482 242.5885,-20.6483 242.5886,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"230.8893\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7f8c441fa910>"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nfa0.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "32c9fb47",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "00100\t{q0}\n",
      "0100\t{q2, q3, q0, q1}\n",
      "100\t{q2, q3, q0, q1}\n",
      "00\t{q2, q1}\n",
      "0\t{q3}\n",
      "_\t{q3}\n",
      "Completed computation: string accepted\n"
     ]
    }
   ],
   "source": [
    "nfa0.report_computation(Tools.tokens('00100'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "d495019f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q0\t 00100\n",
      "q1\t 0100\n",
      "q3\t 100\n",
      "Incomplete path: string rejected\n"
     ]
    }
   ],
   "source": [
    "nfa0.report_random_deterministic_path(Tools.tokens('00100'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "f9e50022-b36b-45bf-be09-576c0914a874",
   "metadata": {},
   "outputs": [],
   "source": [
    "nfa0_ne = nfa0.no_epsilon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "26eed986",
   "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: nondeterministic_finite_state_machine Pages: 1 -->\n<svg width=\"319pt\" height=\"170pt\"\n viewBox=\"0.00 0.00 319.19 170.30\" 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 166.2964)\">\n<title>nondeterministic_finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-166.2964 315.1857,-166.2964 315.1857,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"20.1482\" cy=\"-109.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-105.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\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=\"M11.9359,-127.597C10.403,-137.8525 13.1404,-147.2964 20.1482,-147.2964 24.6376,-147.2964 27.3744,-143.4206 28.3586,-137.9386\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"31.8586,-137.5977 28.3605,-127.597 24.8586,-137.5963 31.8586,-137.5977\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-151.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q3 -->\n<g id=\"node2\" class=\"node\">\n<title>q3</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"287.0375\" cy=\"-82.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"287.0375\" cy=\"-82.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"287.0375\" y=\"-78.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q3</text>\n</g>\n<!-- q0&#45;&gt;q3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q0&#45;&gt;q3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M40.2819,-112.8093C46.0778,-113.7287 52.4215,-114.6069 58.2964,-115.1482 129.392,-121.6994 149.1092,-126.2556 218.8893,-111.1482 231.6525,-108.385 245.0147,-103.2498 256.4918,-98.0597\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"258.0896,-101.1758 265.6347,-93.7379 255.0981,-94.8472 258.0896,-101.1758\"/>\n<text text-anchor=\"middle\" x=\"156.5928\" y=\"-123.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2 -->\n<g id=\"node3\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"198.7411\" cy=\"-82.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"198.7411\" y=\"-78.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q0&#45;&gt;q2 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M40.2879,-106.1035C71.5894,-101.3712 132.1025,-92.2227 168.615,-86.7027\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"169.3105,-90.1374 178.675,-85.1818 168.2641,-83.2161 169.3105,-90.1374\"/>\n<text text-anchor=\"middle\" x=\"114.4446\" y=\"-100.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q1 -->\n<g id=\"node4\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"114.4446\" cy=\"-20.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"114.4446\" y=\"-16.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n</g>\n<!-- q0&#45;&gt;q1 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q0&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M34.882,-95.242C50.1545,-80.8273 74.2219,-58.1117 91.8901,-41.4359\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"94.6331,-43.6598 99.5031,-34.2505 89.8283,-38.5691 94.6331,-43.6598\"/>\n<text text-anchor=\"middle\" x=\"67.2964\" y=\"-75.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0,1</text>\n</g>\n<!-- q3&#45;&gt;q3 -->\n<g id=\"edge9\" class=\"edge\">\n<title>q3&#45;&gt;q3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M278.5473,-105.126C277.7387,-115.4058 280.5687,-124.2964 287.0375,-124.2964 291.1815,-124.2964 293.8323,-120.6477 294.9897,-115.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"298.4958,-115.2966 295.5277,-105.126 291.5055,-114.9276 298.4958,-115.2966\"/>\n<text text-anchor=\"middle\" x=\"287.0375\" y=\"-128.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q2&#45;&gt;q3 -->\n<g id=\"edge8\" class=\"edge\">\n<title>q2&#45;&gt;q3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M219.22,-82.1482C229.1271,-82.1482 241.292,-82.1482 252.5704,-82.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"252.5886,-85.6483 262.5886,-82.1482 252.5885,-78.6483 252.5886,-85.6483\"/>\n<text text-anchor=\"middle\" x=\"240.8893\" y=\"-85.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q1&#45;&gt;q3 -->\n<g id=\"edge7\" class=\"edge\">\n<title>q1&#45;&gt;q3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M134.7191,-21.2328C156.2455,-22.9304 190.9484,-27.247 218.8893,-38.1482 233.3529,-43.7912 247.9972,-52.7337 259.9844,-61.0874\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"258.0438,-64.003 268.2028,-67.0106 262.1367,-58.3242 258.0438,-64.003\"/>\n<text text-anchor=\"middle\" x=\"198.7411\" y=\"-41.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- q1&#45;&gt;q2 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q1&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M130.6978,-32.1024C142.98,-41.136 160.052,-53.6924 174.0227,-63.9679\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"172.1206,-66.9136 182.2501,-70.0191 176.2682,-61.2746 172.1206,-66.9136\"/>\n<text text-anchor=\"middle\" x=\"156.5928\" y=\"-55.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- q1&#45;&gt;q1 -->\n<g id=\"edge6\" class=\"edge\">\n<title>q1&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M106.8946,-38.991C105.6115,-49.0931 108.1282,-58.2964 114.4446,-58.2964 118.4911,-58.2964 120.9781,-54.5194 121.9058,-49.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"125.4069,-49.0213 121.9947,-38.991 118.4072,-48.96 125.4069,-49.0213\"/>\n<text text-anchor=\"middle\" x=\"114.4446\" y=\"-62.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7f8c441faa60>"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nfa0_ne.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "90d74cd2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100\t{q0}\n",
      "00\t{q2, q1}\n",
      "0\t{q3}\n",
      "_\t{q3}\n",
      "Completed computation: string accepted\n"
     ]
    }
   ],
   "source": [
    "nfa0_ne.report_computation(Tools.tokens('100'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "f9fd1ab7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q0\t 1000\n",
      "q2\t 000\n",
      "q3\t 00\n",
      "q3\t 0\n",
      "q3\t _\n",
      "Completed path: string accepted\n"
     ]
    }
   ],
   "source": [
    "nfa0_ne.report_random_deterministic_path(Tools.tokens('1000'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9cada723",
   "metadata": {},
   "source": [
    "Definire un ASFND che riconosce il linguaggio $L\\subseteq\\{a,b\\}^*$ definito\n",
    "come $$L_1 = \\{ a^nba^m | n,m\\geq 0 \\}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "e3434614",
   "metadata": {},
   "outputs": [],
   "source": [
    "nfa1 = NFA(\n",
    "    states={'q0', 'q1', 'q2'},\n",
    "    input_symbols={'a', 'b'},\n",
    "    delta={\n",
    "        'q0': {'a': {'q0'}, '': {'q1'}},\n",
    "        'q1': {'b': {'q2'}},\n",
    "        'q2': {'a': {'q2'}}\n",
    "    },\n",
    "    initial_state='q0',\n",
    "    final_states={'q2'}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "b7d05650",
   "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: nondeterministic_finite_state_machine Pages: 1 -->\n<svg width=\"225pt\" height=\"89pt\"\n viewBox=\"0.00 0.00 224.89 89.30\" 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 85.2964)\">\n<title>nondeterministic_finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-85.2964 220.8893,-85.2964 220.8893,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"20.1482\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q0&#45;&gt;q0 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M12.5981,-42.991C11.3151,-53.0931 13.8318,-62.2964 20.1482,-62.2964 24.1947,-62.2964 26.6817,-58.5194 27.6093,-53.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"31.1105,-53.0213 27.6983,-42.991 24.1108,-52.96 31.1105,-53.0213\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-66.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n</g>\n<!-- q1 -->\n<g id=\"node3\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"104.4446\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"104.4446\" y=\"-20.4482\" 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=\"M40.554,-24.1482C50.5977,-24.1482 62.9096,-24.1482 74.0357,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"74.2268,-27.6483 84.2267,-24.1482 74.2267,-20.6483 74.2268,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"62.2964\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">_</text>\n</g>\n<!-- q2 -->\n<g id=\"node2\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"192.7411\" cy=\"-24.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"192.7411\" cy=\"-24.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"192.7411\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q2&#45;&gt;q2 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q2&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M184.2508,-47.126C183.4422,-57.4058 186.2723,-66.2964 192.7411,-66.2964 196.8851,-66.2964 199.5358,-62.6477 200.6933,-57.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"204.1994,-57.2966 201.2313,-47.126 197.2091,-56.9276 204.1994,-57.2966\"/>\n<text text-anchor=\"middle\" x=\"192.7411\" y=\"-70.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n</g>\n<!-- q1&#45;&gt;q2 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q1&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M124.9235,-24.1482C134.8307,-24.1482 146.9956,-24.1482 158.2739,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"158.2922,-27.6483 168.2921,-24.1482 158.2921,-20.6483 158.2922,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"146.5928\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7f8c441ef700>"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nfa1.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "f50d2ee8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "aabaa\t{q0}\n",
      "abaa\t{q0, q1}\n",
      "baa\t{q0, q1}\n",
      "aa\t{q2}\n",
      "a\t{q2}\n",
      "_\t{q2}\n",
      "Completed computation: string accepted\n"
     ]
    }
   ],
   "source": [
    "nfa1.report_computation(Tools.tokens('aabaa'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "d2534054-bdd7-4427-ba80-e133342e7063",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q0\t baa\n",
      "q2\t aa\n",
      "q2\t a\n",
      "q2\t _\n",
      "Completed path: string accepted\n"
     ]
    }
   ],
   "source": [
    "nfa1.report_random_deterministic_path(Tools.tokens('baa'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "0f4add72",
   "metadata": {},
   "outputs": [],
   "source": [
    "nfa1_ne = nfa1.no_epsilon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "1ddd6a38",
   "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: nondeterministic_finite_state_machine Pages: 1 -->\n<svg width=\"224pt\" height=\"113pt\"\n viewBox=\"0.00 0.00 223.89 113.30\" 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 109.2964)\">\n<title>nondeterministic_finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-109.2964 219.8893,-109.2964 219.8893,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"20.1482\" cy=\"-48.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-44.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q0&#45;&gt;q0 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M12.9577,-66.991C11.7357,-77.0931 14.1326,-86.2964 20.1482,-86.2964 24.002,-86.2964 26.3706,-82.5194 27.2541,-77.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"30.7552,-77.0199 27.3388,-66.991 23.7554,-76.9615 30.7552,-77.0199\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-90.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n</g>\n<!-- q2 -->\n<g id=\"node2\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"191.7411\" cy=\"-48.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"191.7411\" cy=\"-48.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"191.7411\" y=\"-44.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q0&#45;&gt;q2 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q0&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M40.294,-51.2874C46.0901,-52.055 52.4309,-52.7655 58.2964,-53.1482 98.7865,-55.7904 109.0874,-55.5424 149.5928,-53.1482 152.1674,-52.996 154.8258,-52.792 157.497,-52.5532\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"158.1265,-56.0068 167.7127,-51.4953 157.4054,-49.044 158.1265,-56.0068\"/>\n<text text-anchor=\"middle\" x=\"103.4446\" y=\"-57.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n</g>\n<!-- q1 -->\n<g id=\"node3\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"103.4446\" cy=\"-20.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"103.4446\" y=\"-16.4482\" 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=\"M39.4675,-41.6541C49.8754,-38.1555 62.9247,-33.7689 74.5189,-29.8716\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"75.8666,-33.1111 84.2302,-26.6071 73.6361,-26.4759 75.8666,-33.1111\"/>\n<text text-anchor=\"middle\" x=\"61.7964\" y=\"-37.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n</g>\n<!-- q2&#45;&gt;q2 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q2&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M183.2508,-71.126C182.4422,-81.4058 185.2723,-90.2964 191.7411,-90.2964 195.8851,-90.2964 198.5358,-86.6477 199.6933,-81.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"203.1994,-81.2966 200.2313,-71.126 196.2091,-80.9276 203.1994,-81.2966\"/>\n<text text-anchor=\"middle\" x=\"191.7411\" y=\"-94.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</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=\"M123.0405,-26.3623C133.5193,-29.6853 146.704,-33.8663 158.7141,-37.6749\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"157.851,-41.0729 168.4412,-40.7595 159.967,-34.4004 157.851,-41.0729\"/>\n<text text-anchor=\"middle\" x=\"145.5928\" y=\"-37.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7f8c45214670>"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nfa1_ne.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "8ac57c38",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "aabaa\t{q0}\n",
      "abaa\t{q0, q1}\n",
      "baa\t{q0, q1}\n",
      "aa\t{q2}\n",
      "a\t{q2}\n",
      "_\t{q2}\n",
      "Completed computation: string accepted\n"
     ]
    }
   ],
   "source": [
    "nfa1_ne.report_computation(Tools.tokens('aabaa'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19fd1bf5",
   "metadata": {},
   "source": [
    "Definire un ASFND che riconosce il linguaggio $L\\subseteq\\{a,b\\}^*$ definito\n",
    "come $$L_1 = \\{ w | uv, u\\in\\{a,b\\}^*, v=aaa \\}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "53eac6a5-ed70-4291-b634-4e142b582f1a",
   "metadata": {},
   "outputs": [],
   "source": [
    "nfa2 = NFA(\n",
    "    states={'q0', 'q1', 'q2', 'q3'},\n",
    "    input_symbols={'a', 'b'},\n",
    "    delta={\n",
    "        'q0': {'a': {'q0', 'q1'}, 'b': {'q0'}},\n",
    "        'q1': {'a': {'q2'}},\n",
    "        'q2': {'a': {'q3'}}\n",
    "    },\n",
    "    initial_state='q0',\n",
    "    final_states={'q3'}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "29f986a5-02f3-4c4d-b5a3-2140899d5018",
   "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: nondeterministic_finite_state_machine Pages: 1 -->\n<svg width=\"306pt\" height=\"85pt\"\n viewBox=\"0.00 0.00 306.19 85.30\" 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 81.2964)\">\n<title>nondeterministic_finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-81.2964 302.1857,-81.2964 302.1857,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"20.1482\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q0&#45;&gt;q0 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M12.9577,-42.991C11.7357,-53.0931 14.1326,-62.2964 20.1482,-62.2964 24.002,-62.2964 26.3706,-58.5194 27.2541,-53.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"30.7552,-53.0199 27.3388,-42.991 23.7554,-52.9615 30.7552,-53.0199\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-66.0964\" 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<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"103.4446\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"103.4446\" y=\"-20.4482\" 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=\"M40.312,-24.1482C50.1635,-24.1482 62.2236,-24.1482 73.1537,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"73.1779,-27.6483 83.1779,-24.1482 73.1778,-20.6483 73.1779,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"61.7964\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n</g>\n<!-- q3 -->\n<g id=\"node2\" class=\"node\">\n<title>q3</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"274.0375\" cy=\"-24.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"274.0375\" cy=\"-24.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"274.0375\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q3</text>\n</g>\n<!-- q2 -->\n<g id=\"node4\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"186.7411\" cy=\"-24.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"186.7411\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q1&#45;&gt;q2 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q1&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M123.6084,-24.1482C133.4599,-24.1482 145.52,-24.1482 156.4501,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"156.4743,-27.6483 166.4743,-24.1482 156.4743,-20.6483 156.4743,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"145.0928\" y=\"-27.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n</g>\n<!-- q2&#45;&gt;q3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q2&#45;&gt;q3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M206.988,-24.1482C216.683,-24.1482 228.5649,-24.1482 239.6191,-24.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"239.8655,-27.6483 249.8655,-24.1482 239.8654,-20.6483 239.8655,-27.6483\"/>\n<text text-anchor=\"middle\" x=\"228.3893\" y=\"-27.9482\" 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 0x7f8c43a9c820>"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nfa2.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "b4cc5a73",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abbaaa\t{q0}\n",
      "bbaaa\t{q0, q1}\n",
      "baaa\t{q0}\n",
      "aaa\t{q0}\n",
      "aa\t{q0, q1}\n",
      "a\t{q2, q0, q1}\n",
      "_\t{q2, q3, q0, q1}\n",
      "Completed computation: string accepted\n"
     ]
    }
   ],
   "source": [
    "nfa2.report_computation(Tools.tokens('abbaaa'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa_nfa2 = nfa2.dfa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"443pt\" height=\"167pt\"\n viewBox=\"0.00 0.00 443.37 167.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 163.0934)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-163.0934 439.3737,-163.0934 439.3737,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"20.1482\" cy=\"-105.9452\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-102.2452\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q0&#45;&gt;q0 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M12.5981,-124.788C11.3151,-134.8901 13.8318,-144.0934 20.1482,-144.0934 24.1947,-144.0934 26.6817,-140.3164 27.6093,-134.9457\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"31.1105,-134.8183 27.6983,-124.788 24.1108,-134.757 31.1105,-134.8183\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-147.8934\" 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<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"115.4937\" cy=\"-100.9452\" rx=\"31.3957\" ry=\"31.3957\"/>\n<text text-anchor=\"middle\" x=\"115.4937\" y=\"-97.2452\" 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=\"M37.8024,-95.6323C44.0616,-92.52 51.2934,-89.5144 58.2964,-87.9452 64.153,-86.6329 70.3446,-86.6139 76.4064,-87.3622\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"75.9274,-90.8336 86.4037,-89.2532 77.2285,-83.9556 75.9274,-90.8336\"/>\n<text text-anchor=\"middle\" x=\"62.2964\" y=\"-91.7452\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n</g>\n<!-- q0.q1.q2.q3 -->\n<g id=\"node2\" class=\"node\">\n<title>q0.q1.q2.q3</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"377.4285\" cy=\"-57.9452\" rx=\"53.8943\" ry=\"53.8943\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"377.4285\" cy=\"-57.9452\" rx=\"57.8905\" ry=\"57.8905\"/>\n<text text-anchor=\"middle\" x=\"377.4285\" y=\"-54.2452\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0.q1.q2.q3</text>\n</g>\n<!-- q0.q1.q2.q3&#45;&gt;q0 -->\n<g id=\"edge7\" class=\"edge\">\n<title>q0.q1.q2.q3&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M320.1926,-48.7261C259.921,-41.2509 163.0316,-35.6388 84.2964,-60.9452 69.0807,-65.8357 54.3203,-75.715 42.802,-84.9741\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"40.4186,-82.4055 35.0278,-91.5263 44.9298,-87.7581 40.4186,-82.4055\"/>\n<text text-anchor=\"middle\" x=\"168.6909\" y=\"-49.7452\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n</g>\n<!-- q0.q1.q2.q3&#45;&gt;q0.q1.q2.q3 -->\n<g id=\"edge8\" class=\"edge\">\n<title>q0.q1.q2.q3&#45;&gt;q0.q1.q2.q3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M363.3614,-114.2488C364.8938,-125.6944 369.5828,-133.8904 377.4285,-133.8904 382.6998,-133.8904 386.5462,-130.1906 388.9676,-124.2912\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"392.4485,-124.8007 391.4956,-114.2488 385.6602,-123.0918 392.4485,-124.8007\"/>\n<text text-anchor=\"middle\" x=\"377.4285\" y=\"-137.6904\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n</g>\n<!-- q0.q1&#45;&gt;q0 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q0.q1&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M84.0428,-102.5945C73.2589,-103.16 61.2177,-103.7915 50.5209,-104.3524\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"50.1715,-100.8659 40.3685,-104.8848 50.5381,-107.8563 50.1715,-100.8659\"/>\n<text text-anchor=\"middle\" x=\"62.2964\" y=\"-107.7452\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n</g>\n<!-- q0.q1.q2 -->\n<g id=\"node4\" class=\"node\">\n<title>q0.q1.q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"233.5871\" cy=\"-112.9452\" rx=\"42.7926\" ry=\"42.7926\"/>\n<text text-anchor=\"middle\" x=\"233.5871\" y=\"-109.2452\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0.q1.q2</text>\n</g>\n<!-- q0.q1&#45;&gt;q0.q1.q2 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q0.q1&#45;&gt;q0.q1.q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M146.8305,-104.1295C157.1891,-105.1821 169.0192,-106.3842 180.5413,-107.555\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"180.2402,-111.0423 190.5428,-108.5713 180.9479,-104.0782 180.2402,-111.0423\"/>\n<text text-anchor=\"middle\" x=\"168.6909\" y=\"-110.7452\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n</g>\n<!-- q0.q1.q2&#45;&gt;q0 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q0.q1.q2&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M193.9935,-129.7229C163.7289,-140.2977 121.0919,-150.3302 84.2964,-140.9452 70.5224,-137.432 56.517,-130.2893 45.1215,-123.3673\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"46.9109,-120.3574 36.5963,-117.9368 43.1501,-126.2614 46.9109,-120.3574\"/>\n<text text-anchor=\"middle\" x=\"115.4937\" y=\"-147.7452\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n</g>\n<!-- q0.q1.q2&#45;&gt;q0.q1.q2.q3 -->\n<g id=\"edge6\" class=\"edge\">\n<title>q0.q1.q2&#45;&gt;q0.q1.q2.q3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M273.6549,-97.6246C286.0826,-92.8728 300.1003,-87.5128 313.72,-82.3051\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"314.9706,-85.5742 323.061,-78.7335 312.4705,-79.0358 314.9706,-85.5742\"/>\n<text text-anchor=\"middle\" x=\"297.9833\" y=\"-92.7452\" 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 0x7f8c4416d610>"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa_nfa2.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "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: finite_state_machine Pages: 1 -->\n<svg width=\"308pt\" height=\"122pt\"\n viewBox=\"0.00 0.00 308.19 122.30\" 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 118.2964)\">\n<title>finite_state_machine</title>\n<polygon fill=\"#d3d3d3\" stroke=\"transparent\" points=\"-4,4 -4,-118.2964 304.1857,-118.2964 304.1857,4 -4,4\"/>\n<!-- q0 -->\n<g id=\"node1\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"#add8e6\" stroke=\"#000000\" cx=\"20.1482\" cy=\"-61.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-57.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q0</text>\n</g>\n<!-- q0&#45;&gt;q0 -->\n<g id=\"edge1\" class=\"edge\">\n<title>q0&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M12.5981,-79.991C11.3151,-90.0931 13.8318,-99.2964 20.1482,-99.2964 24.1947,-99.2964 26.6817,-95.5194 27.6093,-90.1487\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"31.1105,-90.0213 27.6983,-79.991 24.1108,-89.96 31.1105,-90.0213\"/>\n<text text-anchor=\"middle\" x=\"20.1482\" y=\"-103.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n</g>\n<!-- q2 -->\n<g id=\"node3\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"104.4446\" cy=\"-56.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"104.4446\" y=\"-52.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q2</text>\n</g>\n<!-- q0&#45;&gt;q2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q0&#45;&gt;q2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M37.8024,-50.8353C44.0616,-47.723 51.2934,-44.7174 58.2964,-43.1482 64.2282,-41.819 70.5313,-42.3062 76.5111,-43.6816\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"75.5587,-47.0507 86.1467,-46.6709 77.6329,-40.365 75.5587,-47.0507\"/>\n<text text-anchor=\"middle\" x=\"62.2964\" y=\"-46.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n</g>\n<!-- q1 -->\n<g id=\"node2\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"276.0375\" cy=\"-24.1482\" rx=\"20.2726\" ry=\"20.2726\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"276.0375\" cy=\"-24.1482\" rx=\"24.2973\" ry=\"24.2973\"/>\n<text text-anchor=\"middle\" x=\"276.0375\" y=\"-20.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q1</text>\n</g>\n<!-- q1&#45;&gt;q0 -->\n<g id=\"edge7\" class=\"edge\">\n<title>q1&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M251.7948,-21.5931C215.0888,-18.3795 143.4205,-14.6735 84.2964,-27.1482 70.4778,-30.0638 56.4669,-36.9405 45.0792,-43.7523\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"43.1533,-40.8289 36.5626,-49.1244 46.8879,-46.7495 43.1533,-40.8289\"/>\n<text text-anchor=\"middle\" x=\"146.5928\" y=\"-22.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n</g>\n<!-- q1&#45;&gt;q1 -->\n<g id=\"edge8\" class=\"edge\">\n<title>q1&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M267.9164,-47.126C267.143,-57.4058 269.85,-66.2964 276.0375,-66.2964 280.0014,-66.2964 282.5368,-62.6477 283.6439,-57.3225\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"287.1499,-57.2897 284.1586,-47.126 280.1588,-56.9368 287.1499,-57.2897\"/>\n<text text-anchor=\"middle\" x=\"276.0375\" y=\"-70.0964\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n</g>\n<!-- q2&#45;&gt;q0 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q2&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M84.2267,-57.3474C74.2115,-57.9415 61.9065,-58.6713 50.7658,-59.3321\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"50.3292,-55.8518 40.554,-59.9379 50.7437,-62.8395 50.3292,-55.8518\"/>\n<text text-anchor=\"middle\" x=\"62.2964\" y=\"-61.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n</g>\n<!-- q3 -->\n<g id=\"node4\" class=\"node\">\n<title>q3</title>\n<ellipse fill=\"#c0c0c0\" stroke=\"#000000\" cx=\"188.7411\" cy=\"-56.1482\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"188.7411\" y=\"-52.4482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">q3</text>\n</g>\n<!-- q2&#45;&gt;q3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q2&#45;&gt;q3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M124.8504,-56.1482C134.8941,-56.1482 147.2061,-56.1482 158.3321,-56.1482\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"158.5232,-59.6483 168.5232,-56.1482 158.5231,-52.6483 158.5232,-59.6483\"/>\n<text text-anchor=\"middle\" x=\"146.5928\" y=\"-59.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a</text>\n</g>\n<!-- q3&#45;&gt;q0 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q3&#45;&gt;q0</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M171.5267,-66.691C159.0239,-73.6443 141.4161,-82.0245 124.5928,-85.1482 95.4128,-90.5663 86.1981,-87.2641 58.2964,-77.1482 54.9543,-75.9365 51.4783,-74.5952 48.0452,-73.2197\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"49.2091,-69.9136 38.6303,-69.3318 46.5373,-76.3837 49.2091,-69.9136\"/>\n<text text-anchor=\"middle\" x=\"104.4446\" y=\"-90.9482\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n</g>\n<!-- q3&#45;&gt;q1 -->\n<g id=\"edge6\" class=\"edge\">\n<title>q3&#45;&gt;q1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M207.6831,-49.2047C218.104,-45.3847 231.3263,-40.5378 243.3593,-36.127\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"244.9151,-39.2844 253.0996,-32.5565 242.5059,-32.7121 244.9151,-39.2844\"/>\n<text text-anchor=\"middle\" x=\"230.3893\" y=\"-44.9482\" 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 0x7f8c45214e50>"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa_nfa2.renamed_states.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "ce48646bb6368aff8c12a2b8eeb9d1b908c9dd0a6e2925fc70e8d8f5f2053bd1"
  },
  "kernelspec": {
   "display_name": "Python 3.8",
   "language": "python",
   "name": "python3.8"
  },
  "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}