Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Aufgaben zu Grammatiken

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

  1. 1

    Bilde die Verkettung L0L1L_0L_1 der beiden folgenden Sprachen L0L_0​ und L1L_1.

    L0L_0​ = {Verstetigungs, Überhöhungs}

    L1L_1​ = {option, paradigma}

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


  2. 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. 3

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

    Überlege dir, wie du mit einer Turingmaschine die Sprache L={anbn  nN}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. 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. 5

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

    Auch die Sprache Lˉ={alle Wo¨rter, die nicht auf bb enden}\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 Lˉ\bar L einer Sprache L L zu finden:

    1. Du erzeugst aus dem regulären Ausdruck für LL einen nichtdeterministischen endlichen Automaten, der LL 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 Lˉ\bar L erkennt

    4. Du erzeugst aus diesem Automaten den gesuchten regulären Ausdruck für Lˉ\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 Lˉ\bar L zu finden.


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