{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Automaten und Sprachen – Notebook\n",
    "\n",
    "**Informatik 12 · Formale Sprachen**\n",
    "\n",
    "Ein endlicher Automat ist in Python ein `dict` und eine Schleife — mehr nicht.\n",
    "Genau das macht ihn so brauchbar: Was im Heft eine Tabelle ist, ist hier ein\n",
    "lauffähiges Programm.\n",
    "\n",
    "Am Ende programmieren Sie die Teilmengenkonstruktion und lassen eine Grammatik\n",
    "Wörter erzeugen.\n",
    "\n",
    "Führen Sie zuerst die nächste Zelle aus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Der Automat aus Abschnitt 5.6: akzeptiert alle Woerter ueber {a, b},\n",
    "# die auf \"abb\" enden.\n",
    "ABB = {\n",
    "    \"zustaende\": [\"z0\", \"z1\", \"z2\", \"z3\"],\n",
    "    \"start\": \"z0\",\n",
    "    \"akzeptierend\": [\"z3\"],\n",
    "    \"uebergang\": {\n",
    "        (\"z0\", \"a\"): \"z1\", (\"z0\", \"b\"): \"z0\",\n",
    "        (\"z1\", \"a\"): \"z1\", (\"z1\", \"b\"): \"z2\",\n",
    "        (\"z2\", \"a\"): \"z1\", (\"z2\", \"b\"): \"z3\",\n",
    "        (\"z3\", \"a\"): \"z1\", (\"z3\", \"b\"): \"z0\",\n",
    "    },\n",
    "}\n",
    "\n",
    "ALPHABET = [\"a\", \"b\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 1 · Ein Automat, der liest\n",
    "\n",
    "Schreiben Sie `akzeptiert(automat, wort)`: Die Funktion startet im Startzustand,\n",
    "liest das Wort Zeichen für Zeichen und gibt am Ende zurück, ob sie in einem\n",
    "Endzustand steht.\n",
    "\n",
    "Fehlt ein Übergang, bleibt der Automat stehen und akzeptiert nicht.\n",
    "\n",
    "**Frage:** Was liefert Ihre Funktion für das leere Wort `\"\"` — und ist das richtig?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def akzeptiert(automat, wort):\n",
    "    zustand = automat[\"start\"]\n",
    "    # TODO: ueber das Wort laufen; bei fehlendem Uebergang False zurueckgeben\n",
    "    return zustand in automat[\"akzeptierend\"]\n",
    "\n",
    "\n",
    "# for wort in [\"abb\", \"aabb\", \"abba\", \"babb\", \"ab\", \"\", \"b\"]:\n",
    "#     print(wort.ljust(6), akzeptiert(ABB, wort))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 2 · Die Übergangstabelle ausgeben\n",
    "\n",
    "Geben Sie die Übergangstabelle so aus, wie sie im Heft steht: eine Zeile je\n",
    "Zustand, eine Spalte je Zeichen, Endzustände markiert.\n",
    "\n",
    "**Frage:** Woran erkennt man an der Tabelle, ob der Automat deterministisch ist?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tabelle(automat, alphabet=ALPHABET):\n",
    "    # TODO: Kopfzeile und je Zustand eine Zeile ausgeben\n",
    "    pass\n",
    "\n",
    "\n",
    "# tabelle(ABB)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 3 · Einen eigenen Automaten bauen\n",
    "\n",
    "Bauen Sie einen DEA über $\\{a, b\\}$, der genau die Wörter mit einer **geraden\n",
    "Anzahl von $a$** akzeptiert. Das leere Wort gehört dazu.\n",
    "\n",
    "Testen Sie ihn gegen eine Vergleichsfunktion, die einfach die $a$ zählt — für alle\n",
    "Wörter bis zur Länge 8.\n",
    "\n",
    "**Frage:** Ihr Automat kommt mit zwei Zuständen aus. Wie viele bräuchte er für „Anzahl der $a$ ist durch 5 teilbar“? Und für „Anzahl der $a$ ist gleich der Anzahl der $b$“?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "\n",
    "GERADE_A = {\n",
    "    \"zustaende\": [\"g\", \"u\"],\n",
    "    \"start\": \"g\",\n",
    "    \"akzeptierend\": [\"g\"],\n",
    "    \"uebergang\": {\n",
    "        # TODO\n",
    "    },\n",
    "}\n",
    "\n",
    "\n",
    "def alle_woerter(bis):\n",
    "    for laenge in range(bis + 1):\n",
    "        for teile in product(ALPHABET, repeat=laenge):\n",
    "            yield \"\".join(teile)\n",
    "\n",
    "\n",
    "# fehler = [w for w in alle_woerter(8)\n",
    "#           if akzeptiert(GERADE_A, w) != (w.count(\"a\") % 2 == 0)]\n",
    "# print(\"Abweichungen:\", len(fehler))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 4 · Nichtdeterminismus: der Automat in mehreren Zuständen\n",
    "\n",
    "Beim NEA führt ein Paar aus Zustand und Zeichen auf eine **Menge** von\n",
    "Folgezuständen. Schreiben Sie `akzeptiert_nea`, das eine Zustandsmenge mitführt.\n",
    "\n",
    "Der NEA unten ist der aus Abschnitt 5.6.2: Wörter über $\\{a, b\\}$, die auf `ab`\n",
    "enden.\n",
    "\n",
    "**Frage:** Wie viele Zustände kann die mitgeführte Menge höchstens enthalten? Und wie viele verschiedene Mengen gibt es damit?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "NEA_AB = {\n",
    "    \"zustaende\": [\"z0\", \"z1\", \"z2\"],\n",
    "    \"start\": \"z0\",\n",
    "    \"akzeptierend\": [\"z2\"],\n",
    "    \"uebergang\": {\n",
    "        (\"z0\", \"a\"): {\"z0\", \"z1\"},\n",
    "        (\"z0\", \"b\"): {\"z0\"},\n",
    "        (\"z1\", \"b\"): {\"z2\"},\n",
    "    },\n",
    "}\n",
    "\n",
    "\n",
    "def akzeptiert_nea(nea, wort):\n",
    "    menge = {nea[\"start\"]}\n",
    "    # TODO: fuer jedes Zeichen die Nachfolgemenge bilden\n",
    "    return bool(menge & set(nea[\"akzeptierend\"]))\n",
    "\n",
    "\n",
    "# for wort in [\"ab\", \"aab\", \"abab\", \"aba\", \"b\", \"\"]:\n",
    "#     print(wort.ljust(6), akzeptiert_nea(NEA_AB, wort))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 5 · Die Teilmengenkonstruktion programmieren\n",
    "\n",
    "Jetzt kommt der Satz aus dem Heft in Codeform: Zu jedem NEA gibt es einen DEA.\n",
    "\n",
    "Bauen Sie aus `NEA_AB` einen DEA. Jeder DEA-Zustand ist eine Menge von\n",
    "NEA-Zuständen; begonnen wird mit $\\{z_0\\}$, und von jeder Menge aus wird für jedes\n",
    "Zeichen die Nachfolgemenge gebildet, bis keine neue mehr entsteht.\n",
    "\n",
    "**Frage:** Prüfen Sie Ihren DEA gegen den NEA für alle Wörter bis Länge 10. Wie viele Zustände hat der DEA geworden — und wie viele hätte er im schlimmsten Fall haben können?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def teilmengenkonstruktion(nea, alphabet=ALPHABET):\n",
    "    start = frozenset([nea[\"start\"]])\n",
    "    offen, zustaende, uebergang = [start], {start}, {}\n",
    "    # TODO: offene Mengen abarbeiten, Nachfolgemengen bilden,\n",
    "    #       neue Mengen in offen und zustaende aufnehmen\n",
    "    return {\n",
    "        \"zustaende\": sorted(zustaende, key=lambda m: sorted(m)),\n",
    "        \"start\": start,\n",
    "        \"akzeptierend\": [m for m in zustaende if m & set(nea[\"akzeptierend\"])],\n",
    "        \"uebergang\": uebergang,\n",
    "    }\n",
    "\n",
    "\n",
    "# dea = teilmengenkonstruktion(NEA_AB)\n",
    "# print(len(dea[\"zustaende\"]), \"Zustaende\")\n",
    "# fehler = [w for w in alle_woerter(10)\n",
    "#           if akzeptiert(dea, w) != akzeptiert_nea(NEA_AB, w)]\n",
    "# print(\"Abweichungen:\", len(fehler))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 6 · Eine Grammatik erzeugt Wörter\n",
    "\n",
    "Eine Grammatik besteht aus Produktionen. Schreiben Sie `erzeuge`, das von einem\n",
    "Startsymbol aus alle Wörter bis zu einer bestimmten Länge ableitet — mit einer\n",
    "Breitensuche über die Satzformen.\n",
    "\n",
    "Die Grammatik unten erzeugt dieselbe Sprache wie `ABB`.\n",
    "\n",
    "**Frage:** Lassen Sie sich die erzeugten Wörter bis Länge 6 ausgeben und prüfen Sie mit `akzeptiert(ABB, …)` nach. Stimmen Grammatik und Automat überein — und was heißt das für Abschnitt 5.8?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "GRAMMATIK = {\n",
    "    \"start\": \"S\",\n",
    "    \"produktionen\": {\n",
    "        \"S\": [\"aS\", \"bS\", \"aA\"],\n",
    "        \"A\": [\"bB\"],\n",
    "        \"B\": [\"b\"],\n",
    "    },\n",
    "}\n",
    "\n",
    "\n",
    "def erzeuge(grammatik, bis):\n",
    "    \"\"\"Gibt alle ableitbaren Woerter bis zur Laenge bis zurueck.\"\"\"\n",
    "    fertige, offen = set(), [grammatik[\"start\"]]\n",
    "    # TODO: Satzform nehmen, erstes Nichtterminal ersetzen,\n",
    "    #       zu lange Satzformen wegwerfen, fertige Woerter sammeln\n",
    "    return sorted(fertige, key=lambda w: (len(w), w))\n",
    "\n",
    "\n",
    "# woerter = erzeuge(GRAMMATIK, 6)\n",
    "# print(len(woerter), \"Woerter\")\n",
    "# print([w for w in woerter if not akzeptiert(ABB, w)], \"sollte leer sein\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "### Abgabe\n",
    "\n",
    "Fertig ist das Notebook, wenn `akzeptiert` die sieben Testwörter richtig\n",
    "beantwortet, Ihr Automat für „gerade viele $a$“ null Abweichungen hat, die\n",
    "Teilmengenkonstruktion einen DEA liefert, der sich wie der NEA verhält, und die\n",
    "Grammatik nur Wörter erzeugt, die `ABB` akzeptiert.\n",
    "\n",
    "Notieren Sie am Ende, wie viele Zustände Ihr konstruierter DEA hat — und warum\n",
    "es nicht $2^3 = 8$ geworden sind."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
