Übungen
Die folgenden sieben Übungen vertiefen die Zusammenhänge zwischen regulären Grammatiken, endlichen Automaten und regulären Ausdrücken.
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 |
- Zeichne das Übergangsdiagramm und untersuche die Wörter
01,101,010,001undε, ob sie zur Sprache des DEA gehören. - 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. - Gib eine Ableitung des Wortes
001an und vergleiche sie mit dem Weg durch den DEA. - Beschreibe die Sprache in Worten.
- Gib einen regulären Ausdruck für diese Sprache an.
Betrachte die folgende Grammatik über {a, b} mit dem Startsymbol S:
S -> aS S -> bA A -> aA A -> bA A -> ε
- Begründe, warum die dadurch erzeugte Sprache regulär ist.
- 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
eoderεeingeben. - Beschreibe die Sprache so genau wie möglich.
- Gib einen regulären Ausdruck für diese Sprache an.
- Die Produktion
S -> aSbwird 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.
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 | – | – | – |
- Zeichne das Übergangsdiagramm. Markiere die Stellen, an denen Nichtdeterminismus auftritt.
- Untersuche alle möglichen Wege für
01. Notiere zu jedem Weg den jeweils noch nicht gelesenen Teil des Wortes. - Überprüfe, ob
101,010,001undεzu der von diesem NEA erkannten Sprache gehören. Begründe jeweils die Annahme oder Ablehnung. - Erkläre am Wort
010, warum das Erreichen eines Endzustands allein noch nicht zur Annahme des Wortes genügt. - Beschreibe die Sprache des NEA in Worten.
- Gib einen regulären Ausdruck für diese Sprache an.
Gegeben ist die reguläre Grammatik mit dem Startsymbol S:
S -> 0S S -> 1S S -> 1A A -> 0
- Konstruiere einen NEA zur Grammatik. Verwende für die Produktion
A -> 0einen zusätzlichen Endzustand. - Bestimme nach dem Lesen von
1,10und101jeweils alle gleichzeitig möglichen Zustände des NEA. - 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
0und1. - Teste NEA und DEA mit
10,110,101,0undε. Vergleiche anschließend deine Umwandlung mit einer automatisierten Umwandlung. - Gib einen regulären Ausdruck für die gemeinsame Sprache an.
Entscheide für jede Aussage, ob sie wahr oder falsch ist. Begründe deine Entscheidung; korrigiere falsche Aussagen.
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.
- 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.
- 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
11geschehen soll. Kennzeichne Anfangs- und Endzustände. - 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
1enden. - Leite aus deinem DEA eine reguläre Grammatik ab. Gib eine Ableitung von
1010an und zeige, an welcher Stelle ein Verarbeitungsversuch für1011scheitert. - Jemand prüft den Ausdruck nur mit
ε,0,1und01und 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?
Wir verwenden das Alphabet {i, s, p, g}.
- Eine isi-Folge enthält mindestens ein
i; zwischen zwei aufeinanderfolgendenisteht jeweils eins. Beispiele sindi,isiundisisi. - Eine ipigisi-Folge besteht aus drei isi-Folgen, die durch
pund danachggetrennt werden.
Bearbeite damit folgende Aufgaben:
-
Zeige auf einem Weg deiner Wahl, dass die Sprache der isi-Folgen regulär ist.
- Die folgende Grammatik hat das Startsymbol
F:F -> I F -> iSi S -> sIs I -> iSi I -> i S -> s
Leite
isisiab. 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. -
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.
-
Untersuche diese Grammatik mit dem Startsymbol
S:S -> iAi A -> siAis A -> piBis B -> siBis B -> g
Prüfe die Ableitbarkeit von
ipigisi,isipisigisiundisipisigisisisi. Gib für ableitbare Wörter eine vollständige Ableitung an. Beschreibe die erzeugte Sprache und untersuche, wie die Produktionen die Anzahl deriauf beiden Seiten vongbeeinflussen. Handelt es sich um eine reguläre Grammatik? -
Deutet man die Anzahl der
Übersetzeieiner isi-Folge als Zahl,pals Pluszeichen undgals Gleichheitszeichen, erhält man eine Additionsaussage. Ein ipigisi-Ausdruck soll mathematisch korrekt heißen, wenn die beiden Zahlen links vongzusammen die Zahl rechts davon ergeben.ipigi,ipigisi,isipisigisiundisipisigisisisiin 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. Kann ein endlicher Automat alle mathematisch korrekten ipigisi-Ausdrücke erkennen? Begründe.
Diskutiere, ob ein Syntaxdiagramm für beliebige ipigisi-Folgen auch die mathematische Korrektheit prüft.