s n h m r u
i

Übungen

Klicke auf eine Aufgabenüberschrift, um die Aufgabe zu öffnen!

Aufgabe 1 – Modifikation eines Kellerautomaten

Die Sprache der verallgemeinerten Klammerausdrücke entsteht, wenn man in einem korrekt geklammerten Rechenausdruck alle Zahlen und Rechenzeichen weglässt:

Rechenausdruck Klammerausdruck Darstellung mit a und b
(57+18) () ab
(7+4)*(3-1) ()() abab
((2+6)+5)*(7+4) (())() aabbab
(((2+6)+5)*(7+4))*((4-2)) ((())())(()) aaabbabbaabb

Ändere den unten geladenen Kellerautomaten „EinfacheKlammersprache“ so ab, dass er diese Sprache erkennt. Teste deinen Kellerautomaten ausführlich.

Im folgenden Tool ist der Ausgangsautomat zum Bearbeiten geladen.

Aufgabe 2 – Analyse der Sprache eines Kellerautomaten
  1. Finde vier Wörter, die der folgende Kellerautomat nicht erkennt, und vier Wörter, die er erkennt.

    Trage deine Wörter ein und klicke auf Überprüfen. Verwende nur a und b; für das leere Wort gib ε ein.

    Gehört nicht zur SpracheGehört zur Sprache








  2. Beschreibe die Sprache des Kellerautomaten so genau wie möglich.
Aufgabe 3 – ipigisi-Sprache: Grammatik und Kellerautomat vergleichen

Werde ich noch anpassen, könnte aber als Follow-Up zur entsprechenden Übung im Regulären-Sprachen-Kapitel gut passen

In Aufgabe 7 der Übungen zu endlichen Automaten hast du die ipigisi-Sprachen untersucht. Nun vergleichst du eine kontextfreie Grammatik und einen Kellerautomaten für mathematisch korrekte ipigisi-Ausdrücke.

Das Alphabet ist {i, s, p, g}. Eine isi-Folge enthält mindestens ein i; zwischen zwei aufeinanderfolgenden i steht jeweils ein s. Eine ipigisi-Folge besteht aus drei isi-Folgen, getrennt durch p und danach g. Die Anzahl der i einer isi-Folge steht für eine positive ganze Zahl; p bedeutet Plus und g bedeutet Gleichheit. Ein Ausdruck ist mathematisch korrekt, wenn die beiden Zahlen links von g zusammen die Zahl rechts davon ergeben.

Gegeben ist die folgende kontextfreie Grammatik mit dem Startsymbol S und den Nichtterminalsymbolen S, A und B:

S -> iAi
A -> siAis
A -> piBis
B -> siBis
B -> g
  1. Untersuche ipigi, ipigisi, isipisigisi, isipisigisisisi, ipigisisisi und ipiigisi. Unterscheide gültige ipigisi-Folgen, mathematisch korrekte Ausdrücke und Wörter mit verletzten Bildungsregeln. Prüfe anschließend die Ableitbarkeit mit der Grammatik und die Akzeptanz mit dem unten geladenen Kellerautomaten. Halte die Ergebnisse in einer Tabelle fest.
  2. Gib vollständige Ableitungen von ipigisi und isipisigisisisi an. Markiere, welche Anwendungen der Produktionen die erste Zahl, die zweite Zahl und das Ergebnis vergrößern. Welche Produktion beendet jeweils diese Erweiterung?
  3. Begründe allgemein, dass die Grammatik genau die mathematisch korrekten Ausdrücke erzeugt. Zähle dazu die i in den drei isi-Folgen in Abhängigkeit von der Anzahl der Anwendungen von A -> siAis und B -> siBis. Zeige sowohl, dass jede vollständige Ableitung eine richtige Rechnung ergibt, als auch, dass jede Addition zweier positiver ganzer Zahlen darstellbar ist.
  4. Protokolliere für ipigisi nach jedem Automatenübergang den Zustand, die Resteingabe und den Kellerinhalt mit Z links. Erkläre die Bedeutung von X und der Übergänge i|Z→ZX, i|X→XX, i|X→ und ε|Z→. Vergleiche den Lauf mit der Ableitung: Wie wird in beiden Modellen festgehalten, dass ein zusätzliches i links von g ein zusätzliches i rechts davon verlangt?
  5. Eine Schülerin behauptet: „Wenn Grammatik und Kellerautomat bei allen sechs Wörtern aus a) übereinstimmen, erkennen sie dieselbe Sprache.“ Beurteile die Aussage. Formuliere für den Automaten zusätzlich eine allgemeine Beziehung zwischen dem Kellerinhalt und den bisher gelesenen i. Nutze sie zusammen mit den Zustandsphasen und deiner Begründung aus c), um die Übereinstimmung beider Modelle zu erklären.
  6. Vergleiche die Sprache aller gültigen ipigisi-Folgen mit der hier untersuchten Sprache. Erkläre den Unterschied zwischen der Prüfung der Bildungsregeln und der vereinbarten Bedeutung als Rechnung. Was zeigt die kontextfreie Grammatik über die Einordnung der Sprache? Weshalb kann man allein aus einer nicht regulär aufgebauten Grammatik noch nicht schließen, dass ihre Sprache nicht regulär ist?

Suche

v
100.130.2.3.3.5 Übungen
Kopieren durch Anklicken

Rückmeldung geben