Blitzkurs Theoretische Informatik/ Druckversion

Der Informatiker Edsger Wybe Dijkstra soll einmal gesagt haben: „In der Informatik geht es genau so wenig um Computer wie in der Astronomie um Teleskope.“ Dieser griffige Satz lässt auch einem Laien unmittelbar begreiflich werden, dass Informatiker keineswegs durchweg bleiche Kellergespenster sind, die den ganzen Tag am Computer sitzen, sich von Tiefkühlpizza ernähren und kein Liebesleben kennen. „Den Informatiker“ gibt es sowieso nicht. Genauso wie die Biologie keine monolithische Wissenschaft ist, sondern vielmehr zwischen verschiedenen Teilwissenschaften wie Molekularbiologie, Genetik, Ökologie und Zoologie und auch Überschneidungen mit anderen Wissenschaften wie Bioinformatik und Biochemie unterschieden werden muss, gibt es eben auch solche und solche Informatiker.

Einleitung

Die gängigste Einteilung der Informatik in Teilgebiete unterscheidet die Angewandte Informatik, die Praktische Informatik, die Technische Informatik und eben die Theoretische Informatik.

Unter Angewandter Informatik versteht man unter anderem das, was heutzutage in fast jedem Sekretariat passiert: Auf dem Schreibtisch steht ein Computer, der zur Textverarbeitung, zur Tabellenkalkulation und für Internetdienste wie E-Mail und WWW genutzt wird. Darüber hinaus ist die Angewandte Informatik die Schnittstelle zu allen anderen Wissenschaften, denn sie nutzt die Errungenschaften der anderen Teilgebiete der Informatik, um Computersysteme zur Berechnung und Automatisierung beliebiger Vorgänge zu erstellen.

Mit Praktischer Informatik beschäftigen sich Softwareentwickler, die der Angewandten Informatik unter die Arme greifen, indem sie zu von ihr entworfenen Geräten Treiber programmieren und sonstige Software schreiben.

Die Technische Informatik erforscht, wie Computer und Computernetze aufgebaut sein sollten, damit sie nicht nur funktionieren, sondern das auch noch möglichst schnell und zuverlässig. Die neuesten Bildschirmtechnologien sind ein Produkt der Technischen Informatik, genauso wie die moderne Telekommunikation.

Die Theoretische Informatik schließlich beschäftigt sich mit der Frage, ob ein Problem überhaupt mit Methoden der Informatik lösbar ist und wenn ja, wie effizient. Hier wird die Verwandtschaft der Informatik mit der Mathematik besonders deutlich, denn Theoretische Informatik findet fast ausschließlich im Kopf statt.

Nach dieser Einteilung der Informatik hat als das eine Extremum die Angewandte Informatik am meisten mit Computern zu tun, während das andere Extremum, die Theoretische Informatik, die beständigste Teilwissenschaft ist. Neu erworbenes Wissen in den Teilgebieten Angewandte, Praktische und Technische Informatik kann in zwei Jahren schon wieder veraltet und damit höchstens noch zu nostalgischen Zwecken brauchbar sein. Die Theoretische Informatik aber legt bei ihrer Weiterentwicklung nichts ad acta, und sie ist unabhängig vom technischen Fortschritt. Der Begriff „Theoretische Informatik“ wurde im 20. Jahrhundert geprägt. Völlig unabhängig von der Existenz von Rechenmaschinen hätte man aber auch schon vor dreihundert Jahren anfangen können, die Theoretische Informatik zu entwickeln.

Wenn du mehr über die Theoretische Informatik lernen willst, sei dir also dessen bewusst, dass du dabei nicht erfahren wirst, wie man etwa ein Spiel programmiert. In diesem Buch wirst du nichts über Programmiersprachen, nichts über den inneren Aufbau deines Computers und keine Anleitung zur Installation irgendeiner Software lesen. Es ist noch nicht einmal nötig, dass du beim Nachvollziehen der Aussagen in diesem Buch Zugang zu einem Abakus oder irgendeinem anderen Rechengerät hast. Du benötigst nur einen Stapel Papier, einen Stift und einen wachen Kopf.

Zur Benutzung dieses Buches

Dieser Blitzkurs ist darauf ausgerichtet, dir relativ schmerzlos Wissen über die Theoretische Informatik zu vermitteln. Das bedeutet zum Einen einen lockeren Schreibstil, der Verständlichkeit in den Mittelpunkt stellt und allzu elaboriertes Gefasel zur Seite schiebt und zum Anderen bedeutet das, dass du jeden Tag, an dem du diesen Kurs benutzt, ein bisschen dazulernen kannst. Du bekommst das Wissen in schmackhaften kleinen Häppchen vermittelt, so dass du niemals das Gefühl hast, dich verfranst zu haben. Wenn du irgendwann keine Lust mehr hast, kannst du von einem Tag auf den anderen aufhören und du weißt, was du bis dahin alles gelernt hast.

Der Kurs ist in Wochenabschnitte eingeteilt, die aus fünf Tagen und einem Rückblick bestehen. Die Tagesrationen und die Rückblicke sind so angelegt, dass sie etwa eine halbe oder eine Stunde in Anspruch nehmen. Wenn du dir mehr zutraust, kannst du deine Geschwindigkeit natürlich auch verdoppeln indem du zwei Häppchen pro Tag verschlingst. Aber übertreibe es bitte nicht.

