Unterabschnitte
Induktive Definition:
- und sind reguläre Ausdrücke
- für jedes ist ein regulärer Ausdruck (alle Zeichen sind in sich selbst ein regulärer Ausdruck)
- Mit und sind auch ,
und reguläre Ausdrücke.
- Nichts sonst ist ein regulärer Ausdruck
CFG:
Syntaxdiagramm:
Beispiele für Syntaxdiagramme sehen wir gleich noch.
Zu jedem regulären Ausdruck
gibt es einen NFA
, so daß gilt
1.Verfahren:
Zu einem regulären Ausdruck
gehört eine Sprache
die wie folgt definiert ist:
Dies läßt uns erkennen, wie wir einen Automaten aus einem regulären Ausdruck bilden können. Wir können dies, indem wir triviale Automaten für Teilausdrücke zur Verfügung stellen und mit diesen Operationen für die Vereinigung, den Durchschnitt und den Kleenabschluß durchführen:
2.Verfahren:
Wir können aus einem initialen NFA einen äquivalenten NFA zum regulären Ausdruck konstruieren, indem wir die Kanten rekursiv ersetzen:
Initialer NFA:
Wenn
:
Wenn
:
Wenn
:
Zu jedem DFA
gibt es einen regulären Ausdruck
, so daß gilt
Wir wenden das Verfahren des dynamischen Programmierens an. Dabei erstellen wir für Teilmengen an Zuständen des DFAs reguläre Ausdrücke und fügen diese zu immer größer werdenden Teilmengen zusammen. Wir starten dabei bei Teilmengen aus zwei oder einem Zustand, wobei bei zwei Zuständen diese Zustände direkt verbunden sein müssen.
Es gilt für
und
:
Wir können folgende reguläre Ausdrücke erzeugen:
Diese Ausdrücke können wir nach folgender Formel zusammenfügen
Wieder der reguläre Ausdruck