{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Grammatiken"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Formale Grammatiken sind ein immer wiederkehrender Bestandteil im CL-Studium. Da sie in den nächsten Semestern noch ausführlicher behandelt werden, gibt es hier nur einen kurzen Überblick.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Folie Formale Grammatiken](Folien/03/slide-71.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eine formale Grammatik ist ein 4-Tupel und besteht somit aus 4 Teilen. Die Terminalsymbole T sind das Alphabet der formalen Sprache, die die Grammatik generiert. Im Beispiel auf der Folie ist also T={the, cat, sleeps}.\n",
    "N ist die Menge der Nichtterminalsymbole. Salopp gesagt: Diese werden benutzt, um den Sätzen in einer formalen Sprache Struktur zu geben. \n",
    "Im Beispiel ist N={S,NP,VP,V,D,N}. \n",
    "Mit Hilfe der Nichtterminalsymbole kann man Grammatikregeln bilden, sogenannte Produktionen (P). Die Produktionen haben eine linke und eine rechte Regelseite. \n",
    "In der allgemeinen Form der formalen Grammatik (Typ0) gilt dabei nur die Beschränkung, dass die linke Regelseite nicht ausschließlich Terminalsymbole enthalten darf und nicht leer sein darf. Die linke Regelseite kann aber mehrere Symbole enthalten, und die Zusammensetzung der rechten Regelseite ist egal. \n",
    "\n",
    "Das Startsymbol ist das Nichtterminale, mit dem jede Ableitung der Grammatik starten muss. Häufig verwendet man S für Satz. \n",
    "\n",
    "**Frage zum Grübeln:** Warum darf die linke Regelseite nicht $\\epsilon$ sein?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Einschränkungen formaler Grammatiken"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die oben beschriebenen Beschränkungen geben einen sehr mächtigen Formalismus. Wir werden später genauer sehen, warum das so ist. Wichtig ist aber: Typ0-Grammatiken sind so mächtig, dass es unendlich lange dauern kann, um zu entscheiden ob ein Wort von einer Typ0-Grammatik generiert wird oder nicht. \n",
    "Deshalb beschränken wir formale Grammatiken. Die so entstehenden Grammatiken erzeugen Teilmengen der Menge der formalen Sprachen. \n",
    "Die Chomsky-Hierarchie ist eine weit verbreitete Hierarchie für die Beschränkungen formaler Grammatiken.\n",
    "Je stärker die Beschränkung der Produktionen ist, umso schneller kann man erkennen, ob ein Wort durch die Grammatik generiert wird. \n",
    "Hier ist eine grobe Übersicht:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Folie 89](Folien/03/slide-84.png)\n",
    "![Folie 90](Folien/03/slide-85.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Kontextfreie und reguläre Sprachen\n",
    "\n",
    "Einen Teil dieser Tabelle kennen wir schon, und damit wollen wir uns jetzt näher befassen.\n",
    "**Kontextfreie Sprachen** sind die formalen Sprachen, bei denen die linke Regelseite genau ein Symbol enthält, und dieses Symbol ist ein Nichtterminal. Die \"the cat sleeps\"-Grammatik von oben ist also kontextfrei.\n",
    "\n",
    "**Reguläre Sprachen** sind noch weiter beschränkt. Die linke Regelseite besteht aus einem Nichtterminalsymbol. Die rechte Regelseite besteht entweder\n",
    "1. aus einer beliebig langen Kette von Terminalen, gefolgt von einem oder keinem Nichtterminal (rechtsregulär), oder\n",
    "2. aus einem oder null Nichtterminalen, gefolgt von einer beliebig langen Kette von Terminal (linksregulär).\n",
    "\n",
    "Dabei gilt: Die Produktionen einer regulären Grammatik erfüllen alle der selben Beschränkung 1 oder 2.\n",
    "Die Menge der regulären Sprachen ist eine echte Teilmenge der Menge der kontextfreien Sprachen. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Video Linksableitung"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<video \n",
    " controls \n",
    " width=\"560\" \n",
    " height=\"315\" \n",
    " src=\"https://user.phil-fak.uni-duesseldorf.de/~petersen/magrula/videos/03_06_Ableitung.mp4?autoplay=0\"></video>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}