Aufgaben zu Grammatiken

Wie gut kennst du dich mit formalen Sprachen aus? Teste dein Wissen mit diesen Übungsaufgaben!

1
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 ?
Die vier gültigen Wörter der Sprache $L_0L_1$ sind:
Verstetigungsoption
Überhöhungsoption
Verstetigungsparadigma
Überhöhungsparadigma
keine gültigen Wörter ergeben sich, wenn du...
...zuerst ein Wort aus $L_1$ , dann aus $L_0$ verwendest, denn das wäre die Sprache $L_1L_0$ (also z.B. optionVerstetigungs).
...von einer der beiden Sprachen mehr als ein Wort verwendest (z.B. VerstetigungsÜberhöhungsoption)
...zusätzliche Symbole oder Wörter einfügst, die nicht in $L_0$ oder in $L_1$ liegen (z.B. Verstetigungs-option oder Verstetigungsparadigmaverkäufer)
Die Wörter werden dadurch gebildet, dass du genau ein Wort aus der ersten Sprache nimmst und genau eines aus der zweiten hintendran hängst. Dabei ist die Reihenfolge wichtig!
2
Ü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).

Die Übergangsrelation der Turingmaschine entspricht genau der Übergangsrelation der endlichen Automaten, außer dass als Cursoraktion noch jeweils ein $R$ hinzukommt und außer dass noch ein zusätzliches Tupel hinzukommt, um nach Erreichen des Zustands 2 sicherzustellen, dass das Eingabewort zu Ende ist.
3
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!
4
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!
5
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:
Du erzeugst aus dem regulären Ausdruck für $L$ einen nichtdeterministischen endlichen Automaten, der $L$ erkennt
Du formst diesen Automaten mittels der Teilmengenkonstruktion in einen deterministischen endlichen Automaten um
Du wandelst in diesem Automaten alle Endzustände in Nicht-Endzustände um und umgekehrt, sodass der Automat nunmehr $\bar L$ erkennt
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.

Für diese Aufgabe benötigst Du folgendes Grundwissen: Reguläre Ausdrücke und endliche Automaten
Der folgende nichtdeterministische endliche Automat erkennt die Sprache $L$ aller Wörter, die auf bb enden.
Mithilfe der Teilmengenkonstruktion erzeugst du den folgenden deterministischen endlichen Automaten, der dieselbe Sprache erkennt.
Du wandelst nun alle Endzustände des Automaten in Nicht-Endzustände um und umgekehrt.
Aus diesem Automaten leitest du den entsprechenden regulären Ausdruck ab. Du wendest entweder das entsprechende Konstruktionsverfahren an oder du erkennst durch scharfes Hinsehen, dass es ausgehend vom Startzustand drei Schleifen gibt: $\text a$ , $\text{ba}$ und $\text{bbb}^*\text a$ . Der Startzustand ist auch gleichzeitig ein Endzustand. Zusätzlich ist es möglich mit $\text b$ zum zweiten Endzustand zu gelangen.
Der entsprechende reguläre Ausdruck lautet also
$(\text a ~|~ \text{ba} ~|~ \text{bbb}^*\text a)^* ~\text b^?$
Hierbei ist $\text b^?$ eine Abkürzung für den Ausdruck $\varepsilon ~|~ \text b$ .
Du kannst diesen regulären Ausdruck noch vereinfachen. In der Klammer steht: 0 $\text b$ 's gefolgt von $\text a$ oder 1 $\text b$ gefolgt von $\text a$ oder 2 oder mehr $\text b$ 's gefolgt von $\text a$ , also zusammengenommen 0 oder mehr $\text b$ 's gefolgt von $\text a$ . Damit vereinfachst du den regulären Ausdruck zu
$(\text b^* \text a)^* ~\text b^?$
Du gehst so vor, wie in der Aufgabenstellung angegeben.

Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0 → Was bedeutet das?

Aufgaben zu Grammatiken

Systematisches Vorgehen