Lektion 2: Grammatiken

Ihr wisst bereits, was formale Sprachen sind. In dieser Lektion werdet ihr lernen, wie man mit Grammatiken Wörter einer Sprache konstruieren kann und welche Regeln Grundlage einer Grammatik sind.

Aufgabe 1: Grammatiken

Lies das Fachkonzept: Grammatik und beantworte folgende Fragen:

Aus welchen Bestandteilen besteht eine Grammatik?
Welche "Sonderregel" gilt für reguläre Grammatiken?
Was ist die Chomsky-Hierarchie?

Aufgabe 2: Syntaxdiagramme

Lies das Fachkonzept: Syntaxdiagramm und stelle im Anschluss daran die Grammatik für EMails aus dem Fachkonzept Grammatik als Syntax-Diagramm dar.

Aufgabe 3: Übungsaufgaben

Aufgabe: Grammatik für Bezeichner

Bezeichner = Buchstabe {Buchstabe | Ziffer}.
Ziffer = "0" | "1" | "2" | "..." | "9".
Buchstabe = "a" | "b" | "c" | "..." | "z".

Beantwortet in eurem Gruppendokument:

Welche Nichtterminalsymbole und welche Terminalsymbole enthält die Grammatik?
Gib ein Wort der Sprache an und ein Wort, das nicht zur Sprache gehört.
Zeichne ein Syntaxdiagramm dazu (per Hand!). Kontrolliert euer Ergebnis mit dem EBNF-Tool.

Lösung Bezeichner

Nichtterminalsymbole: Bezeichner, Ziffer, Buchstabe, Terminalsymbole: 0, …, 9, a, …, z
z.b. nudelsuppe123 gehört dazu, 1nudel2 nicht.
siehe Grafik

{Bezeichner = Buchstabe {Buchstabe | Ziffer}.
Ziffer = "0" | "1" | "2" | "..." | "9".
Buchstabe = "a" | "b" | "c" | "..." | "z".}

Aufgabe: ABBA

Gegeben sei die Grammatik $G$ mit $N=\{X,C\}$, $T=\{a,b\}$ und $S=X$. Die Regeln $P$:

$X\to aCa$
$C\to\varepsilon|bbC$

Das Symbol $\varepsilon$ soll das leere Wort darstellen, C kann also durch "nichts" oder durch bbC ersetzt werden.

a) Zeichne mit dem EBNF-Tool ein Syntaxdiagramm.

b) Prüfe, ob die folgenden Wörter in der Grammatik abgeleitet werden können:

aa
abba
abbbba
abbba

Notiere die Begründungen, warum oder warum nicht, in eurem Gruppendokument.

Lösung ABBA

{
X = "a" C "a".
C = ["b" "b" C].
}

  X = "a" C "a".
  C = ["b" "b" C].

abbba kann nicht abgeleitet werden, da b's nur in Paaren auftreten können. Alle anderen Wörter sind Teil der Sprache.

Aufgabe: Binärzahlen

Gegeben sei die Grammatik $G$ mit $N=\{s_0,s_1,s_2\}$, $T=\{0,1\}$ und $S=s_0$. Das Symbol $\varepsilon$ soll das leere Wort darstellen. Die Regeln:

$s_0\to\varepsilon|0s_0|1s_1$
$s_1\to 0s_2|1s_0$
$s_2\to 0s_1|1s_2$

{
s0 = [ "0" s0 | "1" s1 ].
s1 = "0" s2 | "1" s0.
s2 = "0" s1 | "1" s2.
}

1. Die Worte können als Binärzahlen interpretiert werden. Stelle fest, welche der Binärzahlen in der Grammatik ableitbar sind:

Wort	Dezimalzahl	ableitbar?
0
1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111

2. Erläutere im Gruppendokument die Ableitung am Beispiel 10101.

Lösung Aufgabe Binärzahlen