Die Rückblicklektionen sind geeignet, sie sich immer wieder anzusehen. Sie komprimieren das Wissen der vergangenen fünf Tage in Form von Übungen. Du kannst bei fortgeschrittenem Lernerfolg hin und wieder eine Woche einschieben, in der du ausschließlich vergangene Rückblicke durcharbeitest. Auch wenn du den ganzen Kurs erfolgreich abgeschlossen hast, solltest du dir das Gelernte ab und zu zurück ins Bewusstsein rufen, weil du es sonst schneller vergisst als du denkst.

Jede Woche und jeder Tag beginnt mit einer blau unterlegten Zusammenfassung:

Zusammenfassung

In diesem Kasten steht in verkürzter Form das, was du in der folgenden Woche beziehungsweise dem folgenden Tag lernst.

Es ist in jedem Fall zu empfehlen, diesen Abriss zu lesen, auch wenn du kein Wort kapierst. Es wird hin und wieder vorkommen, dass du doch etwas verstehst. Und du hast ein Ziel vor Augen: Was werde ich am Ende dieser Woche oder dieses Tages wissen? Wenn du schon über ein Vorwissen in dem behandelten Thema verfügst, können dir diese Zusammenfassungen hilfreich sein, zu entscheiden, ob du diesen Teil des Kurses überhaupt lesen möchtest. Vielleicht reicht es dir, dich an den Übungen zu probieren.

Die Übungen im grünen Kasten zieren das Ende jedes Tageshäppchens und sind der wichtigste Bestandteil der Rückblicke. Hier kommt gleich die erste Übung:

Übung

Die Lösungen zu den Übungen in diesen Kästen findest du im letzten Kapitel namens Lösungen. Probiere das mal aus! Die erste Aufgabe lautet: In welche vier Teilwissenschaften unterteilt man die Informatik?

Die Lösungen stehen am Ende des Buches im Abschnitt Lösungen.

Sollte dir beim Durcharbeiten des Kurses etwas unklar sein, zögere nicht, zu fragen. Wenn du etwas nicht ganz verstanden hast und dir irgendwas zusammenreimst, lernst du mit einem Halbwissen weiter und es werden vielleicht in den folgenden Lektionen weitere Fragen aufgeworfen. Sobald du am Ende einer Tagesration nicht das Gefühl hast, bestens informiert zu sein, frage bitte auf der _Diskussionsseite nach. Du kannst jetzt mit dem ersten Häppchen beginnen. Heute ist Tag 1 der Woche _Sprachen allgemein.

Wochenlektionen

Sprachen allgemein

Zusammenfassung

Eine Sprache ist eine Menge von Wörtern, ein Wort ist eine Folge von Buchstaben aus einem Alphabet. Ein Alphabet ist eine Menge von Buchstaben. Die Länge von Wörtern bestimmt man mit Betragsstrichen. Das Nullwort heißt $\varepsilon :|\varepsilon |=0.$ Man kann Buchstaben, Wörter und die Elemente von Alphabeten und Sprachen mit dem Konkatenationsoperator $\cdot$ verketten. Die Potenzierung $X^{y}$ ist eine Mehrfachausführung der Konkatenation. Der Kleene-Stern-Operator $X^{\star }$ ist die Vereinigung aller natürlichen Potenzen. Die absteigende Reihenfolge der Priorität dieser Operatoren ist: Potenzierung und Kleene-Stern, Konkatenation, Vereinigung.

Tag 1

Zusammenfassung

Ein Compiler übersetzt Quelltext in ein lauffähiges Programm. Der Compilerbau fällt viel leichter, wenn man das Wissen der Theoretischen Informatik anwenden kann. Grundbegriffe bezüglich Sprachen: Buchstabe $a,$ Alphabet $\Sigma$ (Menge von Buchstaben), Wort $w$ (Folge von Buchstaben), Sprache $L$ (Menge von Wörtern), $\Sigma ^{*}$ (Menge aller Wörter über $\Sigma$)

Mitte der 50er Jahre baute man den ersten Compiler. Ein Compiler ist ein Computerprogramm, das den Quelltext eines anderen Programms aus einer von Menschen überschaubaren Programmiersprache wie Pascal, BASIC oder C in eine ausführbare Folge von Nullen und Einsen übersetzt. Ein Compiler wandelt also Befehle, die der Programmierer dem Computer mittels einer formalisierten Sprache gibt, in das eigentliche Programm um. Mit dem ersten Compiler gab es erstmals die Möglichkeit, mit dem Computer fast wie mit einem Menschen zu reden und ihm mitzuteilen, was man ausrechnen möchte. Die Sprache, die damals verwendet wurde, heißt FORTRAN und wurde vor allem dafür entwickelt, den Computer als mächtige Rechenmaschine benutzen zu können. FORTRAN ist ein Akronym. Ausgesprochen heißt es formula translation. (englisch für Formelübersetzung)

Diesen Compiler zu bauen, dauerte insgesamt 18 Personenjahre. Heute ist das eine Praktikumsaufgabe für Informatikstudenten. Dieser enorme Effizienzgewinn beruht unter anderem auf dem Fortschritt in der Theoretischen Informatik. Man weiß heute vieles über Programmiersprachen. Man weiß, warum einige Sprachen, wie zum Beispiel Polnisch, nicht geeignet sind, mit dem Computer zu reden, andere dagegen, wie etwa Pascal, aber durchaus.

Dieser Blitzkurs wird zunächst ein paar Worte über Sprachen im Allgemeinen verlieren. Eigentlich ist alles ganz einfach solange man leicht Parallelen zur deutschen Sprache ziehen kann.

