Berry-Sethi-Verfahren

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

Zunächst wird dabei der reguläre Ausdruck in eine Baumstruktur überführt. Die Knoten entsprechen den Regeln des regulären Ausdrucks (Konkatenation $\cdot$, Transitiver Abschluss $^{*}$ und Vereinigung $\mid$). 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 ${\mathcal {O}}(n^{2})$.

Vorgehensweise

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

Das Symbol $\bullet$ 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.

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