2. Vorlesung (29-apr-99)

(Fast) Alles was wir immer schon über Typen wissen wollten ...

The Common-Lisp data type hierarchy is tangled and purposely left somewhat open-ended [...]
[Steele 90, 37]

Für die praxisnahe und effiziente Repräsentation endlicher Automaten ist die Kodierung der Eingabe als Liste von Symbolen ungeeignet, weil

• Eingaben typischerweise als Folge von Zeichen vorliegen (e.g. beim Lesen mit read-line());
• Symbole (typischerweise) nicht nach Groß- und Kleinschreibung unterscheiden;
• Symbole mehr Speicherplatz belegen als notwendig ist;
• Listen mehr Speicherplatz belegen als notwendig ist.

• characters; zur Repräsentation einzelner Zeichen (Buchstaben) und
• Konversionsfunktionen zwischen characters und integers: char-code() und code-char;
• Prädikate über characters, e.g. alphanumericp();
• Zeichenketten als Vektoren von characters;
• Zugriffsfunktionen für einzelne Elemente von Zeichenketten (und Vektoren im allgemeinen);
• Zugriffsfunktionen für Subsequenzen) von Zeichenketten;
• sogenannte generalisierte Variablen: Zuweisung an Feldelemente mit setf().

So ausgerüstet können wir eine Variante der Automatenfunktionen schreiben, die mit beliebigen sequences arbeitet (characters.lsp). Um jedoch den kostspieligen Test über die Länge der Resteingabe und die unnützen Kopien durch subseq() zu vermeiden, legen wir fortan fest, daß Eingaben als Strings (Vektoren von characters) vorliegen. So können wir optimierte Fassungen von traverse() angeben, die in optionalen Parametern die Länge der Eingabe und aktuelle Position verwalten (optimized.lsp).

Beim Übergang von reinen Akzeptoren (i.e. Automaten, die entscheiden, ob ein Wort zu einer Sprache gehört) zu Automaten, die einen Wert berechnen, der das Analyseergebnis charakterisiert, gibt es oft Eingaben, denen mehrere verschiedene Analysen zugewiesen werden können. Betrachten wir als Beispiel die Analyse von flektierten Verbformen (im Indikativ - Aktiv - Präsens) des Deutschen: denken kann hier entweder als Form in der 1. oder 3. Person Plural analysiert werden.

Eine Möglichkeit, solche Ambiguitäten in endlichen Automaten zu beschreiben, sind nicht deterministische Automaten (non-deterministic finite state automata), die mehrere Übergänge mit dem gleichen Eingabesymbol zulassen. Nicht deterministische Automaten fordern geringe Änderungen in der Kodierung (Liste von Folgezustäden in der Übergangsmatrix anstelle eines einzelnen Folgezustands) und Abarbeitung (Verfolgen aller Folgezustäde und Aufsammeln der berechneten Ergebnisse).