Eine Sprache $L$ – mit dem Buchstaben $L$ bezeichnet man im Allgemeinen irgendeine ausgedachte Sprache – verfügt über ein gewisses Vokabular. Klar. Wie die Wörter, die die Sprache kennt, im Einzelnen lauten, ist erst einmal egal. Irgendein Wort kann man $w$ nennen. Das ist nicht das Wort selbst, sondern nur eine abstrakte Bezeichnung. Da ja nicht alle Wörter $w$ heißen können, nummeriert man sie durch: $w_{1},w_{2},w_{3},\ldots w_{2127},w_{2128}$ – falls die jeweilige Sprache zufällig 2 128 verschiedene Wörter kennt. 2 128 Wörter sind nichts als 2 128 Folgen von Buchstaben. Es könnte sein, dass $w_{366}$ aus den drei Buchstaben $a_{1},$ $a_{2}$ und $a_{3}$ besteht. Der Übersichtlichkeit halber nennt man alle Buchstaben $a$ und gibt ihnen eine Nummer. In alter Mathematikermanier kann man den Index, also diese tiefergestellte Zahl, auch weglassen, wenn von einem beliebigen Buchstaben die Rede ist. Zum Beispiel: Das Wort $w$ beginnt mit dem Buchstaben $a$ und endet mit $a.$ Das heißt, wir denken uns ein Wort, das mit dem gleichen Buchstaben beginnt, mit dem es endet. Das Wort Lagerregal erfüllt diese Regel, genauso wie Hirsch. Die Länge des Wortes ist nicht bekannt, also egal.

Wie viele verschiedene Buchstaben $a$ gibt es eigentlich? Das hängt von der Sprache ab. Zu jeder Sprache gehört ein Alphabet. Man symbolisiert es üblicherweise mit dem griechischen Großbuchstaben $\Sigma .$ Das Alphabet $\Sigma$ ist eine Menge von Buchstaben $a.$

Eine Sprache ist also nichts als die Menge aller Wörter, die man verstehen muss, um von sich behaupten zu können, diese Sprache zu kennen. Üblicherweise verwendet man den Buchstaben $L,$ um irgendeine Sprache zu bezeichnen. Es gibt eine wichtige Ausnahme von dieser Regel. Wenn man eine Sprache als die Menge sämtlicher Wörter, die man aus einem Alphabet bilden kann, definieren möchte, kann man stattdessen den Kleene-Stern [ˈkliːni] (nach dem Informatiker Stephen Cole Kleene) verwenden:

Das Alphabet $\Sigma$ besteht, für dieses Beispiel, aus den Buchstaben „A“, „B“, „a“ und „b“. Dann kennt die Sprache $\Sigma ^{\star }$ die Wörter „“, „A“, „B“, „a“, „b“, „AA“, „AB“, „Aa“, „Ab“, „BA“, „BB“, „Ba“, „Bb“, „aA“, „aB“, „aa“, „ab“, „“bA, „bB“, „ba“, „bb“, „AAA“, „AAB“, … Zur Sprache $\Sigma ^{\star }$ gehören sämtliche Folgen von Buchstaben des Alphabets $\Sigma .$ Das sind unendlich viele. Auch das Wort, das aus keinem einzigen Buchstaben besteht, gehört dazu. Es sind eben alle Wörter, die mit den Buchstaben des Alphabets auskommen. Auch wenn das Alphabet nur aus einem einzigen Buchstaben besteht, ist die Sprache $\Sigma ^{\star }$ als Menge aller Wörter eine unendliche Menge.

Übung

Welche dieser Aussagen ist falsch?: „Ein $w$ ist eine geordnete Folge von $a.$“, „Ein $\Sigma$ ist eine ungeordnete Menge von $a.$“, „Ein $L$ ist eine geordnete Folge von $\Sigma .$“, „Ein $L$ ist eine ungeordnete Menge von $w.$“

---

$\Sigma _{b}=\{0;1\}$ nennt man das binäre Alphabet. Welche Wörter kennt die Sprache $\Sigma _{b}^{\star }$?

---

Wenn $\Sigma =\{{\text{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}}\},$ welches der folgenden Wörter gehört dann nicht zur Sprache $\Sigma ^{\star }$?:
„monatlich“, „sichtbar“, „verlängern“, „quer“, „jxq“, „manchmal“

Die Lösungen stehen am Ende des Buches im Abschnitt Lösungen.

Tag 2

Zusammenfassung

$|w|$ ist die Länge von $w,$ also die Anzahl der Buchstaben. $|\varepsilon |$ ist 0. Die Konkatenation ist eine Operation, die Wörter aneinander hängt. Dabei ist die Reihenfolge wichtig. Die Konkatenation mit $\varepsilon$ hat keinen Effekt. Präfixe, Suffixe und Infixe sind Anwendungen der Konkatenation.

Gestern hast du das leere Wort kennen gelernt. Das erscheint vielleicht nicht besonders sinnvoll. Aber wenn ein Wort eine Folge von beliebig vielen Buchstaben ist, dann kann es eben auch eine Folge von genau null Buchstaben sein. Das ist wissenschaftliche Exaktheit. Wenn man mit Wörtern rechnet, (Ja, das kommt noch.) dann kann ein Wort aus null Buchstaben ziemlich nützlich sein. Deshalb erhält es ein Symbol. Man bezeichnet das leere Wort normalerweise mit dem griechischen Kleinbuchstaben Epsilon $(\varepsilon ).$

