Aufgaben zu Grammatiken

Bilde die Verkettung $L_0L_1$ der beiden folgenden Sprachen $L_0​$ und $L_1$.

$L_0$​ = {Verstetigungs, Überhöhungs}

$L_1$​ = {option, paradigma}

Gib immer nur ein mögliches Wort der Sprache in das Textfeld ein und überprüfe es. Findest du alle ?

Überlege dir, wie du den nichtdeterministischen endlichen Automaten aus dem Beispiel auf der Seite Endlicher Automat in eine nichtdeterministische Turingmaschine überführen kannst. Schau dir die Übergangsrelation des endlichen Automaten an und konstruiere daraus die Übergangsrelation der nichtdeterministischen Turingmaschine. Du brauchst noch ein zusätzliches Tupel, um sicherzustellen, dass die Turingmaschine das Eingabewort zu Ende gelesen hat (wie in dem Beispiel oben).

Turingmaschine für $\text{a}^n\text{b}^n$

Überlege dir, wie du mit einer Turingmaschine die Sprache $L = \{\text{a}^n\text{b}^n ~|~ n \in \N\}$ erkennst. Erstelle auf der Webseite http://hwlang.de/theor/turing-simulation-anbn.htm eine entsprechende Turingtabelle. Anschließend kannst du deine Turingmaschine dort ausprobieren!

Mit Turingmaschine addieren

Du kannst mit einer Turingmaschine auch Berechnungen anstellen, zum Beispiel zwei Zahlen addieren. Auf der Webseite hwlang.de/theor/turing-simulation-add.htm findest du hierzu die Aufgabe und eine Anleitung dazu, wie du eine entsprechende Turingmaschine entwirfst. Du kannst deine Turingmaschine dort auch ausprobieren!

Die Sprache $L = \{\text{alle Wörter, die auf bb enden}\}$ über dem Alphabet $A = \{\text a,\text b\}$ ist regulär. Es ist sehr einfach, für diese Sprache einen regulären Ausdruck anzugeben, nämlich $(\text a|\text b)^*\text{bb}$.

Auch die Sprache $\bar L = \{\text{alle Wörter, die {\it nicht} auf bb enden}\}$ ist regulär, denn das Komplement einer regulären Sprache ist ebenfalls regulär. Aber für diese Sprache ist es nicht so einfach, einen regulären Ausdruck anzugeben.

Systematisches Vorgehen

Du kannst folgende systematische Methode anwenden, um einen regulären Ausdruck für das Komplement $\bar L$ einer Sprache $L$ zu finden:

1. Du erzeugst aus dem regulären Ausdruck für $L$ einen nichtdeterministischen endlichen Automaten, der $L$ erkennt

2. Du formst diesen Automaten mittels der Teilmengenkonstruktion in einen deterministischen endlichen Automaten um

3. Du wandelst in diesem Automaten alle Endzustände in Nicht-Endzustände um und umgekehrt, sodass der Automat nunmehr $\bar L$ erkennt

4. Du erzeugst aus diesem Automaten den gesuchten regulären Ausdruck für $\bar L$

Bei einem solchen systematischen Vorgehen hast du automatisch die Gewähr dafür, dass du ein korrektes Ergebnis erzielst - vorausgesetzt natürlich, dass du alle Schritte richtig ausführst.

Versuche einmal, diese Methode anzuwenden und einen regulären Ausdruck für die oben genannte Sprache $\bar L$ zu finden.