Exkurs - Anwendung der Theorie

Problem

Im Abschnitt Ausblick - Theoriebildung wurde das folgende Problem formuliert:

Gibt es einen endlichen Automaten A, der die Sprache LEMail erkennt?

Die Sprache LEMail soll dabei durch folgende Syntaxdiagramme beschrieben werden:

Emailadresse:

Syntaxdiagramm

User:

Syntaxdiagramm

Domain:

Syntaxdiagramm

Subdomains:

Syntaxdiagramm

Topleveldomain:

Syntaxdiagramm

Name:

Syntaxdiagramm

Buchstabe:

Lösung 1

Zu den Syntaxdiagrammen lässt sich direkt eine Grammatik angeben:

emailadresse -> user @ domain
user -> name
domain -> subdomains topleveldomain
subdomains -> name .
subdomains -> name . subdomains
topleveldomain -> b b
name -> buchstabe
name -> buchstabe name
buchstabe -> b

Abkürzend kann man sie so schreiben:

E -> U@D
U -> N
D -> ST
S -> N.
S -> N.S
T -> bb
N -> B
N -> BN
B -> b

Diese Grammatik ist nicht regulär. Das heißt aber nicht, dass die Sprache LEMail nicht regulär ist. Die gezeigte Grammatik hilft nur beim Problemlösen nicht weiter.

Die Sprache LEMail wird ebenfalls von der folgenden Grammatik erzeugt (siehe Experimente mit JFlap):

E -> bU
U -> bU
U -> @S
S -> bB
B -> bB
B -> .S
B -> .T
T -> bZ
Z -> b

Wenn man sie geringfügig abändert, erhält man eine reguläre Grammatik:

E -> bU
U -> bU
U -> @S
S -> bB
B -> bB
B -> .S
B -> .T
T -> bZ
Z -> bX
X -> λ

Nach dem Satz über den Zusammenhang zwischen regulären Sprachen und deterministischen Automaten gibt es zu dieser Grammatik einen deterministischen endlichen Automaten, der die von der Grammatik erzeugte Sprache erkennt. Dieser Automat kann auch Schritt für Schritt (z.B. mit Hilfe von JFlap) erzeugt werden (siehe Übungen).

Lösung 2

Zur Sprache LEMail lässt sich leicht der folgende erkennende Automat konstruieren:

Akzeptor

Dieser Automat ist nichtdeterministisch. Nach dem Satz über den Zusammenhang zwischen deterministischen und nichtdeterministischen Automaten gibt es einen deterministischen endlichen Automaten, der dieselbe Sprache erkennt. Dieser Automat kann auch Schritt für Schritt (z.B. mit Hilfe von JFlap) erzeugt werden (siehe Übungen).

X

Fehler melden

X

Suche