Über dem Alphabet $\Sigma$ mit den Buchstaben „A“, „B“, „a“ und „b“ gibt es ganz schön viele Wörter der Länge 50. (gut eine Quintillion) Es gibt sechzehn Wörter der Länge 2: „AA“, „AB“, „Aa“, „Ab“, „BA“, „BB“, „Ba“, „Bb“, „aA“, „aB“, „aa“, „ab“, „“bA, „bB“, „ba“ und „bb“. Es gibt vier Wörter der Länge 1: „A“, „B“, „a“ und „b“. Und es gibt ein Wort der Länge 0: $\varepsilon$ oder „“. Beachte, dass $\varepsilon$ nicht das Wort selbst ist, sondern nur ein Formelzeichen.

Für die Länge eines Wortes gibt es eine einfache Schreibweise mit Betragsstrichen:

• Wenn $w$ aus den Buchstaben $a_{1}$ und $a_{2}$ besteht, dann kann man sagen $|w|=2.$
• $|\varepsilon |=0$

Jetzt aber zum Rechnen mit Wörtern: Im Deutschen kann man Wörter aneinander hängen, um neue Wörter zu bilden. Aus „kennen“ und „lernen“ wird „kennenlernen“. In der Theoretischen Informatik nennt man das Konkatenation und man verwendet dafür das Multiplikationszeichen: „kennen“ ⋅ „lernen“ = „kennenlernen“. Wenn man $w_{1}$ mit drei Buchstaben und $w_{2}$ mit siebzig Buchstaben konkateniert, hat das Ergebnis dreiundsiebzig Buchstaben: $|w_{1}\cdot w_{2}|=|w_{1}|+|w_{2}|.$ Diese Gleichung bedeutet, dass die Länge des Wortes, das bei der Konkatenation von $w_{1}$ und $w_{2}$ entsteht, mit der Addition der Länge von $w_{1}$ und der Länge von $w_{2}$ ausgerechnet werden kann.

Bei der Konkatenation ist die Reihenfolge der Operanden entscheidend. $w_{1}\cdot w_{2}$ muss nicht das gleiche sein wie $w_{2}\cdot w_{1}.$ Es gibt nur zwei Ausnahmen: Zum Einen ist die Reihenfolge dann egal, wenn $w_{1}$ und $w_{2}$ identisch sind. Zum Anderen könnte aber auch eins der Wörter $\varepsilon$ sein. Egal, ob man $w\cdot \varepsilon$ oder $\varepsilon \cdot w$ oder $\varepsilon \cdot \varepsilon \cdot w\cdot \varepsilon$ rechnet, das Ergebnis ist immer wieder $w.$

Die Konkatenation führt uns zum Thema Affixe. Präfixe und Suffixe kennst du bestimmt. Präfixe sind im Deutschen zum Beispiel „ver-“, „aus-“ und „um-“. Das sind keine ganzen Wörter, sondern Anfangsstücke von Wörtern, die den Wörtern andere Bedeutungen geben. Aus „schieben“ wird „verschieben“, aus „Steuer“ wird „Aussteuer“, aus „formen“ wird „umformen“. Auf der anderen Seite gibt es Suffixe wie „-ung“, „-en“ und „-ig“. Das sind wieder Affixe (Teilwörter), die man an das Ende eines Wortes hängt, um die Bedeutung und in diesem Fall auch die Wortart festzulegen. „Richtung“, „richten“ und „richtig“ sind drei völlig verschiedene Wörter, obwohl der Wortstamm sich nicht ändert. Nur die Suffixe sind unterschiedlich.

Es ist naheliegend, dass es sich beim Anfügen von Affixen um nichts weiter als eine Konkatenation handelt. Dabei ist „Aus“ ein Präfix von „Aussteuer“ und „um“ ein Präfix von „umformen“. „ung“ ist ein Suffix von „Richtung“ und „ig“ ist ein Suffix von „richtig“. „en“ ist sowohl Präfix als auch Suffix von „enthalten“. Das kommt dir vielleicht komisch vor, weil doch eigentlich „ent-“ das Präfix von „enthalten“ ist. Als Informatiker muss man sich bei der Festlegung der Affixe aber nicht unbedingt an die grammatikalischen Gegebenheiten im Deutschen halten. Man kann auch feststellen, dass „vers“ ein Präfix von „verschieben“ und „hten“ ein Suffix von „richten“ ist. Für solch eine Behauptung würde dir jeder Deutschlehrer eine Ohrfeige verpassen, aber in der Theoretischen Informatik kann man das durchgehen lassen. Und es kommt noch besser: „verschieben“ ist sowohl Suffix als auch Präfix von „verschieben“. Nein, das war jetzt kein Tippfehler. „verschieben“ beginnt mit „verschieben“ und „verschieben“ endet mit „verschieben“. Stimmt doch, oder? Wenn du diese seltsame Logik verstanden hast, kannst du weiterlesen: „“ ist sowohl Suffix als auch Präfix von „Fensterkitt“. Das Wort, das aus keinem Buchstaben besteht, $\varepsilon ,$ ist überhaupt immer Präfix und Suffix von jedem Wort. Kann man so sehen. Versuche einfach, es dir vorzustellen. „Fensterkitt“ beginnt mit keinem Buchstaben. Danach kommt nochmal kein Buchstabe. Dann erst kommt das große „F“.

