{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c02eb6ca",
   "metadata": {},
   "source": [
    "# Practical — First steps with `automata-lib`\n",
    "\n",
    "**Duration: 60 minutes**\n",
    "\n",
    "This notebook assumes that you know basic Python, but that you have **never used `automata-lib` before**.\n",
    "\n",
    "The goal is not to memorize a Python API. The goal is to connect the mathematical objects from the lecture to executable objects.\n",
    "\n",
    "We will use only a few library operations:\n",
    "\n",
    "| Python | Meaning |\n",
    "|---|---|\n",
    "| `DFA(...)` | create a deterministic finite automaton |\n",
    "| `NFA(...)` | create a nondeterministic finite automaton |\n",
    "| `.accepts_input(word)` | ask whether a word is accepted |\n",
    "| `.read_input_stepwise(word)` | inspect the computation step by step |\n",
    "| `DFA.from_nfa(nfa)` | convert an NFA into a DFA |\n",
    "\n",
    "At the very end, we will optionally use `NFA.from_regex(...)`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45adad54",
   "metadata": {},
   "source": [
    "## 0. Setup and library orientation — 10 minutes\n",
    "\n",
    "`automata-lib` is a Python library for manipulating finite automata, pushdown automata, and Turing machines.\n",
    "\n",
    "If the library is not installed in your environment, run the next cell once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1acbde1f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Uncomment this line only if automata-lib is not already installed.\n",
    "# %pip install automata-lib"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "543848d3",
   "metadata": {},
   "source": [
    "We import two Python classes:\n",
    "\n",
    "- `DFA` for deterministic finite automata;\n",
    "- `NFA` for nondeterministic finite automata.\n",
    "\n",
    "The names of the Python arguments closely follow the mathematical definition\n",
    "\n",
    "\\[\n",
    "A=(Q,\\Sigma,\\delta,q_0,F).\n",
    "\\]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d0fdfd13",
   "metadata": {},
   "outputs": [],
   "source": [
    "from automata.fa.dfa import DFA\n",
    "from automata.fa.nfa import NFA"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c2c013d",
   "metadata": {},
   "source": [
    "### Reading a DFA definition in Python\n",
    "\n",
    "Do **not** edit this first example. Just read it.\n",
    "\n",
    "It is the same automaton from the lecture: it accepts binary words containing an even number of `1`s."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "9ae2c27b",
   "metadata": {},
   "outputs": [],
   "source": [
    "even_ones = DFA(\n",
    "    states={\"even\", \"odd\"},            # Q\n",
    "    input_symbols={\"0\", \"1\"},          # Sigma\n",
    "    transitions={                      # delta\n",
    "        \"even\": {\"0\": \"even\", \"1\": \"odd\"},\n",
    "        \"odd\":  {\"0\": \"odd\",  \"1\": \"even\"},\n",
    "    },\n",
    "    initial_state=\"even\",              # q_0\n",
    "    final_states={\"even\"},             # F\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68ab380b",
   "metadata": {},
   "source": [
    "The transition dictionary\n",
    "\n",
    "```python\n",
    "\"even\": {\"0\": \"even\", \"1\": \"odd\"}\n",
    "```\n",
    "\n",
    "means:\n",
    "\n",
    "- if the machine is in state `even` and reads `0`, stay in `even`;\n",
    "- if it reads `1`, move to `odd`.\n",
    "\n",
    "This is simply the transition table written as a Python dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "47b6c63e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "states: frozenset({'even', 'odd'})\n",
      "alphabet: frozenset({'1', '0'})\n",
      "initial state: even\n",
      "accepting states: frozenset({'even'})\n"
     ]
    }
   ],
   "source": [
    "# We can inspect the object we created.\n",
    "print(\"states:\", even_ones.states)\n",
    "print(\"alphabet:\", even_ones.input_symbols)\n",
    "print(\"initial state:\", even_ones.initial_state)\n",
    "print(\"accepting states:\", even_ones.final_states)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef931fb5",
   "metadata": {},
   "source": [
    "### Your first library call\n",
    "\n",
    "Before running the cell, predict the output for each word."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "f7101b00",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "'' -> True\n",
      "'0' -> True\n",
      "'1' -> False\n",
      "'11' -> True\n",
      "'1011' -> False\n",
      "'1111' -> True\n"
     ]
    }
   ],
   "source": [
    "words = [\"\", \"0\", \"1\", \"11\", \"1011\", \"1111\"]\n",
    "\n",
    "for word in words:\n",
    "    answer = even_ones.accepts_input(word)\n",
    "    print(f\"'{word}' -> {answer}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f554780",
   "metadata": {},
   "source": [
    "`True` means **accepted** and `False` means **rejected**.\n",
    "\n",
    "**Question:** Why is the empty word `\"\"` accepted?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a6ca9b8",
   "metadata": {},
   "source": [
    "---\n",
    "## 1. Follow a computation step by step\n",
    "\n",
    "Instead of asking only for the final answer, we can inspect the sequence of states visited by the DFA."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "617acf56",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['even', 'odd', 'odd', 'even', 'odd']\n"
     ]
    }
   ],
   "source": [
    "word = \"1011\"\n",
    "\n",
    "states_visited = list(\n",
    "    even_ones.read_input_stepwise(\n",
    "        word,\n",
    "        ignore_rejection=True\n",
    "    )\n",
    ")\n",
    "\n",
    "print(states_visited)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "173a0f92",
   "metadata": {},
   "source": [
    "Compare the Python output with the path from the lecture:\n",
    "\n",
    "| Step | Symbol read | State |\n",
    "|---:|:---:|:---:|\n",
    "| 0 | — | **even** |\n",
    "| 1 | `1` | **odd** |\n",
    "| 2 | `0` | **odd** |\n",
    "| 3 | `1` | **even** |\n",
    "| 4 | `1` | **odd** |\n",
    "\n",
    "### Exercise\n",
    "\n",
    "Change `word` to each of the following and predict the final state before running the code:\n",
    "\n",
    "- `1100`\n",
    "- `111`\n",
    "- `101101`\n",
    "\n",
    "Then answer:\n",
    "\n",
    "**What information is the Python object actually remembering while it runs?**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bcc17b75",
   "metadata": {},
   "source": [
    "---\n",
    "## 2. Build your first DFA \n",
    "\n",
    "Now we will construct a new machine ourselves.\n",
    "\n",
    "### Language\n",
    "\n",
    "Accept binary words that contain the substring `11`.\n",
    "\n",
    "Examples:\n",
    "\n",
    "- `11` → accept\n",
    "- `1011` → accept\n",
    "- `001100` → accept\n",
    "- `1010` → reject\n",
    "\n",
    "### Step 1 — decide what the states mean\n",
    "\n",
    "We will use:\n",
    "\n",
    "- `q0`: we have not seen `11`, and the previous symbol is not `1`;\n",
    "- `q1`: we have not seen `11`, but the previous symbol is `1`;\n",
    "- `q2`: we have already seen `11`.\n",
    "\n",
    "### Step 2 — complete the transitions\n",
    "\n",
    "Fill in the strings marked `TODO`.\n",
    "\n",
    "**Tip:** every state must have exactly one transition for `0` and exactly one transition for `1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "da4e12c4",
   "metadata": {},
   "outputs": [
    {
     "ename": "InvalidStateError",
     "evalue": "end state TODO for transition on q0 is not valid",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mInvalidStateError\u001b[0m                         Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[15], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m contains_11 \u001b[38;5;241m=\u001b[39m \u001b[43mDFA\u001b[49m\u001b[43m(\u001b[49m\n\u001b[1;32m      2\u001b[0m \u001b[43m    \u001b[49m\u001b[43mstates\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43m{\u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mq0\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mq1\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mq2\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m}\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m      3\u001b[0m \u001b[43m    \u001b[49m\u001b[43minput_symbols\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43m{\u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43m0\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43m1\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m}\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m      4\u001b[0m \u001b[43m    \u001b[49m\u001b[43mtransitions\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43m{\u001b[49m\n\u001b[1;32m      5\u001b[0m \u001b[43m        \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mq0\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m:\u001b[49m\u001b[43m \u001b[49m\u001b[43m{\u001b[49m\n\u001b[1;32m      6\u001b[0m \u001b[43m            \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43m0\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m:\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mTODO\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m,\u001b[49m\n\u001b[1;32m      7\u001b[0m \u001b[43m            \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43m1\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m:\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mTODO\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m,\u001b[49m\n\u001b[1;32m      8\u001b[0m \u001b[43m        \u001b[49m\u001b[43m}\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m      9\u001b[0m \u001b[43m        \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mq1\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m:\u001b[49m\u001b[43m \u001b[49m\u001b[43m{\u001b[49m\n\u001b[1;32m     10\u001b[0m \u001b[43m            \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43m0\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m:\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mTODO\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m,\u001b[49m\n\u001b[1;32m     11\u001b[0m \u001b[43m            \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43m1\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m:\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mTODO\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m,\u001b[49m\n\u001b[1;32m     12\u001b[0m \u001b[43m        \u001b[49m\u001b[43m}\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m     13\u001b[0m \u001b[43m        \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mq2\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m:\u001b[49m\u001b[43m \u001b[49m\u001b[43m{\u001b[49m\n\u001b[1;32m     14\u001b[0m \u001b[43m            \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43m0\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m:\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mTODO\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m,\u001b[49m\n\u001b[1;32m     15\u001b[0m \u001b[43m            \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43m1\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m:\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mTODO\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m,\u001b[49m\n\u001b[1;32m     16\u001b[0m \u001b[43m        \u001b[49m\u001b[43m}\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m     17\u001b[0m \u001b[43m    \u001b[49m\u001b[43m}\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m     18\u001b[0m \u001b[43m    \u001b[49m\u001b[43minitial_state\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mq0\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m,\u001b[49m\n\u001b[1;32m     19\u001b[0m \u001b[43m    \u001b[49m\u001b[43mfinal_states\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43m{\u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mTODO\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m}\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m     20\u001b[0m \u001b[43m)\u001b[49m\n",
      "File \u001b[0;32m~/miniforge3/lib/python3.9/site-packages/automata/fa/dfa.py:119\u001b[0m, in \u001b[0;36mDFA.__init__\u001b[0;34m(self, states, input_symbols, transitions, initial_state, final_states, allow_partial)\u001b[0m\n\u001b[1;32m    108\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21m__init__\u001b[39m(\n\u001b[1;32m    109\u001b[0m     \u001b[38;5;28mself\u001b[39m,\n\u001b[1;32m    110\u001b[0m     \u001b[38;5;241m*\u001b[39m,\n\u001b[0;32m   (...)\u001b[0m\n\u001b[1;32m    116\u001b[0m     allow_partial: \u001b[38;5;28mbool\u001b[39m \u001b[38;5;241m=\u001b[39m \u001b[38;5;28;01mFalse\u001b[39;00m,\n\u001b[1;32m    117\u001b[0m ) \u001b[38;5;241m-\u001b[39m\u001b[38;5;241m>\u001b[39m \u001b[38;5;28;01mNone\u001b[39;00m:\n\u001b[1;32m    118\u001b[0m \u001b[38;5;250m    \u001b[39m\u001b[38;5;124;03m\"\"\"Initialize a complete DFA.\"\"\"\u001b[39;00m\n\u001b[0;32m--> 119\u001b[0m     \u001b[38;5;28;43msuper\u001b[39;49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[38;5;21;43m__init__\u001b[39;49m\u001b[43m(\u001b[49m\n\u001b[1;32m    120\u001b[0m \u001b[43m        \u001b[49m\u001b[43mstates\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43mstates\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    121\u001b[0m \u001b[43m        \u001b[49m\u001b[43minput_symbols\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43minput_symbols\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    122\u001b[0m \u001b[43m        \u001b[49m\u001b[43mtransitions\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43mtransitions\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    123\u001b[0m \u001b[43m        \u001b[49m\u001b[43minitial_state\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43minitial_state\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    124\u001b[0m \u001b[43m        \u001b[49m\u001b[43mfinal_states\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43mfinal_states\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    125\u001b[0m \u001b[43m        \u001b[49m\u001b[43mallow_partial\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43mallow_partial\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    126\u001b[0m \u001b[43m    \u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m    128\u001b[0m     \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mclear_cache()\n",
      "File \u001b[0;32m~/miniforge3/lib/python3.9/site-packages/automata/base/automaton.py:66\u001b[0m, in \u001b[0;36mAutomaton.__init__\u001b[0;34m(self, **kwargs)\u001b[0m\n\u001b[1;32m     64\u001b[0m     \u001b[38;5;28;01mfor\u001b[39;00m attr_name, attr_value \u001b[38;5;129;01min\u001b[39;00m kwargs\u001b[38;5;241m.\u001b[39mitems():\n\u001b[1;32m     65\u001b[0m         \u001b[38;5;28mobject\u001b[39m\u001b[38;5;241m.\u001b[39m\u001b[38;5;21m__setattr__\u001b[39m(\u001b[38;5;28mself\u001b[39m, attr_name, attr_value)\n\u001b[0;32m---> 66\u001b[0m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43m__post_init__\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\n",
      "File \u001b[0;32m~/miniforge3/lib/python3.9/site-packages/automata/base/automaton.py:73\u001b[0m, in \u001b[0;36mAutomaton.__post_init__\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m     69\u001b[0m \u001b[38;5;250m\u001b[39m\u001b[38;5;124;03m\"\"\"\u001b[39;00m\n\u001b[1;32m     70\u001b[0m \u001b[38;5;124;03mPerform post-initialization validation of the automaton.\u001b[39;00m\n\u001b[1;32m     71\u001b[0m \u001b[38;5;124;03m\"\"\"\u001b[39;00m\n\u001b[1;32m     72\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m global_config\u001b[38;5;241m.\u001b[39mshould_validate_automata:\n\u001b[0;32m---> 73\u001b[0m     \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mvalidate\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\n",
      "File \u001b[0;32m~/miniforge3/lib/python3.9/site-packages/automata/fa/dfa.py:468\u001b[0m, in \u001b[0;36mDFA.validate\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m    466\u001b[0m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39m_validate_transition_start_states()\n\u001b[1;32m    467\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m start_state, paths \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mtransitions\u001b[38;5;241m.\u001b[39mitems():\n\u001b[0;32m--> 468\u001b[0m     \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43m_validate_transitions\u001b[49m\u001b[43m(\u001b[49m\u001b[43mstart_state\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mpaths\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m    469\u001b[0m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39m_validate_initial_state()\n\u001b[1;32m    470\u001b[0m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39m_validate_final_states()\n",
      "File \u001b[0;32m~/miniforge3/lib/python3.9/site-packages/automata/fa/dfa.py:448\u001b[0m, in \u001b[0;36mDFA._validate_transitions\u001b[0;34m(self, start_state, paths)\u001b[0m\n\u001b[1;32m    446\u001b[0m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39m_validate_transition_missing_symbols(start_state, paths)\n\u001b[1;32m    447\u001b[0m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39m_validate_transition_invalid_symbols(start_state, paths)\n\u001b[0;32m--> 448\u001b[0m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43m_validate_transition_end_states\u001b[49m\u001b[43m(\u001b[49m\u001b[43mstart_state\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mpaths\u001b[49m\u001b[43m)\u001b[49m\n",
      "File \u001b[0;32m~/miniforge3/lib/python3.9/site-packages/automata/fa/dfa.py:439\u001b[0m, in \u001b[0;36mDFA._validate_transition_end_states\u001b[0;34m(self, start_state, paths)\u001b[0m\n\u001b[1;32m    437\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m end_state \u001b[38;5;129;01min\u001b[39;00m paths\u001b[38;5;241m.\u001b[39mvalues():\n\u001b[1;32m    438\u001b[0m     \u001b[38;5;28;01mif\u001b[39;00m end_state \u001b[38;5;129;01mnot\u001b[39;00m \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mstates:\n\u001b[0;32m--> 439\u001b[0m         \u001b[38;5;28;01mraise\u001b[39;00m exceptions\u001b[38;5;241m.\u001b[39mInvalidStateError(\n\u001b[1;32m    440\u001b[0m             \u001b[38;5;124mf\u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mend state \u001b[39m\u001b[38;5;132;01m{\u001b[39;00mend_state\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m for transition on \u001b[39m\u001b[38;5;124m\"\u001b[39m\n\u001b[1;32m    441\u001b[0m             \u001b[38;5;124mf\u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;132;01m{\u001b[39;00mstart_state\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m is not valid\u001b[39m\u001b[38;5;124m\"\u001b[39m\n\u001b[1;32m    442\u001b[0m         )\n",
      "\u001b[0;31mInvalidStateError\u001b[0m: end state TODO for transition on q0 is not valid"
     ]
    }
   ],
   "source": [
    "contains_11 = DFA(\n",
    "    states={\"q0\", \"q1\", \"q2\"},\n",
    "    input_symbols={\"0\", \"1\"},\n",
    "    transitions={\n",
    "        \"q0\": {\n",
    "            \"0\": \"TODO\",\n",
    "            \"1\": \"TODO\",\n",
    "        },\n",
    "        \"q1\": {\n",
    "            \"0\": \"TODO\",\n",
    "            \"1\": \"TODO\",\n",
    "        },\n",
    "        \"q2\": {\n",
    "            \"0\": \"TODO\",\n",
    "            \"1\": \"TODO\",\n",
    "        },\n",
    "    },\n",
    "    initial_state=\"q0\",\n",
    "    final_states={\"TODO\"},\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e59e0e6",
   "metadata": {},
   "source": [
    "When you think your machine is correct, test it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "91acfdff",
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'contains_11' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[14], line 4\u001b[0m\n\u001b[1;32m      1\u001b[0m tests \u001b[38;5;241m=\u001b[39m [\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124m1\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124m11\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124m1011\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124m1010\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124m111\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124m001100\u001b[39m\u001b[38;5;124m\"\u001b[39m]\n\u001b[1;32m      3\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m word \u001b[38;5;129;01min\u001b[39;00m tests:\n\u001b[0;32m----> 4\u001b[0m     \u001b[38;5;28mprint\u001b[39m(\u001b[38;5;124mf\u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;132;01m{\u001b[39;00mword\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m -> \u001b[39m\u001b[38;5;132;01m{\u001b[39;00m\u001b[43mcontains_11\u001b[49m\u001b[38;5;241m.\u001b[39maccepts_input(word)\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m\"\u001b[39m)\n",
      "\u001b[0;31mNameError\u001b[0m: name 'contains_11' is not defined"
     ]
    }
   ],
   "source": [
    "tests = [\"\", \"1\", \"11\", \"1011\", \"1010\", \"111\", \"001100\"]\n",
    "\n",
    "for word in tests:\n",
    "    print(f\"{word} -> {contains_11.accepts_input(word)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34236e3c",
   "metadata": {},
   "source": [
    "### Debugging question\n",
    "\n",
    "If your code raises an error, first inspect:\n",
    "\n",
    "1. Are all state names written exactly the same way?\n",
    "2. Does every DFA state have a transition for both `0` and `1`?\n",
    "3. Is every accepting state included in `states`?\n",
    "\n",
    "**Conceptual question:** Why should `q2` loop to itself on both `0` and `1`?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce0c6c60",
   "metadata": {},
   "source": [
    "---\n",
    "## 3. First NFA \n",
    "\n",
    "We now recreate the NFA from the lecture for words ending in `01`.\n",
    "\n",
    "The main Python difference is important:\n",
    "\n",
    "- a DFA transition points to **one state**;\n",
    "- an NFA transition points to a **set of possible states**.\n",
    "\n",
    "Compare:\n",
    "\n",
    "```python\n",
    "# DFA\n",
    "\"0\": \"q1\"\n",
    "\n",
    "# NFA\n",
    "\"0\": {\"q0\", \"q1\"}\n",
    "```\n",
    "\n",
    "The braces `{...}` represent the set of possible next states."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e28eb2cf",
   "metadata": {},
   "outputs": [],
   "source": [
    "ending_01_nfa = NFA(\n",
    "    states={\"q0\", \"q1\", \"q2\"},\n",
    "    input_symbols={\"0\", \"1\"},\n",
    "    transitions={\n",
    "        \"q0\": {\n",
    "            \"0\": {\"q0\", \"q1\"},\n",
    "            \"1\": {\"q0\"},\n",
    "        },\n",
    "        \"q1\": {\n",
    "            \"1\": {\"q2\"},\n",
    "        },\n",
    "        \"q2\": {},\n",
    "    },\n",
    "    initial_state=\"q0\",\n",
    "    final_states={\"q2\"},\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a5b8f7e",
   "metadata": {},
   "source": [
    "First, simply test it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "041f9b28",
   "metadata": {},
   "outputs": [],
   "source": [
    "for word in [\"01\", \"1101\", \"1001\", \"011\", \"1010\"]:\n",
    "    print(f\"{word!r:8} -> {ending_01_nfa.accepts_input(word)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d69f60a",
   "metadata": {},
   "source": [
    "Now inspect the possible active states after each symbol:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "adce1b6a",
   "metadata": {},
   "outputs": [],
   "source": [
    "word = \"1101\"\n",
    "\n",
    "for step, active_states in enumerate(\n",
    "    ending_01_nfa.read_input_stepwise(word)\n",
    "):\n",
    "    print(f\"step {step}: {set(active_states)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d47dc7c4",
   "metadata": {},
   "source": [
    "### Questions\n",
    "\n",
    "1. At what point is the NFA in more than one possible state?\n",
    "2. Why does the transition on `0` from `q0` contain both `q0` and `q1`?\n",
    "3. Does the machine literally choose one path, or does the mathematical model keep all possibilities?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79712df3",
   "metadata": {},
   "source": [
    "---\n",
    "## 4. Let the library convert the NFA into a DFA\n",
    "\n",
    "In the lecture, we performed the subset construction by hand.\n",
    "\n",
    "The library can perform the same construction for us:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b6996afd",
   "metadata": {},
   "outputs": [],
   "source": [
    "ending_01_dfa = DFA.from_nfa(\n",
    "    ending_01_nfa,\n",
    "    retain_names=True,\n",
    "    minify=False,\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5b36c27",
   "metadata": {},
   "source": [
    "Inspect the states created by the conversion:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a54de41a",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"DFA states:\")\n",
    "for state in ending_01_dfa.states:\n",
    "    print(state)\n",
    "\n",
    "print(\"\\nAccepting DFA states:\")\n",
    "for state in ending_01_dfa.final_states:\n",
    "    print(state)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8b019d46",
   "metadata": {},
   "source": [
    "You should recognise the idea from the subset-construction slides:\n",
    "\n",
    "\\[\n",
    "\\{q_0\\}, \\qquad\n",
    "\\{q_0,q_1\\}, \\qquad\n",
    "\\{q_0,q_2\\}.\n",
    "\\]\n",
    "\n",
    "Each DFA state represents a **set of possible NFA states**.\n",
    "\n",
    "### Check that the two machines agree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "044bd92b",
   "metadata": {},
   "outputs": [],
   "source": [
    "tests = [\"\", \"0\", \"1\", \"01\", \"101\", \"1101\", \"1010\", \"0001\"]\n",
    "\n",
    "for word in tests:\n",
    "    nfa_answer = ending_01_nfa.accepts_input(word)\n",
    "    dfa_answer = ending_01_dfa.accepts_input(word)\n",
    "\n",
    "    print(\n",
    "        f\"{word!r:8} \"\n",
    "        f\"NFA={nfa_answer!s:5} \"\n",
    "        f\"DFA={dfa_answer!s:5}\"\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ebb60c7a",
   "metadata": {},
   "source": [
    "**Question:** Why is this conversion useful even though the DFA and NFA recognise exactly the same language?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8804043",
   "metadata": {},
   "source": [
    "---\n",
    "## 5. Optional final challenge — regular expression to automaton \n",
    "\n",
    "\n",
    "The regular expression\n",
    "\n",
    "\\[\n",
    "(0|1)^*01\n",
    "\\]\n",
    "\n",
    "describes binary words ending in `01`.\n",
    "\n",
    "`automata-lib` can build an NFA directly from this expression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4ae0eea1",
   "metadata": {},
   "outputs": [],
   "source": [
    "regex_nfa = NFA.from_regex(\n",
    "    \"(0|1)*01\",\n",
    "    input_symbols={\"0\", \"1\"},\n",
    ")\n",
    "\n",
    "for word in [\"01\", \"101\", \"1101\", \"011\", \"1010\"]:\n",
    "    print(word, regex_nfa.accepts_input(word))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a262b36",
   "metadata": {},
   "source": [
    "### Final challenge\n",
    "\n",
    "Change the regular expression so that the automaton accepts binary words containing **exactly one `1`**.\n",
    "\n",
    "First find the the expression for this.\n",
    "\n",
    "Remember that in the Python string we write `0*10*`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "b5fb0382",
   "metadata": {},
   "outputs": [
    {
     "ename": "InvalidSymbolError",
     "evalue": "state 0 has invalid transition symbol T",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mInvalidSymbolError\u001b[0m                        Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[16], line 2\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[38;5;66;03m# TODO\u001b[39;00m\n\u001b[0;32m----> 2\u001b[0m exactly_one_1 \u001b[38;5;241m=\u001b[39m \u001b[43mNFA\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mfrom_regex\u001b[49m\u001b[43m(\u001b[49m\n\u001b[1;32m      3\u001b[0m \u001b[43m    \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mTODO\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m,\u001b[49m\n\u001b[1;32m      4\u001b[0m \u001b[43m    \u001b[49m\u001b[43minput_symbols\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43m{\u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43m0\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43m1\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m}\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m      5\u001b[0m \u001b[43m)\u001b[49m\n\u001b[1;32m      7\u001b[0m \u001b[38;5;66;03m# Uncomment after replacing TODO:\u001b[39;00m\n\u001b[1;32m      8\u001b[0m \u001b[38;5;66;03m# for word in [\"1\", \"01\", \"10\", \"00100\", \"11\", \"101\", \"000\"]:\u001b[39;00m\n\u001b[1;32m      9\u001b[0m \u001b[38;5;66;03m#     print(word, exactly_one_1.accepts_input(word))\u001b[39;00m\n",
      "File \u001b[0;32m~/miniforge3/lib/python3.9/site-packages/automata/fa/nfa.py:234\u001b[0m, in \u001b[0;36mNFA.from_regex\u001b[0;34m(cls, regex, input_symbols)\u001b[0m\n\u001b[1;32m    228\u001b[0m         \u001b[38;5;28;01mraise\u001b[39;00m exceptions\u001b[38;5;241m.\u001b[39mInvalidSymbolError(\n\u001b[1;32m    229\u001b[0m             \u001b[38;5;124mf\u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mInvalid input symbols: \u001b[39m\u001b[38;5;132;01m{\u001b[39;00mconflicting_symbols\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m\"\u001b[39m\n\u001b[1;32m    230\u001b[0m         )\n\u001b[1;32m    232\u001b[0m nfa_builder \u001b[38;5;241m=\u001b[39m parse_regex(regex, input_symbols)\n\u001b[0;32m--> 234\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[38;5;28;43mcls\u001b[39;49m\u001b[43m(\u001b[49m\n\u001b[1;32m    235\u001b[0m \u001b[43m    \u001b[49m\u001b[43mstates\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[38;5;28;43mfrozenset\u001b[39;49m\u001b[43m(\u001b[49m\u001b[43mnfa_builder\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43m_transitions\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mkeys\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\u001b[43m)\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    236\u001b[0m \u001b[43m    \u001b[49m\u001b[43minput_symbols\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43minput_symbols\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    237\u001b[0m \u001b[43m    \u001b[49m\u001b[43mtransitions\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43mnfa_builder\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43m_transitions\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    238\u001b[0m \u001b[43m    \u001b[49m\u001b[43minitial_state\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43mnfa_builder\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43m_initial_state\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    239\u001b[0m \u001b[43m    \u001b[49m\u001b[43mfinal_states\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43mnfa_builder\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43m_final_states\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    240\u001b[0m \u001b[43m\u001b[49m\u001b[43m)\u001b[49m\n",
      "File \u001b[0;32m~/miniforge3/lib/python3.9/site-packages/automata/fa/nfa.py:100\u001b[0m, in \u001b[0;36mNFA.__init__\u001b[0;34m(self, states, input_symbols, transitions, initial_state, final_states)\u001b[0m\n\u001b[1;32m     90\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21m__init__\u001b[39m(\n\u001b[1;32m     91\u001b[0m     \u001b[38;5;28mself\u001b[39m,\n\u001b[1;32m     92\u001b[0m     \u001b[38;5;241m*\u001b[39m,\n\u001b[0;32m   (...)\u001b[0m\n\u001b[1;32m     97\u001b[0m     final_states: AbstractSet[NFAStateT],\n\u001b[1;32m     98\u001b[0m ) \u001b[38;5;241m-\u001b[39m\u001b[38;5;241m>\u001b[39m \u001b[38;5;28;01mNone\u001b[39;00m:\n\u001b[1;32m     99\u001b[0m \u001b[38;5;250m    \u001b[39m\u001b[38;5;124;03m\"\"\"Initialize a complete NFA.\"\"\"\u001b[39;00m\n\u001b[0;32m--> 100\u001b[0m     \u001b[38;5;28;43msuper\u001b[39;49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[38;5;21;43m__init__\u001b[39;49m\u001b[43m(\u001b[49m\n\u001b[1;32m    101\u001b[0m \u001b[43m        \u001b[49m\u001b[43mstates\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43mstates\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    102\u001b[0m \u001b[43m        \u001b[49m\u001b[43minput_symbols\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43minput_symbols\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    103\u001b[0m \u001b[43m        \u001b[49m\u001b[43mtransitions\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43mtransitions\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    104\u001b[0m \u001b[43m        \u001b[49m\u001b[43minitial_state\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43minitial_state\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    105\u001b[0m \u001b[43m        \u001b[49m\u001b[43mfinal_states\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43mfinal_states\u001b[49m\u001b[43m,\u001b[49m\n\u001b[1;32m    106\u001b[0m \u001b[43m    \u001b[49m\u001b[43m)\u001b[49m\n",
      "File \u001b[0;32m~/miniforge3/lib/python3.9/site-packages/automata/base/automaton.py:66\u001b[0m, in \u001b[0;36mAutomaton.__init__\u001b[0;34m(self, **kwargs)\u001b[0m\n\u001b[1;32m     64\u001b[0m     \u001b[38;5;28;01mfor\u001b[39;00m attr_name, attr_value \u001b[38;5;129;01min\u001b[39;00m kwargs\u001b[38;5;241m.\u001b[39mitems():\n\u001b[1;32m     65\u001b[0m         \u001b[38;5;28mobject\u001b[39m\u001b[38;5;241m.\u001b[39m\u001b[38;5;21m__setattr__\u001b[39m(\u001b[38;5;28mself\u001b[39m, attr_name, attr_value)\n\u001b[0;32m---> 66\u001b[0m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43m__post_init__\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\n",
      "File \u001b[0;32m~/miniforge3/lib/python3.9/site-packages/automata/base/automaton.py:73\u001b[0m, in \u001b[0;36mAutomaton.__post_init__\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m     69\u001b[0m \u001b[38;5;250m\u001b[39m\u001b[38;5;124;03m\"\"\"\u001b[39;00m\n\u001b[1;32m     70\u001b[0m \u001b[38;5;124;03mPerform post-initialization validation of the automaton.\u001b[39;00m\n\u001b[1;32m     71\u001b[0m \u001b[38;5;124;03m\"\"\"\u001b[39;00m\n\u001b[1;32m     72\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m global_config\u001b[38;5;241m.\u001b[39mshould_validate_automata:\n\u001b[0;32m---> 73\u001b[0m     \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mvalidate\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\n",
      "File \u001b[0;32m~/miniforge3/lib/python3.9/site-packages/automata/fa/nfa.py:269\u001b[0m, in \u001b[0;36mNFA.validate\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m    256\u001b[0m \u001b[38;5;250m\u001b[39m\u001b[38;5;124;03m\"\"\"\u001b[39;00m\n\u001b[1;32m    257\u001b[0m \u001b[38;5;124;03mRaises an exception if this automaton is not internally consistent.\u001b[39;00m\n\u001b[1;32m    258\u001b[0m \n\u001b[0;32m   (...)\u001b[0m\n\u001b[1;32m    266\u001b[0m \u001b[38;5;124;03m    If this NFA has invalid symbols in the transition dictionary.\u001b[39;00m\n\u001b[1;32m    267\u001b[0m \u001b[38;5;124;03m\"\"\"\u001b[39;00m\n\u001b[1;32m    268\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m start_state, paths \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mtransitions\u001b[38;5;241m.\u001b[39mitems():\n\u001b[0;32m--> 269\u001b[0m     \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43m_validate_transition_invalid_symbols\u001b[49m\u001b[43m(\u001b[49m\u001b[43mstart_state\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mpaths\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m    270\u001b[0m     \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39m_validate_transition_end_states(start_state, paths)\n\u001b[1;32m    271\u001b[0m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39m_validate_initial_state()\n",
      "File \u001b[0;32m~/miniforge3/lib/python3.9/site-packages/automata/fa/nfa.py:196\u001b[0m, in \u001b[0;36mNFA._validate_transition_invalid_symbols\u001b[0;34m(self, start_state, paths)\u001b[0m\n\u001b[1;32m    194\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m input_symbol \u001b[38;5;129;01min\u001b[39;00m paths\u001b[38;5;241m.\u001b[39mkeys():\n\u001b[1;32m    195\u001b[0m     \u001b[38;5;28;01mif\u001b[39;00m input_symbol \u001b[38;5;129;01mnot\u001b[39;00m \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39minput_symbols \u001b[38;5;129;01mand\u001b[39;00m input_symbol \u001b[38;5;241m!=\u001b[39m \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124m\"\u001b[39m:\n\u001b[0;32m--> 196\u001b[0m         \u001b[38;5;28;01mraise\u001b[39;00m exceptions\u001b[38;5;241m.\u001b[39mInvalidSymbolError(\n\u001b[1;32m    197\u001b[0m             \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mstate \u001b[39m\u001b[38;5;132;01m{}\u001b[39;00m\u001b[38;5;124m has invalid transition symbol \u001b[39m\u001b[38;5;132;01m{}\u001b[39;00m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;241m.\u001b[39mformat(\n\u001b[1;32m    198\u001b[0m                 start_state, input_symbol\n\u001b[1;32m    199\u001b[0m             )\n\u001b[1;32m    200\u001b[0m         )\n",
      "\u001b[0;31mInvalidSymbolError\u001b[0m: state 0 has invalid transition symbol T"
     ]
    }
   ],
   "source": [
    "# TODO\n",
    "exactly_one_1 = NFA.from_regex(\n",
    "    \"TODO\",\n",
    "    input_symbols={\"0\", \"1\"},\n",
    ")\n",
    "\n",
    "# Uncomment after replacing TODO:\n",
    "# for word in [\"1\", \"01\", \"10\", \"00100\", \"11\", \"101\", \"000\"]:\n",
    "#     print(word, exactly_one_1.accepts_input(word))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ccc04a0",
   "metadata": {},
   "source": [
    "---\n",
    "# What you should remember\n",
    "\n",
    "You do **not** need to memorize the library syntax.\n",
    "\n",
    "The important correspondence is:\n",
    "\n",
    "\\[\n",
    "\\text{mathematical automaton}\n",
    "\\longleftrightarrow\n",
    "\\text{Python object}.\n",
    "\\]\n",
    "\n",
    "- `states` represents \\(Q\\)\n",
    "- `input_symbols` represents \\(\\Sigma\\)\n",
    "- `transitions` represents \\(\\delta\\)\n",
    "- `initial_state` represents \\(q_0\\)\n",
    "- `final_states` represents \\(F\\)\n",
    "\n",
    "Python lets us **construct, execute, inspect, and transform** the same machines that we studied mathematically."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1073335e",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}