inf-schule | Syntaxdiagramme

Übungen

Die Aufgaben sind in drei Gruppen geordnet. Klicke auf eine Aufgabenüberschrift, um die Aufgabe zu öffnen!

Diagramme lesen und prüfen

Aufgabe 1 - Torjubel und Lachen

Hier siehst du zwei Syntaxdiagramme. Beide begegnen dir in späteren Kapiteln wieder.

Stelle in der ersten Maschine das Wort Tooor und in der zweiten das Wort hahaha her.
Entscheide, ob das Wort zur Sprache Torjubel gehört:
- Tor
- Tr
- ToooorT
Entscheide, ob das Wort zur Sprache Lachen gehört:
- haha
- hah
- haa
Beschreibe in eigenen Worten, wie die Wörter der Sprache Lachen aufgebaut sind. Gib das kürzeste Wort an.

Du kommst nicht weiter?

Gehe das Wort Zeichen für Zeichen durch das Diagramm. Wo musst du einen Weg wählen? Wo gibt es nur einen Weg?

Aufgabe 2 - Zahlen wie in Python

Das folgende Syntaxdiagramm beschreibt vereinfacht, wie Zahlen in Python aufgebaut sind. Es erlaubt ein optionales Vorzeichen, keine führenden Nullen (außer bei der Zahl 0 selbst) und optional einen Punkt mit mindestens einer Nachkommaziffer. Ein Kasten wie 1–9 steht für einen Zeichenbereich: Du wählst eine der Ziffern von 1 bis 9.

Stelle das Wort -12.50 her.
Entscheide mithilfe des Diagramms, ob das Wort eine gültige Zahl ist:
- 42
- -0.5
- 007
- 3.
- 1,5
Gib alle fünf Wörter in einer Python-Shell ein, dazu .5. Vergleiche die Reaktion von Python mit deinen Entscheidungen. Bei welchen Wörtern gibt es Unterschiede?
Diskutiere: Warum beschreibt das Diagramm die Zahlen von Python nur vereinfacht? Was müsstest du ändern, damit es genau zu Python passt?

Du kommst nicht weiter?

Prüfe bei jedem Wort: Welchen Weg müsste das erste Zeichen nehmen? Wo musst du dann abbiegen? Wird irgendwo ein Zeichen benötigt, das das Diagramm nicht anbietet?

Zum Nachlesen: Diagramm und Python im Vergleich

Ein Syntaxdiagramm legt genau fest, welche Zeichenketten zur Sprache gehören. Python erlaubt mehr als das vereinfachte Diagramm, zum Beispiel 3., .5 oder 1e3. Das Wort 007 lehnt Python dagegen ab, 1,5 versteht es als etwas ganz anderes (ein Paar von Zahlen). Wer eine Programmiersprache genau beschreiben will, muss also jede Einzelheit im Diagramm festlegen.

Aufgabe 3 - KfZ-Kennzeichen

Das Diagramm beschreibt vereinfacht KfZ-Kennzeichen wie MZ-AB123. Dabei steht B für einen beliebigen Buchstaben und Z für eine beliebige Ziffer. Aus MZ-AB123 wird also BB-BBZZZ.

Stelle das Wort BBB-BBZZZZ her.
Entscheide, ob das Wort zur Sprache Kennzeichen gehört:
- B-BZ
- BBBB-BZ
- B-ZZ
- BB-BBZZZZZ
- BB-B
Gib das kürzeste Wort der Sprache an:
Aus wie vielen Zeichen besteht das längste Wort?
Das Diagramm ist ungenau: Nenne zwei Eigenschaften echter Kennzeichen, die es nicht erfasst.

Diagramme entwerfen

Aufgabe 4 - A-B-Sprachen

Alle Wörter dieser Aufgabe bestehen nur aus den Zeichen a und b (Alphabet Σ = {a, b}). Skizziere auf Papier jeweils ein Syntaxdiagramm für die Sprache aller Wörter, die

mit a beginnen,
mit b enden,
das Teilwort ab enthalten,
mindestens zwei Zeichen haben,
am Anfang und am Ende verschiedene Zeichen haben.

Teste dein Diagramm, indem du jeweils zwei Wörter, die dazugehören, und zwei Wörter, die nicht dazugehören, durchspielst.

Du kommst nicht weiter?

Überlege zuerst: Welche Zeichen sind festgelegt, und an welcher Stelle im Wort stehen sie? Alles andere darf beliebig oft und in beliebiger Reihenfolge vorkommen. Das erreichst du mit einer Schleife um eine Verzweigung.

Lösungsvorschlag

