Blitzkurs Theoretische Informatik/ 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.$“

Der Satz „Ein $L$ ist eine geordnete Folge von $\Sigma .$“ ist falsch. Diese Aussage bedeutet, dass eine Sprache eine Aneinanderreihung von Alphabeten wäre. Das ist natürlich Quatsch. Eine Sprache $L$ definiert sich durch die Wörter, die zu ihr gehören. Anders ausgedrückt: „Ein $L$ ist eine Menge von $w.$“

---

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

„“, „0“, „1“, „00“, „01“, „10“, „11“, „000“, „001“, …

---

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“

„verlängern“ gehört nicht dazu, denn es enthält mit „ä“ einen Buchstaben, den das Alphabet nicht kennt.

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 Klammern sind überflüssig. Wenn man ein Wort mit null Buchstaben $(\varepsilon ),$ ein Wort mit fünf Buchstaben $(\langle a_{1},a_{2},a_{3},a_{4},a_{5}\rangle )$ und ein Wort mit vier Buchstaben $({\text{vier}})$ konkateniert $(\cdot ),$ dann beläuft sich die Länge $(||)$ des Ergebnisses auf neun Buchstaben.
$|\varepsilon \cdot \langle a_{1},a_{2},a_{3},a_{4},a_{5}\rangle \cdot {\text{vier}}|=9$

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{?}}$

$\varepsilon ,$ alle Wörter aus $L$ sowie alle möglichen Konkatenationen von Wörtern aus $L.$

---

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}}\}$

eklig, furchtbar, wunderbar, sagenhaft, lachhaft, Untersuchungshaft, kleinlich, hoeflich, haesslich, menschlich, Energieeinsparung, Energieverschwendung, Energieversorgung, Wassereinsparung, Wasserverschwendung, Wasserversorgung

---

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

$L=\{b\}^{\star }\cdot \{a\}^{\star }$

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“.

$L=\{a\}^{4}\cdot \Sigma ^{\star }\cdot \{b\}\cdot \Sigma ^{\star }\cdot \{b\}\cdot \Sigma ^{\star }\cdot \{a\}^{4}$ oder
$L=\{a^{4}\}\cdot \Sigma ^{\star }\cdot \{b\}\cdot \Sigma ^{\star }\cdot \{b\}\cdot \Sigma ^{\star }\cdot \{a^{4}\}$

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?

• Wort: Folge von Buchstaben
• Alphabet: Menge von Buchstaben
• Sprache: Menge von Wörtern

Eine elegante Definition für „Buchstabe“ lautet: „Ein Buchstabe ist ein Wort der Länge 1.“ Da ein Wort eine Folge von Buchstaben ist, hat man damit den Buchstaben mit sich selbst definiert. Genauer kann man es leider nicht ausdrücken. Man müsste sagen: Der Buchstabe ist.

---

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

Da ein Wort eine endliche Folge von Buchstaben ist, ist die Länge eines Wortes die Anzahl der Buchstaben. Dabei müssen nicht alle Buchstaben verschieden voneinander sein. Die Länge eines Wortes $w$ stellt man mit Betragsstrichen dar: $|w|=n.$ Das Nullwort heißt $\varepsilon$ (Epsilon): $|\varepsilon |=0.$

---

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

Das Ergebnis des Kleene-Stern-Operators ist die Vereinigungsmenge aller Potenzen: $\Sigma ^{\star }=\Sigma ^{0}\cup \Sigma ^{1}\cup \Sigma ^{2}\cup \dotsb$

---

$\Sigma =\{{\text{a, b, c, d}}\}$ ist ein Alphabet. $L=\{{\text{aaa, bbb, ccc, ddd}}\}$ ist eine Sprache über $\Sigma .$ Berechne $\Sigma ^{\star },L^{\star }$ und $a^{\star }{\text{!}}$

$\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!

$L=\Sigma ^{2}\cdot \{c\}\cdot \Sigma ^{2}\cup \Sigma \cdot \{c\}\cdot \Sigma$