s n h m r u
i

Übungen

Die folgenden sieben Übungen vertiefen die Zusammenhänge zwischen regulären Grammatiken, endlichen Automaten und regulären Ausdrücken.

Übung 1: Vom DEA zur regulären Grammatik

Gegeben ist ein DEA über dem Alphabet {0, 1}. S ist der Startzustand und B der einzige Endzustand.

Zustand Eingabe 0 Eingabe 1
S A S
A A B
B A S
  1. Zeichne das Übergangsdiagramm und untersuche die Wörter 01, 101, 010, 001 und ε, ob sie zur Sprache des DEA gehören.





  2. Erzeuge von Hand eine reguläre Grammatik mit dem Startsymbol S, die dieselbe Sprache beschreibt. Erläutere, wie die Übergänge und der Endzustand in den Produktionen wiederzufinden sind.
  3. Gib eine Ableitung des Wortes 001 an und vergleiche sie mit dem Weg durch den DEA.
  4. Beschreibe die Sprache in Worten.
  5. Gib einen regulären Ausdruck für diese Sprache an.

Übung 2: Reguläre Produktionen erkennen und ergänzen

Betrachte die folgende Grammatik über {a, b} mit dem Startsymbol S:

S -> aS
S -> bA
A -> aA
A -> bA
A -> ε
  1. Begründe, warum die dadurch erzeugte Sprache regulär ist.
  2. Notiere drei Wörter der erzeugten Sprache und drei Wörter über dem Alphabet, die nicht dazugehören.

    Für das leere Wort kannst du e oder ε eingeben.

    Wörter der Sprache:

    1.
    2.
    3.

    Wörter außerhalb der Sprache:

    1.
    2.
    3.

  3. Beschreibe die Sprache so genau wie möglich.
  4. Gib einen regulären Ausdruck für diese Sprache an.

  5. Die Produktion S -> aSb wird hinzugefügt. Ist die erweiterte Grammatik regulär? Kannst du allein daraus schließen, dass ihre Sprache nicht regulär ist? Begründe und vergleiche die erzeugte Sprache mit der ursprünglichen Sprache.
Übung 3: Verschiedene Wege durch einen NEA

Der folgende NEA hat den Startzustand S und den einzigen Endzustand F. Ein Strich bedeutet, dass kein Übergang vorhanden ist. Mehrere Einträge in einer Zelle bezeichnen verschiedene mögliche Folgezustände.

Zustand Eingabe 0 Eingabe 1 ε-Übergang
S S, A S –
A – B –
B – – F
F – – –
  1. Zeichne das Übergangsdiagramm. Markiere die Stellen, an denen Nichtdeterminismus auftritt.
  2. Untersuche alle möglichen Wege für 01. Notiere zu jedem Weg den jeweils noch nicht gelesenen Teil des Wortes.
  3. Überprüfe, ob 101, 010, 001 und ε zu der von diesem NEA erkannten Sprache gehören. Begründe jeweils die Annahme oder Ablehnung.




  4. Erkläre am Wort 010, warum das Erreichen eines Endzustands allein noch nicht zur Annahme des Wortes genügt.
  5. Beschreibe die Sprache des NEA in Worten.
  6. Gib einen regulären Ausdruck für diese Sprache an.

Übung 4: Von der Grammatik über den NEA zum DEA

Gegeben ist die reguläre Grammatik mit dem Startsymbol S:

S -> 0S
S -> 1S
S -> 1A
A -> 0
  1. Konstruiere einen NEA zur Grammatik. Verwende für die Produktion A -> 0 einen zusätzlichen Endzustand.
  2. Bestimme nach dem Lesen von 1, 10 und 101 jeweils alle gleichzeitig möglichen Zustände des NEA.
  3. Konstruiere einen gleichwertigen DEA. Fasse dazu die jeweils möglichen NEA-Zustände zu einem DEA-Zustand zusammen. Kennzeichne Start- und Endzustände und ergänze alle Übergänge für 0 und 1.
  4. Teste NEA und DEA mit 10, 110, 101, 0 und ε. Vergleiche anschließend deine Umwandlung mit einer automatisierten Umwandlung.





  5. Gib einen regulären Ausdruck für die gemeinsame Sprache an.

Übung 5: Wahr oder falsch?

Entscheide für jede Aussage, ob sie wahr oder falsch ist. Begründe deine Entscheidung; korrigiere falsche Aussagen.

  1. "Ein NEA ist mächtiger als ein DEA, weil er mehrere mögliche Wege für ein Wort besitzt."

  2. "Wenn ein Weg durch einen NEA scheitert, wird das Wort abgelehnt."

  3. "Wenn ein DEA-Startzustand zugleich Endzustand ist, muss die zugehörige Sprache das leere Wort enthalten."

  4. "Wenn eine Grammatik nicht regulär ist, kann ihre Sprache durch keinen DEA erkannt werden."

  5. "Zu jeder regulären Grammatik gibt es einen regulären Ausdruck für dieselbe Sprache."

  6. "Zwei Automaten mit unterschiedlich vielen Zuständen erkennen immer unterschiedliche Sprachen."

