Um Informationen austauschen zu können, bedient man sich der Sprache. Dabei müssen Sätze nach bestimmten Regeln aufgestellt werden, damit ihre Bedeutung verstanden wird. Diese Regeln werden Grammatik genannt. Natürliche Sprachen haben einen hohen Wortschatzumfang und komplexe Grammatiken. Somit kann man komplizierte Sachverhalte sprachlich ausdrücken.
In technischen oder theoretischen Systemen reicht jedoch meistens eine geringe Wortzahl, um Informationen auszutauschen. Daher ist es nicht sinnvoll, sich an natürlichen Sprachen zu orientieren. Vielmehr versucht man, die Sprachen den Bedürfnissen der Systeme anzupassen. Dadurch entstehen formale Sprachen wie die mathematische Formelsprache und die Computersprachen.
Formale Sprachen sind nicht nur für den Informationsaustausch wichtig, sondern auch für die Grundlagenforschung. So werden etwa Methoden gewonnen zur Sprach- und Zeichenerkennung bei natürlichen Sprachen.
Im folgenden wird eine Definition Formaler Sprachen gegeben und es werden Beschreibungsmöglichkeiten erarbeitet. Es werden Methoden zur Analyse Formaler Sprachen vorgestellt, die auch im Zusammenhang mit der Untersuchung von PASCAL – Programmen auf syntaktische Korrektheit wichtig sind.
Die grammatikalischen Regeln einer Sprache bestimmen ihre Syntax. Bei Formalen Sprachen reichen häufig wenige Regeln und ein stark eingeschränkter Wortschatz aus. Wichtig ist, dass die grammatischen Regeln eindeutig sind.
Beispiel 1: Umgangssprachliche Sätze
Beispiel 2: Wohlgeformte Klammern
Beispiel 3: Ausgewogene Muster
Beispiel 1: Umgangssprachliche Sätze
Es werden folgende Sätze als kleiner Ausschnitt der deutschen Sprache untersucht:
"Die Katze jagt",
"Das Buch frisst Heu",
"Susanne liest das Buch".
Grammatikalisch gesehen haben diese Sätze die Nominalphrase und die Verbalphrase gemeinsam. Die Nominalphrase ist daran erkennbar, daß sie ein Nomen oder ein Pronomen enthält. Die Verbalphrase ergänzt die Nominalphrase zu einem vollständigen Satz. In Form einer Grammatikregel wird der Sachverhalt folgendermaßen ausgedrückt:
(1) <Satz> --> <Nominalphrase><Verbalphrase>
Der Pfeil wird als 'besteht aus' gelesen. Die Nominalphrasen dieser Sätze bestehen aus Eigennamen oder einem Substantiv mit zugehörigem Artikel; dies formalisiert folgende Grammatikregel:
(2.1) <Nominalphrase> --> <Eigenname>
(2.2) <Nominalphrase> --> <Artikel><Substantiv>
Die Verbalphrase besteht entweder aus einem Verb oder aus einem Verb mit Akkusativobjekt; letzteres ist wieder eine Nominalphrase:
(3.1) <Verbalphrase> --> <Verb>
(3.2) <Verbalphrase> --> <Verb><Nominalphrase>
Außerdem ergibt sich ein kleines Lexikon:
<Eigenname> --> Susanne
<Substantiv> --> Katze | Pferd | Heu | Buch
<Artikel> --> der | die | das
<Verb> --> jagt | frißt | liest
Die Gesamtheit der Ersetzungsregeln (1) – (3) heißt Grammatik.
Anwendung: Es soll der Satz 'Susanne liest' hergeleitet werden!
Die Herleitung eines Satzes geschieht dadurch, dass jeweils der linke Teil einer Regel durch deren rechten Teil ersetzt wird, wobei stets mit <Satz> zu beginnen ist:
<Satz> => Nominalphrase><Verbalphrase> nach Regel (1)
=> <Eigenname><Verbalphrase> nach Regel (2.1)
=> Susanne<Verbalphrase> Lexikon
=> Susanne liest Lexikon
Den Pfeil liest man als 'wird ersetzt durch'. Der zweite Beispielsatz oben macht deutlich, daß sich auch semantisch sinnlose Sätze herleiten lassen. Möchte man sicherstellen, dass eine Grammatik nur sinnvolle Sätze erzeugt, muss man zusätzlich semantische Regeln festlegen.
Beispiel 1: Umgangssprachliche Sätze
Beispiel 2: Wohlgeformte Klammern
Beispiel 3: Ausgewogene Muster
Beispiel 2: Wohlgeformte Klammerterme
Wenn man in einem Rechenausdruck sämtliche Buchstaben und Zahlen weglässt, so erhält man Klammerterme der Form (); (()()) oder (((())())). Ein solcher Term muß gleich viele öffnende wie schließende Klammern besitzen. Die Grammatikregeln zur Erzeugung wohlgeformter Klammerterme lauten:
(1) S --> ( ) (2) S --> (S) (3) S --> SS
Mit (3) kann man Klammerterme aneinandereihen, mit (2) eine rekursive Verschachtelung vornehmen und mit (1) schließlich den Erzeugungsvorgang abbrechen.
Die Klammerfolge ( ( ) ) ( ( ) ( ) ) kann so abgeleitet werden:
S => SS => ( S ) S => ( ( ) ) ( S ) => ( ( ) ) ( S S ) => ( ( ) ) ( ( ) S ) => ( ( ) ) ( ( ) ( ) )
In den Grammatikregeln der zwei Beispiele kommen zwei Arten von Zeichen vor:
- Terminalzeichen : endgültige Zeichen; das sind Zeichen, die zum Alphabet gehören; in Beispiel 2 sind es die Klammern.
- Nicht-Terminalzeichen : vorläufige Zeichen; diese treten innerhalb einer Herleitung, aber nicht in einer endgültig abgeleiteten Zeichenfolge auf; im Beispiel 2 ist es das Zeichen S).
Formale Sprache:
Wenn X ein Alphabet, also eine endliche Menge von Zeichen ist, dann ist X* die Menge aller endlichen Zeichenfolgen über X . Jede Teilmenge L von X* heißt Formale Sprache.
Wenn G eine Grammatik mit X als Menge der Terminalzeichen ist, so ist L(G) die Menge aller Zeichenfolgen über X, welche mit Hilfe der Ersetzungsregeln aus G erstellt werden können. L(G) ist also die von G erzeugte formale Sprache.
Beispiel 1: Umgangssprachliche Sätze
Beispiel 2: Wohlgeformte Klammern
Beispiel 3: Ausgewogene Muster
Beispiel 3: Augewogene Bitmuster
Über den Terminalzeichen der Menge {0;1} wird eine Sprache betrachtet, bei der jedes Wort gleich viele Einsen wie Nullen enthalten muss. Die Worte 01, 10, 001011 oder 110010 gehören dazu. Als Nicht-Terminalzeichen dienen S, A und B, wobei S das Startzeichen ist. Dabei sollen aus A alle Wörter herleitbar sein, die genau eine Eins mehr als Nullen enthalten und aus B soll man alle Wörter erhalten, die genau eine 0 mehr als Einsen besitzen. Das führt zu folgenden Grammatikregeln:
(1) S --> 0A | 1B (2) A --> 1| 1S| 0AA (3) B --> 0| 0S| 1BB
Das Wort 110010 kann dann wie fogt abgeleitet werden:
S => 1B => 11BB => 11B0 => 110S0 => 1100A0 =>110010
[ Startseite]
[Anfang]