Aufgaben zu Grammatiken
Wie gut kennst du dich mit formalen Sprachen aus? Teste dein Wissen mit diesen Übungsaufgaben!
- 1
Bilde die Verkettung der beiden folgenden Sprachen und .
= {Verstetigungs, Überhöhungs}
= {option, paradigma}
Gib immer nur ein mögliches Wort der Sprache in das Textfeld ein und überprüfe es. Findest du alle ?
- 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).
- 3
Turingmaschine für
Überlege dir, wie du mit einer Turingmaschine die Sprache 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 über dem Alphabet ist regulär. Es ist sehr einfach, für diese Sprache einen regulären Ausdruck anzugeben, nämlich .
Auch die Sprache 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 einer Sprache zu finden:
Du erzeugst aus dem regulären Ausdruck für einen nichtdeterministischen endlichen Automaten, der 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 erkennt
Du erzeugst aus diesem Automaten den gesuchten regulären Ausdruck für
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 zu finden.
Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0 → Was bedeutet das?