Theorie - Reguläre Ausdrücke und endliche Automaten

Reguläre Ausdrücke

Reguläre Ausdrücke dienen dazu, Sprachen zu beschreiben. So lässt sich die Sprache

LBin = {0, 1, 10, 11, 100, 101, 110, 111, 1000, ...}

mit Hilfe des folgenden regulären Ausdruckes beschreiben:

0+1(0+1)*

Zur Erinnerung: Reguläre Ausdrücke über dem Alphabet Σ werden wie folgt definiert:

Ein Automatenbaukasten

Zu einem regulären Ausdruck kann man recht einfach einen endlichen Automaten konstruieren, der die vom regulären Ausdruck beschriebene Sprache akzeptiert. Der Automat kann dabei aus den Bestandteilen des regulären Ausdrucks nach dem Baukastenprinzip konstruiert werden. Im Folgenden wird erst einmal der Automatenbaukasten vorgestellt.

Zum regulären Ausdruck Ø gehört der folgende endliche Automat:

Automat

Zum regulären Ausdruck λ gehört der folgende endliche Automat:

Automat

Zum regulären Ausdruck a mit a ∈ Σ gehört der folgende endliche Automat:

Automat

Wenn A1 ein endlicher Automat für den regulären Ausdruck α ist und A2 ein endlicher Automat für den regulären Ausdruck β, dann kombiniert man diese beiden endlichen Automenten wie folgt zu einem für den regulären Ausdruck αβ:

Automat

Wenn A1 ein endlicher Automat für den regulären Ausdruck α ist und A2 ein endlicher Automat für den regulären Ausdruck β, dann kombiniert man diese beiden Automenten wie folgt zu einem für den regulären Ausdruck α+β:

Automat

Wenn A1 ein endlicher Automat für den regulären Ausdruck α ist, dann erhält man wie folgt einen endlichen Automaten zum regulären Ausdruck (α)*:

Automat

Wenn man die vorgestellten Konstruktionsregeln befolgt, dann ergibt sich der folgende endliche Automat zum regulären Ausdruck 0+1(0+1)*:

Automat

Theorie

Die Vorüberlegungen deuten darauf hin, dass es Zusammenhänge zwischen endlichen Automaten und regulären Ausdrücken gibt.

Satz (über den Zusammenhang zwischen regulären Ausdrücken und (nicht)deterministischen endlichen Automaten):
Zu jedem regulären Ausdruck gibt es einen nichtdeterministischen endlichen Automaten (und folglich auch einen deterministischen endlichen Automaten), der die vom regulären Ausdruck beschriebene Sprache erkennt. Der (nicht)deterministische endliche Automat kann automatisiert aus dem regulären Ausdruck erzeugt werden.

Auch die umgekehrte Erzeugung ist möglich:

Satz (über den Zusammenhang zwischen (nicht)deterministischen endlichen Automaten und regulären Ausdrücken):
Zu jedem nichtdeterministischen endlichen Automaten (und folglich auch deterministischen endlichen Automaten) gibt es einen regulären Ausdruck, der die vom (nicht)deterministische endlichen Automaten erkannte Sprache beschreibt. Der reguläre Ausdruck kann automatisiert aus dem endlichen Automaten erzeugt werden.

Fasst man die Ergebnisse aus diesem und dem vorangegangenen Abschnitt zusammen, so erhält man den folgenden fundamentalen Satz:

Satz (über reguläre Sprachen und endliche Automaten):
Die Klasse der Sprachen, die mit einer regulären Grammatik beschrieben werden können, ist identisch mit der Klasse der Sprachen, die mit einem regulären Ausdruck beschrieben werden können. Sie ist ebenso identisch mit der Klasse der Sprachen, die von deterministischen endlichen Automaten bzw. von nichtdeterministischen endlichen Automaten erkannt werden können.

X

Fehler melden

X

Suche