Logik:Klausuren/20.02.2002/B.4 Aufgabe: Unterschied zwischen den Versionen

Aktuelle Version vom 23. November 2004, 16:57 Uhr

1. Aufgabenstellung[Bearbeiten]

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). $

2. Lösung[Bearbeiten]

3. Lösungsweg[Bearbeiten]

4. Alternativen/Diskussion/Hinweise etc.[Bearbeiten]

zur Klausur 20.02.2002