Informatikmaterialien 
von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |


Richard-Wossidlo-Gymnasium Ribnitz-Damgarten
Fachbereich Informatik


Formale Sprachen


Der Begriff der Formalen Sprache soll zeigen, dass es sich bei den betrachteten Sprachen nicht um natürliche oder Programmier-Sprachen handelt. In Formalen Sprachen spielt die Semantik (Bedeutung der Sätze) keine, die Syntax (Lehre vom Satzbau; Grammatik) hingegen die zentrale Rolle. 

Einführendes Beispiel: Lachautomaten-Akzeptor

Aufgabe: Es ist ein Akzeptor zu konstruieren, der folgendes erkennt: ha!, haha!, hahaha! usw. 

Lösung als Automatengraph:

Modellierung in PROLOG:

% Start- und Endzustände festlegen
start(1).
ende(4).

% Überführungsfunktion delta festlegen
% Überführungsfunktionen zum Zustand 5 
% müssen nicht implementiert werden (Warum eigentlich? ;) )
delta(1, h, 2).
delta(2, a, 3).
delta(3, h, 2).
delta(3, '!', 4).

% Prüfen, ob Zeichenkette
%  (1) der Startzustandsbedingung genügt
%  (2) den restlichen Bedingungen genügt
akzeptiert(String) :- start(Startzustand), pruefer(Startzustand, String).

pruefer(Zustand, []) :- ende(Zustand).
pruefer(Zustand, [Zeichen|Restzeichen]) :- delta(Zustand, Zeichen, NeuerZustand), pruefer(NeuerZustand, Restzeichen).

Der Automat akzeptiert alle Wörter der geforderten Gestalt. Er ist also in der Lage, eine – wenn auch beschränkte – Sprache zu erkennen.

Formale Sprache

Ein Wort w ist die Hintereinanderreihung endlich vieler Zeichen aus einem vorgegebenen Alphabet  X. Die Menge aller Wörter wird X* bezeichnet. Das leere Wort gehört zu X*, besteht aus keinem Alphabetzeichen und wird mit ε bezeichnet. 

Beispiel für den Lachautomaten:

X = {h, a, !}
X* = {ε, h, a, !, ha, h!, ah, a!, !h, !a, hh, aa, !!, ...}

Die formale Sprache L über einem Alphabet X ist eine beliebige Teilmenge aus X*, L X*. Wörter sind die Elemente von L. 

Beispiel für den Lachautomaten: L soll die Lachsprache sein

X = {h, a, !}
L = {ha!, haha!, hahaha!, ...} = {(ha)n ! | n > 0}

In formalen Sprachen spielt die Semantik keine Rolle! 

Übungen

  1. Man gebe einen Automaten an, der die Sprache L = {a bn c | n ≥ 0} akzeptiert.

  2. Man gebe einen Automaten an, der ein Wort einer Sprache über das Alphabet X = {a,b} genau dann akzeptiert, wenn die Differenz der Anzahl der Elemente a und der Anzahl der Elemente b in diesem Wort durch vier teilbar ist.

  3. Man konstruiere einen Akzeptor für die Menge aller Binärzahlen (ohne führende Nullen)



zur Startseite
© Tino Hempel 1997 - 2007
Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.