Übungen
Klicke auf eine Aufgabenüberschrift, um die Aufgabe zu öffnen!
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.
- Finde vier Wörter, die der folgende Kellerautomat nicht erkennt, und vier Wörter, die er erkennt.
- Beschreibe die Sprache des Kellerautomaten so genau wie möglich.
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
- Untersuche
ipigi,ipigisi,isipisigisi,isipisigisisisi,ipigisisisiundipiigisi. 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. - Gib vollständige Ableitungen von
ipigisiundisipisigisisisian. Markiere, welche Anwendungen der Produktionen die erste Zahl, die zweite Zahl und das Ergebnis vergrößern. Welche Produktion beendet jeweils diese Erweiterung? - Begründe allgemein, dass die Grammatik genau die mathematisch korrekten Ausdrücke erzeugt. Zähle dazu die
iin den drei isi-Folgen in Abhängigkeit von der Anzahl der Anwendungen vonA -> siAisundB -> siBis. Zeige sowohl, dass jede vollständige Ableitung eine richtige Rechnung ergibt, als auch, dass jede Addition zweier positiver ganzer Zahlen darstellbar ist. - Protokolliere für
ipigisinach jedem Automatenübergang den Zustand, die Resteingabe und den Kellerinhalt mitZlinks. Erkläre die Bedeutung vonXund der Übergängei|Z→ZX,i|X→XX,i|X→undε|Z→. Vergleiche den Lauf mit der Ableitung: Wie wird in beiden Modellen festgehalten, dass ein zusätzlichesilinks vongein zusätzlichesirechts davon verlangt? - 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. - 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?