Nach dem „F“ und vor dem „e“ steht kein Buchstabe. Also ist $\varepsilon$ auch tausendfach Infix von „Fensterkitt“. „pferd“ ist Infix von „Kupferdraht“ und außerdem ist „verschieben“ Infix von „verschieben“. Aber irgendwie ist es doch auch lustig, oder?

Übung

$|(\varepsilon \cdot \langle a_{1},a_{2},a_{3},a_{4},a_{5}\rangle )\cdot {\text{vier}}|={\text{?}}$

Die Lösungen stehen am Ende des Buches im Abschnitt Lösungen.

Tag 3

Zusammenfassung

Die Konkatenation, der Kleene-Stern und die Vereinigung kann auf Sprachen angewendet werden.

Lass uns kurz wiederholen: Wenn man von einer Sprache redet, meint man eine Ansammlung von Wörtern. Der Mathematiker hat für ungeordnete Ansammlungen den Begriff Menge. Wenn die Dinge geordnet sind, spricht man dagegen von einer Folge. Eine Sprache ist deshalb eine Menge von Wörtern, weil es egal ist, in welcher Reihenfolge man die Wörter aufschreibt. Die Wörter selbst sind aber keine Mengen, sondern Folgen von Buchstaben, denn es ist überhaupt nicht egal, in welcher Reihenfolge man die Buchstaben aufschreibt. (Wer jetzt an eine gewisse Studie an einer englischen Universität denkt – nein, die Reihenfolge der Buchstaben ist wirklich nicht egal.)

Außer der Tatsache, dass Folgen geordnet sind und Mengen eben nicht, gibt es noch einen weiteren Unterschied: Nur in Folgen können Glieder auch mehrfach vorkommen. Das dürfte leicht nachzuvollziehen sein: Ein Wort als Folge von Buchstaben kann natürlich einzelne Buchstaben mehrmals enthalten. Das Wort „Rentner“ zum Beispiel hat nur einen Buchstaben, der nicht zweimal darin vorkommt. Demgegenüber gibt es aber keinen Grund, weshalb eine Sprache als Menge von Wörtern ein Wort gleich zwei- oder dreimal kennen sollte. Entweder es gibt dieses Wort oder es gibt es nicht. Aus dem gleichen Grund ist übrigens ein Alphabet keine Folge, sondern eine Menge von Buchstaben: Es gibt keine Alphabete, die zweimal den gleichen Buchstaben enthalten. Und es ist auch völlig egal, in welcher Reihenfolge man die Buchstaben eines Alphabets aufschreibt, solange man keinen vergisst.

Um also den Folgen- bzw. Mengenbegriff noch einmal zusammenfassend auf einige bisher gelernte Begriffe anzuwenden:

• Ein Buchstabe ist irgendetwas, was man nicht definiert.
• Ein Alphabet ist eine Menge von Buchstaben.
• Ein Wort ist eine Folge von Buchstaben.
• Eine Sprache ist eine Menge von Wörtern.

Neben $L$ als irgendeiner Sprache hast du auch schon eine ganz bestimmte Sprache kennen gelernt: $\Sigma ^{\star }$ ist die Menge aller Wörter, die man aus dem Alphabet $\Sigma$ bilden kann. Jede Sprache $L$ über einem Alphabet $\Sigma$ ist also eine Teilmenge der Sprache $\Sigma ^{\star }.$ Sie ist maximal identisch mit $\Sigma ^{\star }.$ Aber es ist natürlich genauso möglich, dass man sich für ein Alphabet mit sechsundzwanzig Buchstaben eine Sprache ausdenkt, die nur drei Wörter kennt.

Mit Sprachen kannst du nun fast genauso rechnen wie mit Wörtern. Wenn man zum Beispiel die beiden Sprachen $L_{1}=\{{\text{Alt, Neu}}\}$ und $L_{2}=\{{\text{heit, ertum}}\}$ konkateniert, dann lautet das Ergebnis $L_{1}\cdot L_{2}=\{{\text{Altheit, Neuheit, Altertum, Neuertum}}\}.$ Es passiert hier also nichts anderes als dass alle Wörter der einen Sprache mit allen Wörtern der anderen Sprache konkateniert werden. Beachte, dass dabei wieder die Reihenfolge der Operanden entscheidend ist: $L_{1}\cdot L_{2}$ ist selten das gleiche wie $L_{2}\cdot L_{1}.$

Neben der Konkatenation kennst du eine weitere Rechenoperation: den Kleene-Stern. Wenn $\Sigma$ ein Alphabet ist, dann ist $\Sigma ^{\star }$ die Sprache mit allen aus den Buchstaben dieses Alphabets gebildeten Wörtern. Den Kleene-Stern kann man aber nicht nur auf Alphabete, sondern auch auf Sprachen anwenden. Nehmen wir für dieses Beispiel die Sprache $L=\{{\text{Alt, Neu}}\}.$ Dann ist $L^{\star }=\{\varepsilon ,{\text{Alt, Neu, AltAlt, AltNeu, NeuAlt, NeuNeu, AltAltAlt, AltAltNeu, AltNeuAlt,}}\ldots \}.$ Es handelt sich um eine unendliche Menge, die alle Wörter enthält, die man durch Konkatenation aus den Wörtern der Sprache $L$ erhalten kann und außerdem noch das leere Wort $\varepsilon .$