Wort	Dezimalzahl	Ableitung	ableitbar?
0	0	$s_0 \rightarrow 0s_0 \rightarrow 0\varepsilon \rightarrow \color{green}{\bf 0} $	ja
1	1	$s_0 \rightarrow \color{red}{\bf 1s_1} $	nein
10	2	$s_0 \rightarrow 1s_1 \rightarrow \color{red}{\bf 10s_2} $	nein
11	3	$s_0 \rightarrow 1s_1 \rightarrow 11s_0 \rightarrow 11\varepsilon \rightarrow \color{green}{\bf 11} $	ja
100	4	$s_0 \rightarrow 1s_1 \rightarrow 11s_0 \rightarrow \color{red}{\bf 111s_1} $	nein
101	5	$s_0 \rightarrow 1s_1 \rightarrow 10s_2 \rightarrow \color{red}{\bf 101s_2} $	nein
110	6	$s_0 \rightarrow 1s_1 \rightarrow 11s_0 \rightarrow 110s_0 \rightarrow 110\varepsilon \rightarrow \color{green}{\bf 110} $	ja
111	7	$s_0 \rightarrow 1s_1 \rightarrow 11s_0 \rightarrow \color{red}{\bf 111s_1} $	nein
1000	8	$s_0 \rightarrow 1s_1 \rightarrow 10s_2 \rightarrow 100s_1 \rightarrow \color{red}{\bf 1000s_2} $	nein
1001	9	$s_0 \rightarrow 1s_1 \rightarrow 10s_2 \rightarrow 100s_1 \rightarrow 1001s_0 \rightarrow 1001\varepsilon \rightarrow \color{green}{\bf 1001}$	ja
1010	10	$s_0 \rightarrow 1s_1 \rightarrow 10s_2 \rightarrow 101s_2 \rightarrow \color{red}{\bf 1010s_1} $	nein
1011	11	$s_0 \rightarrow 1s_1 \rightarrow 10s_2 \rightarrow 101s_2 \rightarrow \color{red}{\bf 1011s_2} $	nein
1100	12	$s_0 \rightarrow 1s_1 \rightarrow 11s_0 \rightarrow 110s_0 \rightarrow 1100s_0 \rightarrow 1100\varepsilon \rightarrow \color{green}{\bf 1100}$	ja
1101	13	$s_0 \rightarrow 1s_1 \rightarrow 11s_0 \rightarrow 110s_0 \rightarrow \color{red}{\bf 1101s_1} $	nein
1110	14	$s_0 \rightarrow 1s_1 \rightarrow 11s_0 \rightarrow 111s_1 \rightarrow \color{red}{\bf 1110s_2} $	nein
1111	15	$s_0 \rightarrow 1s_1 \rightarrow 11s_0 \rightarrow 111s_1 \rightarrow 1111s_0 \rightarrow 1111\varepsilon \rightarrow \color{green}{\bf 1111}$	ja

$ s_0 \rightarrow 1s_1 \rightarrow 10s_2 \rightarrow 101s_2 \rightarrow 1010s_1 \rightarrow 10101s_0 \rightarrow 10101\varepsilon \rightarrow \color{green}{\bf 10101} $

Aufgabe: Post

Entwickle eine Grammatik in EBNF für Postanschriften. Beachte die folgenden Aspekte:

Eine Postanschrift besteht aus einem Personenteil, gefolgt von einer Straße, gefolgt von der Stadt.
Der Personenteil besteht aus einem Titelteil und einem Namensteil, gefolgt von einem Zeilenende.
Der Titelteil besteht aus einem Titel (z.B. "Dr." oder "Prof.") oder ist leer.
Der Namensteil besteht aus einem Vornamensteil, einem Nachnamen oder aus einem Vornamensteil und wiederum aus einem Namensteil.
Der Vornamenteil besteht aus einem Vornamen oder einem Initial, auf den ein Punkt folgt.
Eine Straße besteht aus einem Straßenname, gefolgt von einer Hausnummer, gefolgt von einem Zeilenende.
Eine Stadt besteht aus einer Postleitzahl, gefolgt von einem Stadtnamen, gefolgt von einem Zeilenende.

