Ausblick - Theoriebildung

Probleme als Ausgangspunkt für Theoriebildung

Probleme, die sich nur schwer oder auch gar nicht lösen lassen, bilden oft den Ausgangspunkt für vertiefende Studien. Wenn es einem dabei gelingt, eine Theorie zum Gegenstandsbereich zu entwickeln, gewinnt man oft auch Klarheit bzgl. der gewünschten Problemlösungen.

Die beiden folgenden Probleme sollen eine solche Theoriebildung motivieren. Zunächst sollst du dich mit den Problemen auseinander setzen. Es ist dabei durchaus möglich, dass du die Probleme nicht auf Anhieb lösen kannst. In den folgenden Abschnitten werden dann die Theoriebausteine entwickelt, die zu den Lösungen der Probleme führen.

Vereinfachte E-Mail-Adressen

Wir betrachten die Sprache L_EMail der stark vereinfachten E-Mail-Adressen, die durch folgende Syntaxdiagramme festgelegt wird. Beachte, dass in diesen Adressen nur die Symbole b, @ und . vorkommen dürfen. Beachte auch, dass eine Topleveldomain hier nur aus genau zwei Buchstaben bestehen soll. Eine nach diesen Syntaxdiagrammen gültige E-Mail-Adresse ist z.B. bb@b.bbb.bb.

Emailadresse:

User:

Domain:

Subdomains:

Topleveldomain:

Name:

Buchstabe:

Problem: Erkennung vereinfachter E-Mail-Adressen

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

Aufgabe 1

Versuche, einen Akzeptor A mit L(A) = L_EMail zu konstruieren.

Klammerausdrücke

Wir betrachten die Sprache L_Klammer der stark vereinfachten Klammerausdrücke, die durch folgende Syntaxdiagramme festgelegt wird.

Klammer:

Zur Sprache L_Klammer gehören also alle Klammerausdrücke der Gestalt

(), (()), ((())), ...,

bei denen nach einer Folge öffnender Klammern genau so viele schließende Klammern folgen.

Problem: Erkennung von Klammerausdrücken

Gibt es einen endlichen Automaten, der die Sprache L_Klammer erkennt?

Aufgabe 2

Versuche, einen Akzeptor A mit L(A) = L_Klammer zu konstruieren.