Übung 6: Einen regulären Ausdruck überprüfen und korrigieren

Gesucht ist die Sprache aller Wörter über {0, 1}, in denen niemals zwei 1 unmittelbar aufeinanderfolgen. Das leere Wort gehört dazu. Als regulärer Ausdruck wird 0*1* vorgeschlagen.

  1. Beschreibe die Sprache des vorgeschlagenen Ausdrucks. Finde ein möglichst kurzes Wort, das der Ausdruck beschreibt, obwohl es die Bedingung nicht erfüllt. Finde außerdem ein möglichst kurzes Wort, das die Bedingung erfüllt, aber vom Ausdruck nicht beschrieben wird. Begründe jeweils, warum kein kürzeres Gegenbeispiel möglich ist.
  2. Konstruiere einen vollständigen DEA für die gesuchte Sprache. Überlege, welche Information über das zuletzt gelesene Zeichen gespeichert werden muss und was nach dem Lesen von 11 geschehen soll. Kennzeichne Anfangs- und Endzustände.
  3. Gib einen passenden regulären Ausdruck für die gesuchte Sprache an. Überprüfe, ob er auch das leere Wort sowie Wörter berücksichtigt, die mit 1 enden.

  4. Leite aus deinem DEA eine reguläre Grammatik ab. Gib eine Ableitung von 1010 an und zeige, an welcher Stelle ein Verarbeitungsversuch für 1011 scheitert.
  5. Jemand prüft den Ausdruck nur mit ε, 0, 1 und 01 und hält ihn danach für richtig. Erkläre, warum diese Tests den Fehler nicht aufdecken. Kann eine endliche Auswahl akzeptierter Beispielwörter allein die Gleichheit zweier Sprachen beweisen?
Übung 7: Die ipigisi-Sprachen untersuchen

Wir verwenden das Alphabet {i, s, p, g}.

  • Eine isi-Folge enthält mindestens ein i; zwischen zwei aufeinanderfolgenden i steht jeweils ein s. Beispiele sind i, isi und isisi.
  • Eine ipigisi-Folge besteht aus drei isi-Folgen, die durch p und danach g getrennt werden.

Bearbeite damit folgende Aufgaben:

  1. Zeige auf einem Weg deiner Wahl, dass die Sprache der isi-Folgen regulär ist.

  2. Die folgende Grammatik hat das Startsymbol F:
    F -> I
    F -> iSi
    S -> sIs
    I -> iSi
    I -> i
    S -> s
    

    Leite isisi ab. Untersuche, warum die Grammatik nicht regulär ist, obwohl sie dieselbe Sprache wie dein Modell aus b erzeugt. Erläutere, weshalb eine nicht reguläre Grammatik allein kein Nachweis für eine nicht reguläre Sprache ist.

  3. Entwickle ein Syntaxdiagramm für beliebige ipigisi-Folgen. Gib auch einen regulären Ausdruck an und konstruiere einen passenden endlichen Automaten oder eine reguläre Grammatik. Erkläre, welcher dieser Ansätze die Regularität nachweist.

  4. Untersuche diese Grammatik mit dem Startsymbol S:

    S -> iAi
    A -> siAis
    A -> piBis
    B -> siBis
    B -> g
    

    Prüfe die Ableitbarkeit von ipigisi, isipisigisi und isipisigisisisi. Gib für ableitbare Wörter eine vollständige Ableitung an. Beschreibe die erzeugte Sprache und untersuche, wie die Produktionen die Anzahl der i auf beiden Seiten von g beeinflussen. Handelt es sich um eine reguläre Grammatik?

  5. Deutet man die Anzahl der i einer isi-Folge als Zahl, p als Pluszeichen und g als Gleichheitszeichen, erhält man eine Additionsaussage. Ein ipigisi-Ausdruck soll mathematisch korrekt heißen, wenn die beiden Zahlen links von g zusammen die Zahl rechts davon ergeben.

    Übersetze ipigi, ipigisi, isipisigisi und isipisigisisisi in Additionsaussagen. Unterscheide dabei zwischen einer gültigen ipigisi-Folge und einer richtigen Rechnung. Begründe, weshalb die Bedeutung der Zeichen zusätzlich zu den Bildungsregeln vereinbart werden muss.
  6. Kann ein endlicher Automat alle mathematisch korrekten ipigisi-Ausdrücke erkennen? Begründe.

  7. Diskutiere, ob ein Syntaxdiagramm für beliebige ipigisi-Folgen auch die mathematische Korrektheit prüft.

Suche

v
100.130.2.3.2.5 Übungen
Kopieren durch Anklicken

Rückmeldung geben