Der Kleene-Stern auf Sprachen angewendet funktioniert also ähnlich wie der Kleene-Stern auf Alphabete angewendet, die du ja schon kennst: Wenn $\Sigma ^{\star }$ die Menge aller Wörter ist, die man durch Konkatenation aus den Elementen von $\Sigma$ bilden kann – zuzüglich $\varepsilon$ –, dann ist $L^{\star }$ ebenso die Menge aller Wörter, die man durch Konkatenation aus den Elementen von $L$ bilden kann – zuzüglich $\varepsilon .$ Wenn $\Sigma$ ein Alphabet ist, dann ist $\Sigma ^{\star }$ eine Sprache. Wenn aber $L$ schon eine Sprache ist, dann ist $L^{\star }$ immer noch eine Sprache.

Man kann den Kleene-Stern übrigens auf die Konkatenation zurückführen: $L^{\star }$ ist die Menge aus $\varepsilon ,$ allen Elementen aus $L,$ allen Elementen aus $L\cdot L,$ allen Elementen aus $L\cdot L\cdot L,$ allen Elementen aus $L\cdot L\cdot L\cdot L$ und immer so weiter. Man kann dafür den Begriff der Vereinigung von Mengen benutzen (mathematisches Symbol: $\cup$): $L^{\star }=\{\varepsilon \}\cup L\cup L\cdot L\cup L\cdot L\cdot L\cup \dotsb$

Jetzt kennst du schon drei Operationen, die du auf Sprachen anwenden kannst: Konkatenation, Kleene-Stern und Vereinigung (denn Sprachen sind ja strenggenommen auch nur Mengen). Mithilfe dieser Rechenoperationen kannst du recht komplizierte Sprachen formal darstellen. Dazu ein Beispiel:

$L=(\{{\text{a, b}}\}^{\star }\cdot \{{\text{a}}\}\cdot \{{\text{a, b}}\})\cup \{{\text{c}}\}$
Hier wird zunächst durch Sternbildung die Sprache $\{\varepsilon ,{\text{a, b, aa, ab, ba, bb, aaa, aab,}}\ldots \}$ geschaffen. Diese Sprache und die Sprache $\{{\text{a}}\}$ werden anschließend konkateniert, was letztlich auf eine Konkatenation aller Wörter der ersten Sprache mit „a“ hinausläuft. Also enden alle Wörter mit dem Buchstaben „a“. Das Ergebnis wird dann noch einmal mit $\{{\text{a, b}}\}$ konkateniert. Es gibt also jetzt von allen Wörtern eine Variante, die auf „a“ endet und eine, die auf „b“ endet. Aber der vorletzte Buchstabe aller Wörter ist immer noch „a“. Wir haben also bis jetzt alle mindestens zwei Buchstaben langen Wörter aus den Buchstaben „a“ und „b“ in einer Sprache zusammengefasst, deren vorletzter Buchstabe ein „a“ ist. Jetzt wird diese aber noch mit der Sprache $\{{\text{c}}\}$ vereinigt. Das Ergebnis lautet also:
$L=\{{\text{c, aa, ab, aaa, aab, baa, bab, aaaa, aaab, abaa, abab, baaa, baab, bbaa, bbab, aaaaa, aaaab, aabaa, aabab,}}\ldots \}$
Die Definition $L=(\{{\text{a, b}}\}^{\star }\cdot \{{\text{a}}\}\cdot \{{\text{a, b}}\})\cup \{{\text{c}}\}$ bedeutet also, dass die Sprache $L$ aus dem Wort „c“ und allen Folgen der Buchstaben „a“ und „b“ besteht, deren vorletztes Glied ein „a“ ist. Nicht schlecht.

Übung

Wenn $L$ eine Sprache ist, welche Wörter kennt dann $L^{\star }{\text{?}}$

---

Nenne die Wörter der Sprache $L{\text{!}}$ $L=\{{\text{eklig}}\}\cup \{{\text{furcht, wunder}}\}\cdot \{{\text{bar}}\}\cup \{{\text{sagen, lach, Untersuchungs}}\}\cdot \{{\text{haft}}\}\cup \{{\text{klein, hoef, haess, mensch}}\}\cdot \{{\text{lich}}\}\cup \{{\text{Energie, Wasser}}\}\cdot \{{\text{einspar, verschwend, versorg}}\}\cdot \{{\text{ung}}\}$

---

Beschreibe die Sprache $L$ formal! $L=\{\varepsilon ,{\text{a, b, aa, ba, bb, aaa, baa, bba, bbb, aaaa, baaa, bbaa, bbba, bbbb, aaaaa,}}\ldots \}$

Die Lösungen stehen am Ende des Buches im Abschnitt Lösungen.

Tag 4

Zusammenfassung

Alphabete, Sprachen, Wörter und Buchstaben können potenziert werden. Der Kleene-Stern kann auf die Potenzierung zurückgeführt werden.

Du hast den Punktoperator (Konkatenation) kennen gelernt. Diese Operation kann man vielseitig einsetzen:

• Auf Buchstaben eines Alphabetes angewendet kann man damit Wörter bilden: $a_{1}\cdot a_{2}=\langle a_{1},a_{2}\rangle$
• Auf Wörter angewendet kann man längere Wörter bilden: $\langle a_{1},a_{2},a_{3},a_{4}\rangle \cdot \langle a_{5},a_{6}\rangle =\langle a_{1},a_{2},a_{3},a_{4},a_{5},a_{6}\rangle$
• Auf Sprachen angewendet kann man alle Wörter verlängern: $\{\langle a_{1},a_{2},a_{3}\rangle ,\langle a_{4},a_{5}\rangle \}\cdot \{\langle a_{6}\rangle ,\langle a_{7},a_{8}\rangle \}=$$\{\langle a_{1},a_{2},a_{3},a_{6}\rangle ,\langle a_{4},a_{5},a_{6}\rangle ,\langle a_{1},a_{2},a_{3},a_{7},a_{8}\rangle ,\langle a_{4},a_{5},a_{7},a_{8}\rangle \}$