Erstelle mit dem EBNF-Tool ein Syntax-Diagramm. Notiere den EBNF-Code und das Diagramm in eurem Gruppendokument.

Lösung: Post

Die folgende Grammatik in EBNF ist eine Lösung. Man kann es auch anders machen, z.B. die Regel "Titel" so umsetzen, dass beliebige Titel erkannt werden, nicht nur die vier vorgegebenen.

Postanschrift = Person Straße Stadt.
Person = Titel Name Zeilenende.
Titel = [ "Dr." | "Prof." | "Mr." | "Mrs." ].
Name = Vorname Nachname | Vorname Name.
Vorname = Buchstabe "." | Nachname.
Nachname = Buchstabe { Buchstabe }.
Straße = Straßenname Hausnummer Zeilenende.
Straßenname = Buchstabe { Buchstabe }.
Hausnummer = Zahl { Zahl } [ Buchstabe ].
Stadt = Postleitzahl Stadtname Zeilenende.
Postleitzahl = Zahl Zahl Zahl Zahl Zahl.
Stadtname = Buchstabe { Buchstabe }.
 
Buchstabe = "a" | "b" | "c" | "..." | "z".
Zahl = "0" | "1" | "..." | "9".
Zeilenende = "\n".

${ Postanschrift = Person Strasse Stadt. Person = Titel Name Zeilenende. Titel = [ "Dr." | "Prof." | "Mr." | "Mrs." ]. Name = Vorname Nachname | Vorname Name. Vorname = Buchstabe "." | Nachname. Nachname = Buchstabe { Buchstabe }. Strasse = Strassenname Hausnummer Zeilenende. Strassenname = Buchstabe { Buchstabe }. Hausnummer = Zahl { Zahl } [ Buchstabe ]. Stadt = Postleitzahl Stadtname Zeilenende. Postleitzahl = Zahl Zahl Zahl Zahl Zahl. Stadtname = Buchstabe { Buchstabe }. Buchstabe = "a" | "b" | "c" | "..." | "z". Zahl = "0" | "1" | "..." | "9". Zeilenende = "\n". }$

Aufgabe: Biber-Perlenketten

Die Kinder der kreativen Biberdame Grace basteln Perlenketten. Sie haben verschiedene Holzperlen (quadratisch und kreisförmig), die sie rot oder blau einfärben können. So können sie beispielsweise die folgende Kette basteln:

Grace erklärt den Kindern, dass diese Kette die folgende Kettenbeschreibung hat:

Grace fertigt nun zwei Zeichnungen an, die "kette" und "teil" heißen. Sie möchte nur Ketten haben, deren Kettenbeschreibung man erhalten kann, wenn man den Pfeilen in den Zeichnungen folgt:

Die kleinen Biber basteln vier Ketten. Leider passt nur eine zu Graces Zeichnungen. Welche? Notiere die Begründungen im Gruppendokument.

Notiere dir im Gruppendokument auch die EBNF der Sprache.

Erläuterung zu Biber-Perlenketten

Transkript Video

Transkript (PDF)

Lösung: Biber

Nur D) ist korrekt. Bei A) sind die rechten Vierecke vertauscht. Bei B) sind die blauen Elemente in der Mitte vertauscht. Bei C) hat der mittlere blaue Kreis keinen Partner.

"Biberperlenkette" {
kette = ("rot" | "blau") "(" teil ")" .
teil = [kette | "kreis" teil "kreis" | "viereck" teil "viereck"] .
}

  kette = ("rot" | "blau") "(" teil ")" .
  teil = [kette | "kreis" teil "kreis" | "viereck" teil "viereck"] .

Transkript Video (PDF)