imported>PlusMinuscule: Siehe auch: Thompson-Konstruktion ergänzt

2025-06-26T11:56:26Z

Siehe auch: Thompson-Konstruktion ergänzt

Neue Seite

Beim '''Berry-Sethi-Verfahren''' (nach [[Gérard Berry]] und [[Ravi Sethi]]; auch '''Gluschkow-Konstruktion''', nach [[Wiktor Michailowitsch Gluschkow]]) handelt es sich um einen Algorithmus zur Überführung eines [[regulärer Ausdruck|regulären Ausdrucks]] in einen [[nichtdeterministischer endlicher Automat|nichtdeterministischen endlichen Automaten]].

Zunächst wird dabei der reguläre Ausdruck in eine [[Baum (Graphentheorie)|Baumstruktur]] überführt. Die Knoten entsprechen den Regeln des regulären Ausdrucks (Konkatenation <math>\cdot</math>, Transitiver Abschluss <math>^*</math> und Vereinigung <math>\mid</math>).
Die Blätter repräsentieren die Elemente des Eingabealphabets im regulären Ausdruck, also genau die Zeichen, aus denen sich gültige Wörter zusammensetzen können. Alle weiteren Berechnungen finden mit Hilfe dieser Darstellungsform statt.

Stellt man sich nun einen Punkt vor, der beginnend bei der Wurzel des Syntaxbaums um den Baum ''herumwandert'', so können sukzessive alle Wörter des regulären Ausdrucks erzeugt werden. Mit Hilfe dieses Punktes wird nun der endliche Automat konstruiert. Die Zeitkomplexität des Verfahrens ist <math>\mathcal O (n^2)</math>.

== Vorgehensweise ==

# Bestimme empty[r] für alle Knoten r des Baumes. Dies ist mit einer post-order DFS möglich (DFS: Depth-First Search, [[Tiefensuche]]).
# Bestimme first[r] für alle Knoten r des Baumes. Dies ist mit einer post-order DFS möglich.
# Bestimme next[r] für alle Knoten r des Baumes. Dies ist mit einer pre-order DFS möglich.
# Bestimme last[r] für alle Knoten r des Baumes. Dies ist mit einer post-order DFS möglich.
# Integration:
## Die Zustände des Automaten sind: <math>\{ \bullet e \} \cup \{i \bullet \mid \mbox{i ist Blatt}\}</math>
## Der Startzustand des Automaten ist: <math> \bullet e </math>
## Die Endzustände des Automaten sind:
###<math>last[e]</math>, falls <math>empty[e] = false</math> und
###<math>\{\bullet e\} \cup last[e]</math>, falls <math>empty[e] = true</math>
## Die Übergänge des Automaten sind:
###<math>( \bullet e, a, i\bullet)</math>, falls <math>i \in first[e]</math> und <math>i</math> mit <math>a</math> beschriftet ist, und
###<math>( i \bullet, a, i'\bullet)</math>, falls <math>i' \in next[i]</math> und <math>i'</math> mit <math>a</math> beschriftet ist.

Das Symbol <math>\bullet</math> markiert hierbei den Punkt, der um den Baum herumwandert. Der resultierende endliche Automat ist im Allgemeinen nichtdeterministisch und kann daher noch durch die [[Potenzmengenkonstruktion]] deterministisch gemacht werden.

== Siehe auch ==

* [[Thompson-Konstruktion]]

== Literatur ==
* Gérard Berry, Ravi Sethi: ''From regular expressions to deterministic automata.'' In: ''Theoretical Computer Science.'' 48, 1986, {{ISSN|0304-3975}}, S. 117–126.
* Viktor M. Glushkov: ''The abstract theory of automata.'' In: ''Russian Mathematical Surveys.'' 16, 1961, {{ISSN|0036-0279}}, S. 1–53.
* [[Anne Brüggemann-Klein]]: ''Regular expressions into finite automata''. In: ''Theoretical Computer Science'' 120, 1993, S. 197–213. {{DOI|10.1016/0304-3975(93)90287-4}}

[[Kategorie:Automatentheorie]]
[[Kategorie:Compilerbau]]
[[Kategorie:Algorithmus]]

Berry-Sethi-Verfahren - Versionsgeschichte

imported>PlusMinuscule: Siehe auch: Thompson-Konstruktion ergänzt