a) Beginnt mit a. Beispiel: abba.

b) Endet mit b. Beispiel: abab.

c) Enthält ab. Beispiel: bbabaa.

d) Mindestens zwei Zeichen. Beispiel: bab.

e) Anfang und Ende verschieden. Beispiel: aabb.

Vergleiche mit deinem Entwurf. Andere Diagramme können dieselbe Sprache beschreiben.

Aufgabe 5 - Uhrzeiten

Uhrzeiten werden in der Form hh:mm geschrieben, zum Beispiel 07:45 oder 23:05. Zugelassen sind alle Uhrzeiten von 00:00 bis 23:59. Stunden und Minuten haben immer zwei Ziffern.

Skizziere auf Papier Syntaxdiagramme für gültige Uhrzeiten. Verwende dazu mehrere Diagramme, zum Beispiel für die Stunde und für die Minute.
Entscheide, ob 24:00, 9:30 und 12:60 zu deiner Sprache gehören.

Du kommst nicht weiter?

Die zweite Stundenziffer hängt von der ersten ab. Welche Ziffern darf sie nach 0 oder 1 haben, welche nach 2? Unterscheide diese Fälle mit einer Verzweigung.

Lösungsvorschlag

Keines der drei Wörter in b) gehört dazu: 24:00 (Stunde zu groß), 9:30 (nur eine Stundenziffer), 12:60 (Minute zu groß).

Aufgabe 6 - E-Mail-Adressen erweitern

Aus dem Einstieg kennst du diese Diagramme für vereinfachte E-Mail-Adressen:

Der User soll jetzt aus mehreren Namen bestehen dürfen, die durch Punkte getrennt sind. Zum Beispiel soll b.bb@bb.b eine gültige Adresse sein.

Entscheide, welches Diagramm du ändern musst, und skizziere die neue Fassung auf Papier.
Entscheide, ob die Adresse gültig ist, wenn man dein neues Diagramm verwendet:
- b.b.b@b.b
- .b@b.b
- b.@b.b

Du kommst nicht weiter?

Schau dir an, wie das Diagramm Subdomains mit Punkten und Namen umgeht. Der User braucht etwas Ähnliches, aber ohne den Punkt am Ende.

Lösungsvorschlag

Nur das Diagramm User ändert sich. Alle anderen bleiben gleich.

Aufgabe 7 - Zwei Diagramme, eine Sprache?

Hier siehst du zwei verschiedene Diagramme für Name.

Diagramm 1 (mit Schleife):

Diagramm 2 (verweist auf sich selbst):

Stelle in beiden Maschinen das Wort bbb her. Beschreibe, was jeweils mit dem Symbol Name bzw. Buchstabe passiert.
Beschreibe die Wörter, die Diagramm 1 herstellt, und die Wörter, die Diagramm 2 herstellt.
Begründe, ob beide Diagramme dieselbe Sprache beschreiben.

Du kommst nicht weiter?

Zähle bei Diagramm 2 mit: Wie oft musst du den Weg über Name nehmen, damit ein Wort mit fünf b entsteht? Kann das Wort in Diagramm 1 genauso lang werden?

Das hast du entdeckt – zum Nachlesen

Verschiedene Syntaxdiagramme können dieselbe Sprache beschreiben. Hier sind beide Diagramme gleichwertig: Sie stellen genau die Wörter b, bb, bbb, … her. Eine Schleife kann man oft durch ein Diagramm ersetzen, das auf sich selbst verweist. Umgekehrt geht es nicht immer, wie die nächsten Aufgaben zeigen.

Anspruchsvoller: Verschachtelung

Aufgabe 8 - Klammern

Aus dem Einstieg kennst du dieses Diagramm für geschachtelte Klammern:

Entscheide, ob das Wort zur Sprache Klammer gehört:
- ()
- ((()))
- ()()
- (()())
Die Wörter ()() und (()()) sind korrekt geschachtelte Klammerausdrücke. Erweitere das Diagramm so, dass alle korrekt geschachtelten Klammerausdrücke (mit mindestens einem Klammerpaar) hergestellt werden können. Skizziere dein Ergebnis auf Papier.
Das leere Wort ε soll jetzt auch dazugehören. Was musst du ändern?

Du kommst nicht weiter?

Ein Klammerausdruck besteht aus einem oder mehreren Klammerpaaren, die nebeneinander stehen. Innerhalb eines Paares steht wieder ein Klammerausdruck, oder nichts. Du brauchst dafür zwei Diagramme, die aufeinander verweisen.

Lösungsvorschlag

