Wahlpflichtthemen

2. Formale Sprachen (1)

Einführung

Wenn man einen Gedanken in einer natürlichen Sprache ausdrücken will, kommt es im wesentlichen auf zwei Aspekte an:

1. Der korrekte Aufbau von Wörtern und Sätzen gemäß der Grammatik und den Rechtschreiberegeln, die Syntax.
2. Die Bedeutung, die auf der Grundlage eines syntaktisch korrekten Satzes von der Sprache übermittelt werden soll, die Semantik.

Der zweite Punkt entzieht sich, auch wenn Ansätze zur Untersuchung der formalen Semantik vorhanden sind, weitgehend einer automatisierten Überprüfung. Dagegen kann, z.B. beim Kompilieren eines Computerprogramms, die syntaktische Korrektheit an Hand festgelegter Regeln überprüft werden. Man unterscheidet bei der Beschreibung formaler Sprachen nicht zwischen Wörtern und Sätzen, sondern betrachtet ein Wort als Zeichenkette über einem gegebenen Alphabet E, also einer nichtleeren Menge von Zeichen. Die Menge aller endlichen Wörter über E, d.h. gebildet aus beliebigen Zeichen aus E, bezeichnen wir als E^*:

E^* = { e₁e₂...e_n | n Î N₀, e_i Î E für alle i Î {1,..,n} }.

Das "leere Wort" l mit der Länge 0 gehört zu dieser Menge.
Jede Sprache L über dem Alphabet E ist eine Teilmenge von E^*: L Ì E^*.
Wenn eine Menge von Wörtern formal beschreibbar ist, was unten näher ausgeführt wird, und die Zugehörigkeit eines Worts nur aus syntaktischen Regeln und nicht durch Semantik oder Interpretation folgt, nennen wir diese Menge eine formale Sprache.

Formale Beschreibung

Die formalen Systeme, die eine Sprache beschreiben und in der Folge untersucht werden sollen, sind zunächst als Überblick ohne Anspruch auf Vollständigkeit aufgelistet:

1. Mengennotation in der beschreibenden Art L = { w | w hat bestimmte Eigenschaften } oder durch Aufzählung;
2. Automaten, die eine Sprache akzeptieren;
3. Reguläre Ausdrücke;
4. Semi-Thue-Systeme;
5. Chomsky-Grammatiken.

Ein formales System zur Beschreibung einer formalen Sprache L heißt

• erzeugend, wenn jedes Wort w Î L in endlich vielen "Schritten" erzeugt werden kann,
• analysierend, wenn es zu jedem Wort w Î L nach endlich vielen "Schritten" angeben kann, dass w zu L gehört.

Zu den analysierenden Systemen gehören z.B. die Automaten, zu den erzeugenden Semi-Thue-Systeme und Chomsky-Grammatiken.

[Index] [Fortsetzung/Reguläre Sprachen]

Autor: Jürgen Dehmer
Letzte Änderung: