{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "cce20a2d",
   "metadata": {},
   "source": [
    "# Practical session — Part 2\n",
    "## Grammars, Pushdown Automata, and Turing Machines\n",
    "\n",
    "This notebook is the **second hour** of the practical session.\n",
    "\n",
    "The goal is to see how you can work with:\n",
    "\n",
    "1. CFG\n",
    "2. PDA\n",
    "3. Turing machine\n",
    "\n",
    "### Approximate timing\n",
    "\n",
    "| Number | Activity |\n",
    "|---:|---|\n",
    "| 1 | Context-free grammar as a generator |\n",
    "| 2 | Stack memory and balanced parentheses |\n",
    "| 3 | A pushdown automaton for \\(a^n b^n\\) |\n",
    "| 4 | A stack remembers order: \\(wcw^R\\) |\n",
    "| 5 | Turing machine: unary increment |\n",
    "| 6 | Exit questions |\n",
    "\n",
    "> **Rule for the practical:** predict what will happen before executing the code."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe32d359",
   "metadata": {},
   "source": [
    "## 0. Setup\n",
    "\n",
    "We will use ordinary Python first, then `automata-lib` for the PDA and Turing-machine examples.\n",
    "\n",
    "The library `automata-lib` is installed for the first practise session but if it is not installed, run the installation cell once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "39ca94a6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: automata-lib in /Users/revekkakyriakoglou/miniforge3/lib/python3.9/site-packages (9.1.2)\n",
      "Requirement already satisfied: networkx>=2.6.2 in /Users/revekkakyriakoglou/miniforge3/lib/python3.9/site-packages (from automata-lib) (3.2.1)\n",
      "Requirement already satisfied: frozendict>=2.3.4 in /Users/revekkakyriakoglou/miniforge3/lib/python3.9/site-packages (from automata-lib) (2.4.7)\n",
      "Requirement already satisfied: typing-extensions>=4.5.0 in /Users/revekkakyriakoglou/miniforge3/lib/python3.9/site-packages (from automata-lib) (4.15.0)\n",
      "Requirement already satisfied: cached_method>=0.1.0 in /Users/revekkakyriakoglou/miniforge3/lib/python3.9/site-packages (from automata-lib) (0.1.0)\n",
      "Note: you may need to restart the kernel to use updated packages.\n"
     ]
    }
   ],
   "source": [
    "# Run this only if automata-lib is not already installed.\n",
    "%pip install automata-lib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "a01bf46a",
   "metadata": {},
   "outputs": [],
   "source": [
    "from automata.pda.dpda import DPDA\n",
    "from automata.tm.dtm import DTM"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75bc35d8",
   "metadata": {},
   "source": [
    "# 1. A context-free grammar as a generator\n",
    "\n",
    "Recall the grammar\n",
    "\n",
    "$$\n",
    "S \\to aSb \\mid \\varepsilon.\n",
    "$$\n",
    "\n",
    "It generates\n",
    "\n",
    "$$\n",
    "L=\\{a^n b^n:n\\ge 0\\}.\n",
    "$$\n",
    "\n",
    "For example,\n",
    "\n",
    "$$\n",
    "S\n",
    "\\Rightarrow aSb\n",
    "\\Rightarrow aaSbb\n",
    "\\Rightarrow aabb.\n",
    "$$\n",
    "\n",
    "The function below should reproduce this derivation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "12adc80e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def derive_anbn(n):\n",
    "    \"\"\"\n",
    "    Return the derivation of a^n b^n using:\n",
    "        S -> aSb\n",
    "        S -> ε\n",
    "    \"\"\"\n",
    "    form = \"S\"\n",
    "    steps = [form] # you want a list because you want to keep trace of the construction and the steps that you needed\n",
    "\n",
    "    # TODO 1: apply S -> aSb exactly n times.\n",
    "    for i in range(n):\n",
    "        pass\n",
    "\n",
    "    # TODO 2: apply S -> ε once.\n",
    "\n",
    "    return steps # that is a list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13cd5a06",
   "metadata": {},
   "source": [
    "### Exercise 1\n",
    "\n",
    "Complete `derive_anbn`.\n",
    "\n",
    "Before running it, predict:\n",
    "\n",
    "```python\n",
    "derive_anbn(3)\n",
    "```\n",
    "\n",
    "What should the final word be?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "95e70511",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['S']"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "derive_anbn(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2dac751",
   "metadata": {},
   "source": [
    "### Think\n",
    "\n",
    "The grammar **generates** a valid word.\n",
    "\n",
    "Soon, the PDA will solve the complementary problem:\n",
    "\n",
    "> Given a finished word, is it in the language?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2374c83",
   "metadata": {},
   "source": [
    "# 2. Stack memory\n",
    "\n",
    "In the theory slides, we write the **top of the stack on the left**.\n",
    "\n",
    "For example,\n",
    "\n",
    "\\[\n",
    "BA\n",
    "\\]\n",
    "\n",
    "means that \\(B\\) is on top of \\(A\\).\n",
    "\n",
    "We will follow the same convention in Python: index `0` is the top."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f474acf6",
   "metadata": {},
   "outputs": [],
   "source": [
    "stack = []\n",
    "\n",
    "def push(stack, symbol):\n",
    "    stack.insert(0, symbol)\n",
    "\n",
    "def pop(stack):\n",
    "    if not stack:\n",
    "        raise IndexError(\"Cannot pop an empty stack\")\n",
    "    return stack.pop(0)\n",
    "\n",
    "def top(stack):\n",
    "    return None if not stack else stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6b1d13f9",
   "metadata": {},
   "outputs": [],
   "source": [
    "stack = []\n",
    "\n",
    "push(stack, \"A\")\n",
    "print(\"After push A:\", stack)\n",
    "\n",
    "push(stack, \"B\")\n",
    "print(\"After push B:\", stack)\n",
    "\n",
    "print(\"Top:\", top(stack))\n",
    "\n",
    "removed = pop(stack)\n",
    "print(\"Popped:\", removed)\n",
    "print(\"Stack now:\", stack)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cd6a8e7",
   "metadata": {},
   "source": [
    "## Exercise 2 — Balanced parentheses\n",
    "\n",
    "A stack can recognise balanced parentheses:\n",
    "\n",
    "- read `(` → push `X`;\n",
    "- read `)` → pop `X`;\n",
    "- reject if a `)` appears when the stack is empty;\n",
    "- accept only if the stack is empty at the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2acb77d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def balanced_parentheses(word, show_trace=False):\n",
    "    stack = []\n",
    "\n",
    "    for char in word:\n",
    "        if char == \"(\":\n",
    "            # TODO: push one marker\n",
    "            pass\n",
    "\n",
    "        elif char == \")\":\n",
    "            # TODO:\n",
    "            # reject if there is nothing to pop;\n",
    "            # otherwise pop one marker\n",
    "            pass\n",
    "\n",
    "        else:\n",
    "            raise ValueError(\"Input must contain only '(' and ')'.\")\n",
    "\n",
    "        if show_trace:\n",
    "            print(f\"read {char!r:>3}   stack = {''.join(stack) or 'ε'}\")\n",
    "\n",
    "    # TODO: accept exactly when the stack is empty\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5c339a4",
   "metadata": {},
   "source": [
    "Predict the answers before running:\n",
    "\n",
    "| Input | Prediction |\n",
    "|---|---|\n",
    "| `(()())` | ? |\n",
    "| `(()` | ? |\n",
    "| `())` | ? |\n",
    "| `()()` | ? |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8ac3687f",
   "metadata": {},
   "outputs": [],
   "source": [
    "tests = [\"(()())\", \"(()\", \"())\", \"()()\"]\n",
    "\n",
    "for word in tests:\n",
    "    print(f\"{word:8} -> {balanced_parentheses(word)}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ee7b66e",
   "metadata": {},
   "outputs": [],
   "source": [
    "balanced_parentheses(\"(()())\", show_trace=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "77984aef",
   "metadata": {},
   "source": [
    "# 3. A pushdown automaton for \\(a^n b^n\\)\n",
    "\n",
    "We now use `automata-lib`.\n",
    "\n",
    "For this practical machine we use\n",
    "\n",
    "\\[\n",
    "L=\\{a^n b^n:n\\ge 1\\}.\n",
    "\\]\n",
    "\n",
    "The idea is the same as in the theory:\n",
    "\n",
    "1. every `a` pushes one `A`;\n",
    "2. every `b` pops one `A`;\n",
    "3. accept only when all markers have been matched.\n",
    "\n",
    "The library uses an initial bottom-of-stack symbol `Z`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc866f83",
   "metadata": {},
   "source": [
    "### Reading the transition dictionary\n",
    "\n",
    "For example,\n",
    "\n",
    "```python\n",
    "'a': {'A': ('q_push', ('A', 'A'))}\n",
    "```\n",
    "\n",
    "means:\n",
    "\n",
    "> If the next input is `a` and `A` is on top of the stack, go to `q_push`\n",
    "> and replace `A` by `AA`.\n",
    "\n",
    "One extra `A` has therefore been pushed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "471dad4c",
   "metadata": {},
   "outputs": [],
   "source": [
    "anbn = DPDA(\n",
    "    states={\"q_start\", \"q_push\", \"q_pop\", \"q_accept\"},\n",
    "    input_symbols={\"a\", \"b\"},\n",
    "    stack_symbols={\"Z\", \"A\"},\n",
    "    transitions={\n",
    "        \"q_start\": {\n",
    "            \"a\": {\"Z\": (\"q_push\", (\"A\", \"Z\"))},\n",
    "        },\n",
    "\n",
    "        \"q_push\": {\n",
    "            \"a\": {\n",
    "                # TODO: push one more A\n",
    "                \"A\": None,\n",
    "            },\n",
    "            \"b\": {\n",
    "                # TODO: switch to pop phase and remove one A\n",
    "                \"A\": None,\n",
    "            },\n",
    "        },\n",
    "\n",
    "        \"q_pop\": {\n",
    "            \"b\": {\n",
    "                # TODO: remove one A\n",
    "                \"A\": None,\n",
    "            },\n",
    "            \"\": {\n",
    "                \"Z\": (\"q_accept\", (\"Z\",)),\n",
    "            },\n",
    "        },\n",
    "    },\n",
    "    initial_state=\"q_start\",\n",
    "    initial_stack_symbol=\"Z\",\n",
    "    final_states={\"q_accept\"},\n",
    "    acceptance_mode=\"final_state\",\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "443366b5",
   "metadata": {},
   "source": [
    "### Exercise 3\n",
    "\n",
    "Fill the three missing transitions.\n",
    "\n",
    "Before running, classify:\n",
    "\n",
    "- `ab`\n",
    "- `aabb`\n",
    "- `aaabbb`\n",
    "- `aab`\n",
    "- `abb`\n",
    "- `abab`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "42a270a4",
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'anbn' 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[5], line 4\u001b[0m\n\u001b[1;32m      1\u001b[0m words \u001b[38;5;241m=\u001b[39m [\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mab\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124maabb\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124maaabbb\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124maab\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mabb\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mabab\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 words:\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[43manbn\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 'anbn' is not defined"
     ]
    }
   ],
   "source": [
    "words = [\"ab\", \"aabb\", \"aaabbb\", \"aab\", \"abb\", \"abab\"]\n",
    "\n",
    "for word in words:\n",
    "    print(f\"{word} -> {anbn.accepts_input(word)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14fbc3da",
   "metadata": {},
   "source": [
    "### Trace a complete computation\n",
    "\n",
    "`read_input_stepwise` exposes the configurations of the PDA.\n",
    "\n",
    "Compare these configurations with the theoretical notation\n",
    "\n",
    "\\[\n",
    "\\langle q,\\;w,\\;\\alpha\\rangle.\n",
    "\\]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "43a2b2ac",
   "metadata": {},
   "outputs": [],
   "source": [
    "for step, configuration in enumerate(anbn.read_input_stepwise(\"aaabbb\")):\n",
    "    print(f\"step {step}: {configuration}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b423dc11",
   "metadata": {},
   "source": [
    "### Questions\n",
    "\n",
    "1. When does the machine switch from the push phase to the pop phase?\n",
    "2. What information is represented by the number of `A` symbols?\n",
    "3. Why can a DFA not store the same information for arbitrary \\(n\\)?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3337b21",
   "metadata": {},
   "source": [
    "# 4. A stack remembers order, not only count\n",
    "\n",
    "Consider\n",
    "\n",
    "\\[\n",
    "L=\\{wcw^R:w\\in\\{a,b\\}^*\\}.\n",
    "\\]\n",
    "\n",
    "Examples include:\n",
    "\n",
    "- `c`\n",
    "- `aca`\n",
    "- `abcba`\n",
    "- `bbcbb`\n",
    "\n",
    "Before `c`, the PDA stores the letters of \\(w\\).\n",
    "After `c`, the stack returns them in reverse order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5ae1116b",
   "metadata": {},
   "outputs": [],
   "source": [
    "wcwr = DPDA(\n",
    "    states={\"q_store\", \"q_check\", \"q_accept\"},\n",
    "    input_symbols={\"a\", \"b\", \"c\"},\n",
    "    stack_symbols={\"Z\", \"A\", \"B\"},\n",
    "    transitions={\n",
    "        \"q_store\": {\n",
    "            \"a\": {\n",
    "                \"Z\": (\"q_store\", (\"A\", \"Z\")),\n",
    "                \"A\": (\"q_store\", (\"A\", \"A\")),\n",
    "                \"B\": (\"q_store\", (\"A\", \"B\")),\n",
    "            },\n",
    "            \"b\": {\n",
    "                \"Z\": (\"q_store\", (\"B\", \"Z\")),\n",
    "                \"A\": (\"q_store\", (\"B\", \"A\")),\n",
    "                \"B\": (\"q_store\", (\"B\", \"B\")),\n",
    "            },\n",
    "            \"c\": {\n",
    "                \"Z\": (\"q_check\", (\"Z\",)),\n",
    "                \"A\": (\"q_check\", (\"A\",)),\n",
    "                \"B\": (\"q_check\", (\"B\",)),\n",
    "            },\n",
    "        },\n",
    "        \"q_check\": {\n",
    "            \"a\": {\"A\": (\"q_check\", \"\")},\n",
    "            \"b\": {\"B\": (\"q_check\", \"\")},\n",
    "            \"\": {\"Z\": (\"q_accept\", (\"Z\",))},\n",
    "        },\n",
    "    },\n",
    "    initial_state=\"q_store\",\n",
    "    initial_stack_symbol=\"Z\",\n",
    "    final_states={\"q_accept\"},\n",
    "    acceptance_mode=\"final_state\",\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47a5f73f",
   "metadata": {},
   "source": [
    "### Exercise 4\n",
    "\n",
    "Predict which words are accepted."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7aeb3785",
   "metadata": {},
   "outputs": [],
   "source": [
    "words = [\"c\", \"aca\", \"abcba\", \"bbcbb\", \"abcab\", \"abca\", \"abba\"]\n",
    "\n",
    "for word in words:\n",
    "    print(f\"{word} -> {wcwr.accepts_input(word)}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "360e3280",
   "metadata": {},
   "outputs": [],
   "source": [
    "for step, configuration in enumerate(wcwr.read_input_stepwise(\"abcba\")):\n",
    "    print(f\"step {step}: {configuration}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8903faa0",
   "metadata": {},
   "source": [
    "### Why does the separator `c` matter?\n",
    "\n",
    "In \\(wcw^R\\), `c` tells the PDA exactly when to stop pushing and start popping.\n",
    "\n",
    "Without a separator, as in\n",
    "\n",
    "$$\n",
    "\\{ww^R:w\\in\\{a,b\\}^*\\},\n",
    "$$\n",
    "\n",
    "the midpoint is not marked. An NPDA can use nondeterminism to **guess** it."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53f263db",
   "metadata": {},
   "source": [
    "# 5. Turing machine: unary increment\n",
    "\n",
    "A Turing machine has more flexible memory than a PDA.\n",
    "\n",
    "It can:\n",
    "\n",
    "- read the current tape symbol;\n",
    "- write a symbol;\n",
    "- move left or right;\n",
    "- change state.\n",
    "\n",
    "Unary `1111` represents \\(4\\).\n",
    "\n",
    "The machine should compute\n",
    "\n",
    "$$\n",
    "1111 \\longrightarrow 11111.\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4be3bb15",
   "metadata": {},
   "outputs": [],
   "source": [
    "unary_increment = DTM(\n",
    "    states={\"q_scan\", \"q_halt\"},\n",
    "    input_symbols={\"1\"},\n",
    "    tape_symbols={\"1\", \".\"},\n",
    "    transitions={\n",
    "        \"q_scan\": {\n",
    "            \"1\": (\"q_scan\", \"1\", \"R\"),\n",
    "\n",
    "            # TODO:\n",
    "            # when the first blank is reached,\n",
    "            # write 1, move right, and halt\n",
    "            \".\": None,\n",
    "        }\n",
    "    },\n",
    "    initial_state=\"q_scan\",\n",
    "    blank_symbol=\".\",\n",
    "    final_states={\"q_halt\"},\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c9b525f",
   "metadata": {},
   "source": [
    "### Exercise 5\n",
    "\n",
    "Complete the missing transition, then trace the machine on `111`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3f8e8355",
   "metadata": {},
   "outputs": [],
   "source": [
    "for step, configuration in enumerate(\n",
    "    unary_increment.read_input_stepwise(\"111\")\n",
    "):\n",
    "    print(f\"step {step}: {configuration}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "135e6092",
   "metadata": {},
   "source": [
    "## Optional challenge — add two\n",
    "\n",
    "Modify the Turing machine so that\n",
    "\n",
    "$$\n",
    "111 \\longrightarrow 11111.\n",
    "$$\n",
    "\n",
    "Hint: after writing the first new `1`, use an additional state to write the second."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "13ad0cfa",
   "metadata": {},
   "outputs": [],
   "source": [
    "# OPTIONAL CHALLENGE\n",
    "# Build your machine here."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb93e39c",
   "metadata": {},
   "source": [
    "# 6. Exit questions\n",
    "\n",
    "Answer without running code.\n",
    "\n",
    "1. Why can a stack recognise \\(a^n b^n\\) while a DFA cannot?\n",
    "2. In \\(wcw^R\\), what does the stack remember besides a count?\n",
    "3. Why is the separator `c` useful?\n",
    "4. What can a Turing-machine tape do that a stack cannot?\n",
    "5. Which progression best summarises the course?\n",
    "\n",
    "\\[\n",
    "\\boxed{\\text{finite state}}\n",
    "\\longrightarrow\n",
    "\\boxed{\\text{stack}}\n",
    "\\longrightarrow\n",
    "\\boxed{\\text{read/write tape}}\n",
    "\\]"
   ]
  }
 ],
 "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
}