c) Im Diagramm Klammerausdruck gibst du der Schleife einen Weg vorbei, sodass man auch ohne ein einziges Klammerpaar zum Ausgang kommt. Dann führt ein Weg nur durch die Schleife, und das Klammer-Symbol vor der Schleife entfällt. So entsteht auch das leere Wort.

Das hast du entdeckt – zum Nachlesen

Hier verweisen zwei Diagramme gegenseitig aufeinander: Klammerausdruck enthält Klammer, und Klammer enthält wieder Klammerausdruck. Auch das ist eine Rekursion. Rekursion ist nötig, wenn sich Strukturen beliebig tief verschachteln, wie bei Klammern. Eine Schleife allein kann solche Verschachtelungen nicht beschreiben, weil sie nur Teile nacheinander wiederholt.

Aufgabe 9 - Rechenausdrücke

Die folgenden Diagramme beschreiben Rechenausdrücke. Dabei steht z für eine Zahl.

Stelle das Wort -z*(z+z) her.
Entscheide, ob das Wort ein gültiger Ausdruck ist:
- z*-z
- z++z
- --z
- -(z)
- (z+z
- z(z)
Das Wort z++z ist nach diesen Diagrammen gültig. Das möchtest du verhindern: Ein Vorzeichen soll nur ganz am Anfang eines Ausdrucks stehen dürfen, also auch am Anfang eines Ausdrucks in Klammern, aber nicht nach einem Operator. Ändere die Diagramme und skizziere sie auf Papier.

Du kommst nicht weiter?

Im Moment steht das Vorzeichen im Diagramm Operand, und der Operand wird nach jedem Operator durchlaufen. An welcher Stelle muss das Vorzeichen stattdessen stehen?

Lösungsvorschlag

Das Vorzeichen wandert in das Diagramm Ausdruck, direkt an den Anfang. Der Operand besteht nur noch aus z oder einem Ausdruck in Klammern.

Jetzt sind z*-z und z++z nicht mehr herstellbar, (-z) aber schon.

Aufgabe 10 - Palindrome

Ein Palindrom ist ein Wort, das vorwärts und rückwärts gelesen gleich ist, zum Beispiel abba oder aba. Betrachte alle nichtleeren Palindrome über dem Alphabet Σ = {a, b}.

Entscheide für abaaba, abab und b, ob sie Palindrome sind.
Entwirf auf Papier ein Syntaxdiagramm für alle nichtleeren Palindrome über {a, b}.
Passe dein Diagramm so an, dass nur Palindrome mit gerader Länge hergestellt werden.

Du kommst nicht weiter?

Entferne bei abaaba das erste und das letzte Zeichen. Was bleibt übrig? Vergleiche mit dem Diagramm Klammer aus dem Einstieg.

Lösungsvorschlag

a) abaaba und b sind Palindrome, abab nicht.

b) Außen stehen zwei gleiche Zeichen, innen steht wieder ein Palindrom (oder nichts). Ein Palindrom mit nur einem Zeichen ist ein Sonderfall.

c) Du lässt die beiden Wege weg, die nur aus einem einzelnen a oder b bestehen. Dann stehen außen immer zwei Zeichen, und jedes Wort hat eine gerade Länge.

Aufgabe 11 - Ausblick: aⁿbⁿcⁿ

Dieses Diagramm stellt Wörter her, in denen auf n Zeichen a genau n Zeichen b folgen:

Jetzt betrachtest du die Sprache, in der auf n Zeichen a genau n Zeichen b und dann genau n Zeichen c folgen: abc, aabbcc, aaabbbccc, …

Stelle in der Maschine das Wort aaabbb her.
Versuche, ein Syntaxdiagramm für die Sprache mit n mal a, n mal b und n mal c zu entwerfen. Woran scheiterst du?
Formuliere eine Vermutung, woran das liegen könnte.

Du kommst nicht weiter?

Betrachte aabbcc. Beim Diagramm AnBn stellt jeder Durchlauf ein a und das passende b her. Warum lässt sich das nicht einfach um die c ergänzen?

Auflösung (erst nach deinen Versuchen öffnen)

Diese Sprache lässt sich mit Syntaxdiagrammen nicht beschreiben. Ein Diagramm kann sich zwar merken, dass zu jedem a ein b gehört, weil es innen und außen zusammenpasst. Für drei Teile, die gleich lang sein müssen, reicht diese Art der Verschachtelung nicht aus. Warum das so ist, klärst du später im Kapitel „Formale Sprachen klassifizieren“.

Übungen

Diagramme lesen und prüfen

Diagramme entwerfen

Anspruchsvoller: Verschachtelung

Suche

Rückmeldung geben