Christian Eisentraut & Julia Krämer
www.vorkurs-mathematik-informatik.de
Mathematik-Vorkurs für Informatiker
Formale Sprachen1
Aufgabe 1. (Wiederholung wichtiger Begriffe)
Notieren Sie die Definitionen der folgenden Begriffe aus dem Kopf ohne im Skript nachzuschlagen und korrigieren Sie dann ihre Lösungen:
(a) Unterschied zwischen natürlichen und formalen Sprachen
(b) Syntax
(c) Semantik
(d) Sprache der binären Bäume in Backus-Naur-Form
(e) Sprache der arithmetischen Ausdrücke in Backus-Naur-Form
(f) die (inhaltlich) korrekte Semantikabbildung zu arithmetischen Ausdrücken
Kategorie
Aufgabe 2. (Metavariablen)
Erklären Sie den Unterschied zwischen Metavariablen und Variablen der Menge V.
Kategorie
Beantworten Sie dabei auch die folgenden Fragen: Weshalb brauchen wir Variablen in
arithmetischen Ausdrücken? Benötigen wir Metavariablen unbedingt, um arithmetische
Ausdrücke bzw. binäre Bäume zu definieren?
Aufgabe 3. (Wiederholung - einmal anders)
Versuchen Sie, Ihren Großeltern zu erklären, was eine informatische Sprache ist.
Kategorie
Aufgabe 4. (Sinn einer Grammatik)
Diskutieren Sie die folgende Frage: Wozu ist eine Grammatik gedacht und wie verwendet man Sie? Überlegen Sie sich dazu: Wie würden Sie die Sprache der Aussagenlogik
notieren ohne die Definition der Vorlesung zu verwenden? Wie bestimmen Sie, ob ein
Ausdruck zu einer Sprache gehört oder nicht?
1
Die vorlegende Sammlung an Übungsaufgaben erstellt von Christian Eisentraut und Julia Krämer
(www.vorkurs-mathematik-informatik.de) ist inklusive aller darin vorkommenden Texte und Bilder lizenziert unter einer Creative Commons Namensnennung - Nicht-kommerziell - Weitergabe
unter gleichen Bedingungen 4.0 International Lizenz. Weitere Hinweise finden Sie unter http:
//creativecommons.org/licenses/by-nc-sa/4.0/.
1
Kategorie
Gruppenaufgabe
Aufgabe 5. (Backus-Naur-Form (1))
Benutzen Sie eine Grammatik in Backus-Naur-Form, um die induktiv definierte Sprache
Listen über den Zeichen o und ∗ zu definieren.
Kategorie
Die Sprache Liste enthält Wörter, die nach folgendem Schema aufgebaut sind: o, ∗o.
∗ ∗ o, …
Aufgabe 6. (Backus-Naur-Form (2))
Benutzen Sie eine Grammatik in Backus-Naur-Form, um die induktiv definierte Sprache
N über dem Zeichen ∅ zu definieren.
Kategorie
Die Sprache N enthÄlt Wörter, die nach folgendem Schema aufgebaut sind: ∅, {∅},
{{∅}}, …
Aufgabe 7. (Backus-Naur-Form – umgekehrt)
Welche Sprache B beschreibt die folgende Backus-Naur-Form? Entwicklen Sie eine aussagekräftige Aufzählung von Wörten, d.h. geben Sie so viele Wörter der Sprache an, wie
notwendig sind, damit man das “Schema”, welches hinter der Sprache steht, vollständig
erkennen kann.
Kategorie
B ∋ φ ::= ab | aφb
Aufgabe 8. (Arithmetische Ausdrücke - nicht korrekt geklammert)
Dieser Aufgabe liegt die folgende Grammatik arithmetischer Ausdrücke zugrunde:
Kategorie
C ∋ φ, ψ ::= φ + ψ | φ − ψ | φ · ψ | phi ÷ ψ | n
wobei n ∈ N, also n eine natürliche Zahl ist. Welche der folgenden Ausdrücke gehören zur
Sprache der arithmetischen Ausdrücke C? Erkären Sie für alle inkorrekten Ausdrücke,
warum diese inkorrekt sind, und finden Sie für alle korrekten Ausdrücke einen entsprechenden Syntaxbaum.
(a) (4 + (3 − (2 · 9)))
(b) (−2)
(c) (7 + ((1 ÷ (3 · 9)) · 9))
(d) ((2 ÷ 0) + 7 − 2)
2
Aufgabe 9. (Verwenden von Semantikklammern)
Verwenden Sie die (inhaltlich) korrekte Definition der Semantik arithmetischer Ausdrücke, um die Semantik der folgenden Ausdrücke zu berechnen. Achten Sie dabei auf die
korrekte Klammerung und lassen Sie keinen Zwischenschritt aus.
Kategorie
Beispiel
J1 ÷ 2 ÷ 3K =
J1÷2K
J3K
=
J1K
J2K
3
=
1
2
3
=
1
6
(a) (4 + 7) · (3 − 4)
(b) 3 · 4 · 5 · 6
(c) 3 + 4 · 5 − 6 ÷ 7
Aufgabe 10. (Modellieren mit Sprachen (1))
Bestimmen Sie die Sprache aller ternären Bäume, d.h. der Bäume, deren Knoten entweder genau drei oder keine Kinder haben. Geben Sie dazu eine Backus-Naur-Form an,
die die Menge aller ternären Bäume beschreibt.
Der folgende Baum ist zum Beispiel ein ternärer Baum.
Kategorie
Aufgabe 11. (Modellieren mit Sprachen (2))
Stellen Sie sich vor, Sie sind nicht nur Informatiker, sondern auch Gärtner. Um sich schon
dem eigentlichen Aussähen sicher sein zu können, dass Ihr Blumenbeet so aussieht, wie
Sie sich das vorstellen, möchten Sie ein Blumenbeet als Sprache modellieren.
(a) Geben Sie eine Sprache an, die eine einzelne Blumenbeetreihe beschreibt. Berücksichtigen Sie dabei Gänseblümchen, Tulpen und Narzissen.
(b) Nun möchten Sie ein Beet mit beliebig vielen Blumenbeetreihen modellieren. Erweitern Sie Ihre Definitionen dazu um eine weitere Backus-Naur-Form, die auf der
Definition für Blumenbeetreihen aufbaut.
(c) Entwerfen Sie sich eine Semantik für Blumenbeete (Möglichkeiten: Gesamtgröße,
Wasserverbrauch Anzahl an verschiedenen Blumen, …)
Kategorie
3
Aufgabe 12. (Über den Tellerrand)
Beurteilen Sie, ob Sie mithilfe einer oder mehrerer Backus-Naur-Formen die Sprache
aufschreiben können, bei der auf jedes a ein b oder ein e folgt, auf jedes b die Zeichenkette
ef , auf e entweder b, f oder a und auf f ein a folgt.
Wie sieht Ihre Beurteilung aus, wenn auf jeden der Buchstaben auch nichts folgen darf?
Erläutern Sie jeweils, warum es nicht möglich ist, solch eine Sprache mit Hilfe von BNFs
zu modellieren bzw. geben Sie eine BNF an, die genau diese Sprache beschreibt.
Kategorie
Aufgabe 13. (Über den Tellerrand)
Wählen Sie einen geeigneten Ausschnitt der realen Welt aus und entwerfen Sie ein Modell
davon mithilfe von formalen Sprachen.
Kategorie
4
© Copyright 2024 ExpyDoc
