Tag2Aufg

	*Didaktik der* *Informatik*

Projekttage zum Erwerb eines Scheins zur Vorlesung Algorithmen, Daten und Programme II, SS 98

Programmierung elementarer Algorithmen

Aufgabe 2 "Sprachprobleme"

Zwischen den Siedlungen auf unserem Planeten Erde2 liegen große Entfernungen und vierzig Jahre lang herrscht nur geringer Kontakt, so dass sich die Sprache in den Siedlungen unterschiedlich entwickelt. Während die Grammatik unverändert erhalten blieb, haben sich teilweise unterschiedliche Begriffe und Zeichen für identische Sachverhalte gebildet. Für diplomatische Gespräche sollen daher schnelle und flexible Sprachübersetzer geschaffen werden.

a) (Vorübung) Schreiben Sie ein Programm in ML, welches Eingabezeichenketten von der Sprache1 in die Sprache2 übersetzt. Verwenden Sie das Modell eines endlichen Automaten.

Sprache 1	Sprache 2
aa	b
ba	a
ab	f
bc	a
d
b	ende

Das Wort "bcaadb" kann z. B. nach "abende" übersetzt werden.
"aacb" könnte ein Fall sein, der nicht übersetzt werden kann.
Hinweis:
Es können gegebenenfalls Fälle auftreten, die nicht eindeutig sind, so dass zusätzliche Bedingungen für die Übersetzung festgelegt werden müssen.

b) Schreiben Sie ein Programm P in ML, welches bei Eingabe von zwei Sprachbeschreibungen A und B ein Programm P' (oder ein Datenmodul für P') erzeugt, das Zeichenketten von der Sprache A in die Sprache B übersetzt. Die Sprachbeschreibung erfolgt in einer Folge von Wortpaaren (<alt>,<neu>), die jeweils Begriffe aus den Sprachen mit identischer Bedeutung zuordnen. Die Zeichenfolge besteht aus mehreren Wörtern, die gegebenenfalls durch ein sprachabhängiges Zeichen getrennt sind, d. h. eines der Wortpaare bildet das Trennsymbol der einen Sprache auf das Trennsymbol der anderen Sprache ab (es ist jedoch nicht bekannt welches!).

Syntax der Spracheingabe:

<Sprache>	::=	<Folge> (,)
<Folge>	::=	<Ersetzung> \| <Folge> <Ersetzung>
<Ersetzung>	::=	(<alt>,<neu>)
<alt>	::=	<Zeichenkette>
<neu>	::=	<Zeichenkette> \| eps
<Zeichenkette>	::=	<Zeichen> \| <Zeichenkette> <Zeichen>
<Zeichen>	::=	<irgendein ASCII-Zeichen, ausser (,) >

c) optionale Aufgabe: Minimierung des Datenmoduls für P' (d. h. Minimierung des endlichen Automaten)

Stichworte:
Pattern Matching, regulärer Ausdruck, kontextfreie Grammatik, deterministischer endlicher Automat, Top-Down, Bottom-Up, Syntaxanalyse, Parser, nichtdeterministischer Automat

Literatur: Sedgewick S. 342-370 (Kapitel 20, 21), zu Aufg. (c): Hopcroft-Ullman S. 72-75

Ergebnisse der Projektgruppe