Möglicherweise erinnert dich die Konkatenation an die Multiplikation von Zahlen, vor allem wegen der Schreibweise mit dem mittigen Punkt. Diese Verbindung ist gar nicht so falsch. Genauso wie man die mehrfache Multiplikation einer Zahl mit sich selbst einfacher als Potenz darstellen kann $(2\cdot 2\cdot 2=2^{3}),$ gibt es die Potenzierung auch als Zusammenfassung mehrerer Konkatenationen von Mengen und Folgen: $a\cdot a\cdot a=a^{3},L\cdot L\cdot L=L^{3}$ und auch $\Sigma \cdot \Sigma \cdot \Sigma =\Sigma ^{3}.$ Besonders das letzte Beispiel ist interessant. Die Konkatenation von Alphabeten müsste dir eigentlich neu vorkommen, weil sie noch nie vorher in diesem Kurs erwähnt wurde. Andererseits ist sie aber auch nichts außergewöhnliches. $\Sigma \cdot \Sigma$ ist einfach die Konkatenation von je zwei Buchstaben. Das Ergebnis ist die Sprache, die alle zweibuchstabigen Wörter über $\Sigma$ enthält. Für das binäre Alphabet $\Sigma _{\text{b}}=\{0,1\}$ ist das $L=\Sigma _{b}^{2}=\{00,01,10,11\}.$

Lass uns noch ein wenig mit den Potenzen herumspielen: $x^{1}$ ist in der Mathematik definiert als $x.$ Also mit 1 kann man immer potenzieren, ohne dass sich an der Zahl etwas ändert. Diese Regel kann man ohne Abstriche in die Theoretische Informatik übernehmen: $\Sigma ^{1}=\Sigma$ und $L^{1}=L.$

Neben der Potenzierung mit 1 gibt es noch einen weiteren Sonderfall: den der Potenzierung mit 0. $x^{0}=1$ steht in jedem Mathebuch. Jede Potenzierung mit 0 ergibt 1, weil 1 das neutrale Element der Multiplikation ist. Wenn man diese Regel auf die Theorie der formalen Sprachen überträgt, lautet sie: Jede Potenzierung mit 0 ergibt $\{\varepsilon \}$ (eine Menge, deren einziges Element $\varepsilon$ ist), weil $\{\varepsilon \}$ das neutrale Element der Konkatenation von Mengen ist. $\Sigma \cdot \{\varepsilon \}=\Sigma ,L\cdot \{\varepsilon \}=L.$

Um das kurz zusammenzufassen: $\Sigma ^{0}$ ist $\{\varepsilon \},$ $\Sigma ^{1}$ ist $\Sigma$, also einfach die Menge aller Buchstaben oder anders ausgedrückt: die Menge aller Wörter der Länge 1, $\Sigma ^{2}$ ist die Menge aller möglichen Konkatenationen von je zwei Buchstaben, also die Menge aller Wörter der Länge 2, $\Sigma ^{x}$ ist die Menge aller Wörter der Länge $x.$ Fällt nicht eine gewisse Ähnlichkeit zum Kleene-Stern auf? Wenn man alle Wörter der Länge 0, alle Wörter der Länge 1, alle Wörter der Länge 2 und so weiter zusammenfasst, also $\Sigma ^{0}\cup \Sigma ^{1}\cup \Sigma ^{2}\cup \dotsb ,$ dann erhält man einfach alle Wörter, also $\Sigma ^{\star }.$ Jetzt dürfte dir klar sein, weshalb der Kleene-Stern ausgerechnet ein hochgestellter Stern ist. Der Stern ist ein Platzhalter für alle möglichen Exponenten von 0 bis ∞.

Übung

Definiere eine Sprache $L$ über dem Alphabet $\Sigma =\{a,b,c\}$ mit der folgenden Eigenschaft: Alle Wörter beginnen mit vier „a“, enden mit vier „a“ und enthalten mindestens zwei „b“.

Die Lösungen stehen am Ende des Buches im Abschnitt Lösungen.

Tag 5

Zusammenfassung

Die Potenzierung und der Kleene-Stern, die Konkatenation und die Vereinigung haben in dieser Reihenfolge absteigende Priorität. Der Betragsoperator kann auch auf Mengen angewendet werden und bestimmt deren Mächtigkeit.

Das ist der letzte Tag in dieser Wochenlektion und er soll nun genutzt werden, das bisher Gelernte zu systematisieren. Folgende Rechenoperationen sind bekannt:

