03_Wörter-und-formale-Sprachen.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Wörter und formale Sprachen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dieses Thema wird einem immer wieder begegnen, denn wir nutzen formale Sprachen, um natürliche Sprachen zu modellieren. Später werden wir sehen, dass man formale Sprachen in Klassen aufteilen kann und die Sprachen teilweise interessante Eigenschaften haben. Doch zuerst benötigen wir etwas Vokabular. \n",
    "\n",
    "Dabei gilt: Alphabete, Worte und Sprachen sind, wenn es um formale Sprachen geht, nicht unbedingt das selbe wie in anderen Bereichen der Linguistik. Es gibt aber durchaus Parallelen. \n",
    "Hier ist es wichtig, die Bezeichnungen hinzunehmen als das, was sie sind: Namen für formal definierte Objekte mit bestimmten Eigenschaften."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Alphabete, Wörter, Länge von Wörtern, leeres Wort, Mengen von Wörtern"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Alphabet**: Eine endlich große Menge von Zeichen. Meist mit $\\Sigma$ (Sigma) bezeichnet. Beispiel: $\\Sigma_1=\\{a,b,c\\}$\n",
    "\n",
    "**Wort**: eine endlich lange Folge von Zeichen eines Alphabets. Meist nutzt man die Variablen $u,v,w$ für Worte. \n",
    "\n",
    "Beispiel: $w_1=acabb$. Man sagt: \"$w_1$ ist ein Wort über $\\Sigma_1$\".\n",
    "\n",
    "**Länge eines Wortes** w: Schreibt man mit senkrechten Strichen, ähnlich der Mächtigkeit einer Menge. Die Länge eines Wortes ist immer eine natürliche Zahl ($\\mathbb{N}$), außer die Länge des leeren Worts (siehe unten).\n",
    "\n",
    "Beispiel: $|w_1|=5$. \n",
    "\n",
    "**leeres Wort**: Das Wort der Länge 0. Quasi das unsichtbare Wort. Um das leere Wort zu notieren, nutzt man meistens den griechischen Buchstaben $\\epsilon$ (epsilon). Manchmal auch $\\lambda$ (lambda).  \n",
    "\n",
    "Es gilt also: $\\epsilon =0$. Das leere Wort ist nicht Teil eines Alphabets. $\\epsilon$ ist also kein Zeichen wie die $a,b,c$ oben, sondern es ist selbst ein Wort. \n",
    "\n",
    "**Leersymbol**: ist ebenfalls ein Zeichen des Alphabets und kann mit dem Leerzeichen verglichen werden. Es ist ein Wort mit Länge 1.\n",
    "\n",
    "**Mengen von Wörtern**: Wir möchten formal korrekt sagen können: \"$w_1$ ist ein Wort über $\\Sigma_1$\".\n",
    "Dafür definieren wir die Menge aller Wörter, die man mit einem Alphabet bilden kann. Das Alphabet wird mit $\\Sigma$ bezeichnet, und dann ist $\\Sigma^\\ast$ die Menge aller Wörter über $\\Sigma$. \n",
    "\n",
    "Der Stern bedeutet: Bilde Wörter, indem du die Elemente aus $\\Sigma$ beliebig oft wiederholst, auch 0-mal. Das leere Wort ist also ein Wort in $\\Sigma^\\ast$: $\\epsilon \\in \\Sigma^\\ast$.\n",
    "\n",
    "Wenn wir das leere Wort nicht in die Menge der Wörter einschließen wollen, mit denen wir uns beschäftigen, verwenden wir $\\Sigma^+$ statt $\\Sigma^\\ast$. Das ist die Menge der Wörter über das Alphabet $\\Sigma$ ohne $\\epsilon$. Formal heißt das: $\\Sigma^\\ast = \\Sigma^+ \\cup \\{\\epsilon\\}$  \n",
    "\n",
    "$\\Sigma^\\ast$ und $\\Sigma^+$ sind also unendlich groß.\n",
    "\n",
    "Beispiele:\n",
    "\n",
    "$w_1=acabb, w_2=aa, w_3=\\epsilon, w_4=a$ mit $w_1,w_2,w_3,w_4 \\in \\Sigma^\\ast$. \n",
    "Also: $w_1,w_2,w_4 \\in \\Sigma^+$ und $w_3 \\notin \\Sigma^+$\n",
    "\n",
    "Merke: da wir sagen, dass $w_4 \\in \\Sigma^\\ast$ ist, behandeln wir das einzelne $a$ gleichzeitig als Wort und als einzelnes Zeichen des Alphabets."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Verkettung von Wörtern"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Um Wörter hintereinander zu schreiben, benutzt man *Konkatenation* oder *Verkettung*. \n",
    "Das Symbol dafür ist $\\circ$. \n",
    "Da man Wörter sehr häufig verkettet, wird das $\\circ$ im Alltag eines Formalsprachlers oft weggelassen. \n",
    "\n",
    "Beispiel:\n",
    "\n",
    "$$w_1=acabb, w_2=aa, w_3=\\epsilon$$.\n",
    "$$w_1 \\circ w_2 = w_1w_2 = acabb \\circ aa = acabbaa $$\n",
    "$$w_2 \\circ w_3 = w_2w_3 = aa \\circ \\epsilon = aa\\epsilon = aa$$\n",
    "\n",
    "\n",
    "Das Symbol $\\circ$ wird für alle möglichen Konkatenationsoperationen verwendet. Die Verkettung von Wörtern ist aber nicht das selbe wie die Komposition von Funktionen, Konkatenation von Listen,...! Man kann also nicht ein Wort mit einer Funktion verketten, nur weil das selbe Symbol verwendet wird."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Verkettung mit sich selbst\n",
    "\n",
    "Statt $w \\circ w \\circ w \\circ w \\circ w ...$ kann man auch einfach $w^n$ schreiben. \n",
    "\n",
    "Beispiel: $w_{1}^{3}=acabbacabbacabb$\n",
    "\n",
    "Verkettet man ein Wort null-mal mit sich selbst, kommt das leere Wort raus: $w_{1}^{0}=\\epsilon$ $w_1$ ist ja \"weg\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Umkehrung\n",
    "\n",
    "Um ein Wort $w$ rückwärts zu schreiben, schreibt man $w^R$: $w_{1}^{R}=(acabb)^R=bbaca$.\n",
    "\n",
    "Natürlich gilt: $(w^R)^R=w$\n",
    "\n",
    "Wörter, die rückwärts wie vorwärts gleich sind, heißen *Palindrome*: $(rentner)^R=rentner$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Formale Sprachen\n",
    "\n",
    "Formale Sprachen sind Mengen von Wörtern über einem Alphabet. Da es keinen Sinn macht, über so unspezifische Mengen wie z.B. $\\Sigma^\\ast$ zu sprechen, grenzen wir die Sprachen weiter ein. Meist gilt: Eine Sprache $L$ umfasst manche der Wörter aus der Menge aller Wörter über ein Alphabet $\\Sigma$. Es gilt also $L \\subseteq \\Sigma^\\ast$. \n",
    "\n",
    "Sprachen können endlich oder unendlich groß sein. Wir können sie auf unterschiedliche Weise beschreiben. \n",
    "\n",
    "Beispiel: $\\Sigma_2 = \\{a,b\\}$\n",
    "\n",
    "Die Sprache aller Wörter mit Länge von 0,1 oder 2 kann man aufzählen. Wir nennen diese Sprache $L_2$ und es gilt $L_2 \\subseteq \\Sigma_{2}^{\\ast}$: \n",
    "\n",
    "$$L_2=\\{\\epsilon,a,b,aa,bb,ab,ba\\}$$\n",
    "\n",
    "Sei $L_m$ die Menge aller Wörter über $\\Sigma_2$ mit mehr als zwei Buchstaben. Es gilt natürlich $L_m \\subseteq \\Sigma_{2}^{\\ast}$. Deshalb kann man schreiben:\n",
    "\n",
    "$$L_m=\\Sigma_{2}^{\\ast} \\setminus L_2 = \\overline{L_2}$$\n",
    "\n",
    "Man kann $L_m$ aber auch über die implizite Mengendarstellung beschreiben, z.B. so:\n",
    "\n",
    "$$L_m = \\{w\\in \\Sigma_{2}^{\\ast} |\\:|w| > 2\\}$$\n",
    "\n",
    "Ein Video von *theSimpleClub*, das das Obige nochmal erklärt, findest du [hier](https://www.youtube.com/watch?v=JAvIyh0rIV4)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Operationen auf Sprachen\n",
    "\n",
    "Da Sprachen einfach Mengen sind, kann man auf sie die üblichen Mengenoperationen anwenden: Vereinigung, Schnitt, Komplement, etc.\n",
    "\n",
    "Eine \"besondere\" Operation ist die Verkettung von Sprachen. \n",
    "\n",
    "Für zwei Sprachen $K, L \\subseteq \\Sigma^\\ast$ ist die Verknüpfung $K\\circ L$ folgende Operation (umgangssprachlich): Bilde eine Menge von Wörtern, indem Du ein Wort $w_K \\in K$ und ein Wort $w_L \\in L$ nimmst und beide verkettest. Spiele dabei alle Möglichkeiten durch:\n",
    "\n",
    "$$K\\circ L = \\{w_K \\circ w_L \\subseteq \\Sigma^\\ast | w_K \\in K \\text{ und } w_L \\in L\\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Video zu Operationen auf Sprachen"
   ]
  },
  {
   "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_01_Operationen-auf-Sprachen.mp4?autoplay=0\"></video>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Im Video werden die verschiedenen Operationen anhand eines Beispiels erläutert. Hier der Fahrplan:\n",
    "\n",
    "\n",
    "- 0:00-1:52 Erläuterung der Sprachen und Alphabete\n",
    "- 1:53-2:42 Vereinigung zweier Sprachen\n",
    "- 2:42-3:36 Schnitt zweier Sprachen\n",
    "- 3:36-4:40 Komplement einer Sprache\n",
    "- 4:40-Ende Verkettung/Verknüpfung zweier Sprachen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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
}