Exkurs - Anwendung der Theorie

Problem

Im Abschnitt Ausblick - Theoriebildung wurde das folgende Problem formuliert:

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

Die Sprache L_EMail soll dabei durch folgende Syntaxdiagramme beschrieben werden:

Emailadresse:

User:

Domain:

Subdomains:

Topleveldomain:

Name:

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 L_EMail nicht regulär ist. Die gezeigte Grammatik hilft nur beim Problemlösen nicht weiter.

Die Sprache L_EMail 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 L_EMail lässt sich leicht der folgende erkennende Automat konstruieren:

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).