Informatikmaterialien |
Startseite
| Informatik | Physik
| Mathematik | Sonstiges
| |
Richard-Wossidlo-Gymnasium Ribnitz-Damgarten |
---|
- 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.
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.
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!
Man gebe einen Automaten an, der die Sprache L = {a bn c | n ≥ 0} akzeptiert.
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.
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. |