Logik:Klausuren/20.02.2002/B.4 Aufgabe
Inhaltsverzeichnis
1. Aufgabenstellung
Eine Sprache $ S\ $ mit dem Alphabet $ \left\{a; b; [\;,\;]; +\right\} $sei die kleinste Menge, die die folgenden
Bedingungen erfüllt:
1. Die Zeichenketten $ a\ $ und $ b\ $gehören zur Sprache $ S.\ $
2. Wenn $ s \ $ein Element der Sprache $ S\ $ist, dann ist $ [s\ $ebenfalls ein Element der Sprache
$ S.\ $
3. Wenn $ s_1\ $und $ s_2\ $Elemente der Sprache $ S\ $sind, dann ist die Zeichenkette $ s_1\,s_1 [+]s_2 $
ebenfalls ein Element der Sprache $ S.\ $
a) Gehören die folgenden Zeichenketten zur Sprache $ S\ ? $
$ [\;[\;[+] \ \ \quad ja \Box \quad nein \Box \qquad \qquad [\;[a[+]b[ \;\quad ja \Box \quad nein \Box $
$ [\;[a[+]b \quad ja \Box \quad nein \Box \qquad \qquad [a[a[+][a \quad ja \Box \quad nein \Box $
b) Formulieren Sie das Prinzip der strukturellen Induktion für diese Sprache (ohne
Beweis).
c) Bezeichne $ f(s)\, $die Anzahl der in s vorkommenden öffnenden eckigen Klammern und
$ g(s)\, $ die Anzahl der in $ s \, $vorkommenden schließenden eckigen Klammern. Beweisen
Sie mit struktureller Induktion: Wenn die Zeichenkette $ s \, $ein Element der Sprache
$ S \, $ist, dann gilt $ f(s) \geq g(s). $