• Vereinigung $\cup .$ Die Vereinigung kann nur auf Mengen, nicht auf Folgen angewendet werden. Mengen sind Alphabete und Sprachen. Die Vereinigung zweier Mengen enthält alle Elemente der einen sowie alle Elemente der anderen Menge. Das neutrale Element der Vereinigung ist die leere Menge { }. Die Vereinigung einer Menge mit der leeren Menge hat keinen Effekt.
• Konkatenation $\cdot .$ Wird die Konkatenation auf Buchstaben und Wörter angewendet, werden die Operanden in der gegebenen Reihenfolge aneinander gehängt. Dabei entstehen immer Wörter, da auch Buchstaben streng genommen nichts als Wörter der Länge eins sind. Das neutrale Element bei der Konkatenation von Wörtern ist das leere Wort $\varepsilon .$ Wird diese Operation dagegen auf Alphabete und Sprachen, also Mengen, angewendet, werden die Elemente der Mengen paarweise aneinandergehängt. Das neutrale Element ist hierbei die Menge mit keinen weiteren Elementen außer dem leeren Wort: $\{\varepsilon \}.$ Außerdem gibt es den Sonderfall der Konkatenation mit der leeren Menge $\{\}:\Sigma \cdot \{\}=\{\}.$
• Potenzierung $X^{y}.$ Die mehrfache Konkatenation von Mengen kann zu einer Potenzierung zusammengefasst werden: $L\cdot L=L^{2}.$ Das neutrale Element der Potenzierung ist die 1. Die Potenzierung mit 0 ergibt $\{\varepsilon \}.$ Die Potenzierung kann nicht auf Folgen angewendet werden.
• Kleene-Stern $X^{\star }.$ Der Kleene-Stern ist die Vereinigung aller Potenzierungen. $\Sigma ^{\star }=\{\varepsilon \}\cup \Sigma \cup \Sigma \cdot \Sigma \cup \Sigma \cdot \Sigma \cdot \Sigma \cup \dotsb =\Sigma ^{0}\cup \Sigma ^{1}\cup \Sigma ^{2}\cup \Sigma ^{3}\cup \dotsb$

Dabei lässt sich die Vereinigung mit der Addition, die Konkatenation mit der Multiplikation und die Potenzierung und der Kleene-Stern mit der klassischen Potenzierung vergleichen, zumindest hinsichtlich ihrer Wertigkeit. Die Gleichung $L=(L_{1}\cdot (L_{2}^{\star }))\cup (L_{1}^{3})$ kommt auch völlig ohne Klammern aus: $L=L_{1}\cdot L_{2}^{\star }\cup L_{1}^{3}.$

Bei der Nennung der Operatoren fiel bislang oft einer unter den Tisch, der tatsächlich eine Sonderstellung einnimmt: Der Betragsoperator, mit dem man unter anderem die Länge eines Wortes bestimmt. Wenn irgendwo steht $|w|=12,$ dann weißt du, dass das Wort $w$ aus zwölf Buchstaben besteht. Was du bis jetzt noch nicht weißt, aber gleich erfahren wirst, ist, dass man den Betragsoperator auch auf Mengen anwenden kann. Man bestimmt dann, aus wie vielen Elementen die Menge besteht oder, etwas elaborierter ausgedrückt, wie mächtig die Menge ist. $|\Sigma |=26$ heißt, dass das Alphabet 26 Buchstaben hat und $|L|=2\cdot |\Sigma |$ heißt, dass die Sprache doppelt so viele Wörter wie das Alphabet Buchstaben hat.

So viel zum Thema Sprachen allgemein. Beschäftige dich bitte morgen, wenn nicht morgen und übermorgen, noch mit dieser Wochenlektion und dem dazugehörigen Rückblick bevor du mit der neuen Wochenlektion anfängst. Es heißt, man muss eine Sache elfmal gehört haben, damit man sie nicht mehr vergisst. Es klingt vielleicht paradox, aber wenn du schnell vorankommen willst, musst du dein Tempo drosseln.

Rückblick

Diese Rückblick-Abschnitte sollen dir nicht nur helfen, dein erworbenes Wissen zu festigen, sondern sie sollen dir auch die Möglichkeit geben, zu testen, wie souverän du bereits entsprechende Fragestellungen lösen kannst. Es handelt sich hierbei um eine Ansammlung von Übungen. Versuche zuerst, die Aufgaben selbst zu lösen bevor du dir die Lösungen ansiehst.

Übung

Ordne den Begriffen „Wort“, „Alphabet“ und „Sprache“ die Begriffe „Folge“ und „Menge“ zu! Welche Rolle nimmt der „Buchstabe“ ein?

---

Was ist die Länge eines Wortes, wie bestimmt man sie und wie nennt man das Wort mit der Länge 0?

---

Der Kleene-Stern kann auf die Potenzierung zurückgeführt werden. Wie ist das zu verstehen?

---

$\Sigma ^{\star }=\{\varepsilon ,a,b,c,d,aa,ab,ac,ad,ba,\ldots ,dcabad,\ldots \}$

$L^{\star }=\{\varepsilon ,aaa,bbb,ccc,ddd,aaaaaa,aaabbb,aaaccc,aaaddd,bbbaaa,\ldots ,dddcccaaabbbaaaddd,\ldots \}$

$a^{\star }=\{a\}^{\star }=\{\varepsilon ,a,aa,aaa,aaaa,\ldots \}$

---

Entwirf eine Sprache über dem Alphabet $\Sigma =\{a,b,c,d,e\},$ deren Wörter drei oder fünf Buchstaben lang sind und als mittleren Buchstaben ein c haben!

Die Lösungen stehen am Ende des Buches im Abschnitt Lösungen.

Lösungen

Die folgende Darstellung der Lösungen funktioniert nicht solange der seit 19 Jahren bekannte Bug 2257 nicht behoben ist. Bitte verzichte in der Zwischenzeit auf diese Druckversion.